中文摘要：

对以最小化加工时间为目标的柔性制造系统无死锁调度问题，提出了一种遗传调度算法．算法考虑到同类工件具有预先确定的相同加工路径，而各工序的处理时间与工件有关．用Petri网对工序和资源分配进行逻辑建模，利用遗传算法，采用工序自然编码方式，基于系统的最佳避免死锁Petri网控制器，检测染色体的可行性，修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束，从而保证算法所利用的所有染色体都对应系统的可行调度．仿真结果表明了算法的可行性和有效性．

英文摘要：

A deadlock-free genetic scheduling algorithm for flexible manufacturing systems is presented to minimize makespan. This algorithm takes into account the facts that jobs of the same type have the same predetermined processing route, and the processing time is different from different job. The operation sequences of jobs and the allocation of resources are modeled logically by a Petri net. In the proposed genetic algorithm, the operation sequence of all jobs in the system is encoded as a chromosome. By using the deadlock-avoidance Petri net controller for the system, the chromosome is tested and amended so that it can be decoded into a schedule that satisfies the resource constraint and the deadlock-free constraint. Thus, all chromosomes in the algorithm are corresponding to feasible schedules. Experimental results demonstrate the effectiveness and feasibility of the proposed genetic algorithm.