Xing KeYi, Han LiBin, Zhou MengChu, Wang Feng
State Key Laboratory for Manufacturing Systems Engineering and the Systems Engineering Institute, Xi’an Jiaotong University, Xi’an, China.
IEEE Trans Syst Man Cybern B Cybern. 2012 Jun;42(3):603-15. doi: 10.1109/TSMCB.2011.2170678. Epub 2011 Nov 16.
Deadlock-free control and scheduling are vital for optimizing the performance of automated manufacturing systems (AMSs) with shared resources and route flexibility. Based on the Petri net models of AMSs, this paper embeds the optimal deadlock avoidance policy into the genetic algorithm and develops a novel deadlock-free genetic scheduling algorithm for AMSs. A possible solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the one-step look-ahead method in the optimal deadlock control policy, the feasibility of a chromosome is checked, and infeasible chromosomes are amended into feasible ones, which can be easily decoded into a feasible deadlock-free schedule. The chromosome representation and polynomial complexity of checking and amending procedures together support the cooperative aspect of genetic search for scheduling problems strongly.
无死锁控制和调度对于优化具有共享资源和路径灵活性的自动化制造系统（AMS）的性能至关重要。基于AMS的Petri网模型，本文将最优死锁避免策略嵌入遗传算法，开发了一种新颖的AMS无死锁遗传调度算法。调度问题的一个可能解被编码为染色体表示，它是零件的重复排列。通过在最优死锁控制策略中使用一步前瞻方法，检查染色体的可行性，并将不可行染色体修正为可行染色体，这些可行染色体可以很容易地解码为可行的无死锁调度。染色体表示以及检查和修正过程的多项式复杂度共同有力地支持了遗传搜索在调度问题上的协同作用。
