基于Petri网和混合遗传算法的JSP优化调度
|
摘要
本文以带有控制器的Petri网和混合遗传算法为工具，对具有多工艺加工路径的生产车间调度问题进行研究。该算法不仅通过与其他学者提出的算法相比较，而且通过了标准算例的验证，证明了其正确性和优越性。针对受双资源制约的动态生产车间调度问题，提出并研究了新的调度策略和方法，并给出了最佳调度策略。本文的研究结果和内容可概括为以下的几个主要方面：
利用局部设计和Petri网简化技术提出了一种实现库所和变迁混合不等式约束Petri网反馈控制器的新方法，该方法计算简单无需搜索整个系统的状态空间，因此在计算效率上具有明显的优势，尤其是对规模较大的系统，其优势更加明显。
以带有控制器的Petri网为建模工具研究了单资源生产车间调度优化问题，应用了一种将遗传算法和模拟退火算法相结合的调度算法，将加工计划与生产调度同时考虑。通过仿真实验证明了其正确性和优越性。
在双资源静态调度问题的基础上，对于机床设备／工人受制约的动态调度问题进行了重点研究。对机床故障、工人离岗、定单取消等基于时间和任务进行分类，决定是否执行再调度。尤其重要的是提出了处理紧急工件的新方法，把剩余任务和紧急任务当成两个独立的任务分别处理，在紧急任务为最优调度的基础上选取剩余任务的最优调度，该方法不仅实现了总体最优，而且局部也是最优的。
最后，用Delphi开发了实用性的生产车间调度软件。以XML为数据存储方式，并以其作为对象兼数据交换的接口信息。
The present dissertation uses Petri nets (PN) and hybrid genetic algorithms as tool to study the scheduling optimization of job shop with multiple process plants. The algorithm is compared with other scheduling algorithms and is tested by standard benchmark scheduling problem. The result has shown that the proposed algorithm is correct and excellent. To the dynamic dual-resource constrained scheduling problem, new strategies and methods are studied and analyzed. The best strategy is pointed out. The principal research results and contents can be outlined as following:
Firstly, A new method of feedback controller design with combined place marking and transition firing constraint based on part net design and Petri net reduction technique is proposed for the first time in this dissertation. The method has the advantage of simpler computation and avoiding searching the entire state space over the reported methods, thus the computation efficiency superiority of the method is evident. The advantage is more obvious especially when the system is large and complex. The control concept of this method is plain and easy to be understood by the control engineers.
Based on Petri net with controller , single- resource constraint job shop scheduling optimization problem is studied. A hybrid algorithm combined genetic algorithm and simulated annealing algorithm is applied, which considers process plan and scheduling. The result has shown that the proposed algorithm is correct and excellent.
The dual-resource constraints dynamic scheduling is studied based on static scheduling. First, classify for machine breaks down, worker leaves, order cancels based on time and task, then decide whether carry out re-scheduling. Especially important, a new method of disposing urgent jobs is proposed, which deal with remainder and urgent jobs separately. Select optimal results of remainder jobs based on optimal scheduling of urgent jobs. The method realizes not only whole is optimal but also part is optimal too.
Finally, a job shop scheduling software is developed using Delphi.
利用局部设计和Petri网简化技术提出了一种实现库所和变迁混合不等式约束Petri网反馈控制器的新方法，该方法计算简单无需搜索整个系统的状态空间，因此在计算效率上具有明显的优势，尤其是对规模较大的系统，其优势更加明显。
以带有控制器的Petri网为建模工具研究了单资源生产车间调度优化问题，应用了一种将遗传算法和模拟退火算法相结合的调度算法，将加工计划与生产调度同时考虑。通过仿真实验证明了其正确性和优越性。
在双资源静态调度问题的基础上，对于机床设备／工人受制约的动态调度问题进行了重点研究。对机床故障、工人离岗、定单取消等基于时间和任务进行分类，决定是否执行再调度。尤其重要的是提出了处理紧急工件的新方法，把剩余任务和紧急任务当成两个独立的任务分别处理，在紧急任务为最优调度的基础上选取剩余任务的最优调度，该方法不仅实现了总体最优，而且局部也是最优的。
最后，用Delphi开发了实用性的生产车间调度软件。以XML为数据存储方式，并以其作为对象兼数据交换的接口信息。
The present dissertation uses Petri nets (PN) and hybrid genetic algorithms as tool to study the scheduling optimization of job shop with multiple process plants. The algorithm is compared with other scheduling algorithms and is tested by standard benchmark scheduling problem. The result has shown that the proposed algorithm is correct and excellent. To the dynamic dual-resource constrained scheduling problem, new strategies and methods are studied and analyzed. The best strategy is pointed out. The principal research results and contents can be outlined as following:
Firstly, A new method of feedback controller design with combined place marking and transition firing constraint based on part net design and Petri net reduction technique is proposed for the first time in this dissertation. The method has the advantage of simpler computation and avoiding searching the entire state space over the reported methods, thus the computation efficiency superiority of the method is evident. The advantage is more obvious especially when the system is large and complex. The control concept of this method is plain and easy to be understood by the control engineers.
Based on Petri net with controller , single- resource constraint job shop scheduling optimization problem is studied. A hybrid algorithm combined genetic algorithm and simulated annealing algorithm is applied, which considers process plan and scheduling. The result has shown that the proposed algorithm is correct and excellent.
The dual-resource constraints dynamic scheduling is studied based on static scheduling. First, classify for machine breaks down, worker leaves, order cancels based on time and task, then decide whether carry out re-scheduling. Especially important, a new method of disposing urgent jobs is proposed, which deal with remainder and urgent jobs separately. Select optimal results of remainder jobs based on optimal scheduling of urgent jobs. The method realizes not only whole is optimal but also part is optimal too.
Finally, a job shop scheduling software is developed using Delphi.
引文
1. Andreas C. Nearchou. A novel meta-heuristic approach for the flow shop scheduling problem[J], Engineering Applications of Artificial Intelligence ,2004, 17 :289 - 300
2. K. Steinhofel, A. Albrecht, C.K. Wong. An experimental analysis of local minima to improve neighbourhood search[J], Computers & Operations Research , 2003, 30: 2157 -2173
3. Huang Wenqi, Yin Aihua. An improved shifting bottleneck procedure for the job shop scheduling problem[J], Computers & Operations Research, 2004, 31: 2093 - 2110
4. Masahiro Arakawa, Masahiko Fuyuki, Ichiro Inoue. An optimization-oriented method for simulation -based job shop scheduling incorporating capacity adjustment function[J], Int. J. Production Economics, 2003, 85 :359 - 369
5. Marco Pranzo. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times[J], European Journal of Operational Research , 2004, 153: 581 - 592
6. Gur Mosheiov, Uri Yovel. Comments on "Flow shop and open shop scheduling with a critical machine and two operations per job"[J], European Journal of Operational Research ,2004, 157: 257 - 261
7. M.S. Jayamohan, Chandrasekharan Rajendran. Development and analysis of cost-based dispatching rules for job shop scheduling [J], European Journal of Operational Research,2004, 157 :307 - 321
8. Ruedee Rangsaritratsamee, William G. Ferrell Jr., Mary Beth Kurz. Dynamic rescheduling that simultaneously considers efficiency and stability[J], Computers & Industrial Engineering, 2004, 46 : 1-15
9. Faizul Huq, Kenneth Cutright, Clarence Martin. Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study [J], Omega, 2004, 32: 121 -129
10. K. SteinhoK fel, A. Albrecht, C.K. Wong. Fast parallel heuristics for the job shop scheduling problem[J], Computers & Operations Research, 2002, 29:151-169.
11. Samir Allet. Handling flexibility in a "generalised job shop" with a fuzzy approach[J],??European Journal of Operational Research, 2003, 147 :312 - 333
12. Gerhard J. Woeginger. Inapproximability results for no-wait job shop scheduling[J], Operations Research Letters, 2004, 32: 320 - 325
13. Alessandro Mascis, Dario Pacciarelli. Job-shop scheduling with blocking and no-wait constraints [J], European Journal of Operational Research, 2002,143: 498 - 517
14. S.H. Yoon, J. A.Ventura. Minimizing the mean weighted absolute deviation from due dates in lot-streaming flow shop scheduling [J], Computers & Operations Research , 2002,29:1301-1315
15. Volker Lau, Frank Werner. On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties [J], Computers & Operations Research, 2004, 31 : 317-345
16. I. Sabuncuoglu, A. Comlekci. Operation-based flowtime estimation in a dynamic job shop[J], Omega, 2002, 30: 423 - 442
17. R.M. Aiex , S. Binatob, M.G.C. Resende. Parallel GRASP with path-relinking for job shop scheduling [J], Parallel Computing , 2003, 29: 393 - 430
18. Yazid Mati, Xiaolan Xie, The complexity of two-job shop problems with multi-purpose unrelated machines[J], European Journal of Operational Research , 2004, 152 : 159 -169
19. K. Steinhofel, A. Albrecht, C.K. Wong. The convergence of stochastic algorithms solving flow shop scheduling[J], Theoretical Computer Science, 2002, 285: 101 - 117
20. Ching-Fang Liaw, Chun-Yuan Cheng, Mingchih Chen, The total completion time open shop scheduling problem with a given sequence of jobs on one machine [J], Computers & Operations Research, 2002, 29:1251-1266
21. Berkin Toktas, Meral Azizoglub, Suna Kondakci Koksalan. Two-machine flow shop scheduling with two criteria: Maximum earliness and makespan [J], European Journal of Operational Research, 2004, 157 : 286 - 295
22. BEATRICE M. OMBUKI, MARIO VENTRESCA. Local Search Genetic Algorithms for the Job Shop Scheduling Problem[J], Applied Intelligence, 2004,21:99-109
23. IBRAHIM KATTAN. Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods[J], Journal of Intelligent Manufacturing, 2003, 14:107-121
24. ROGER Z. R'IOS-MERCADO, JONATHAN F. BARD. The Flow Shop Scheduling??Polyhedron with Setup Times[J], Journal of Combinatorial Optimization, 2003, 7: 291-318
25. STEPHEN OMAN, PADRAIG CUNNINGHAM. Using case retrieval to seed genetic algorithms[J], International Journal of Computational Intelligence and Applications, 2001, 1, (1): 71-82
26．吴云高，王万良．基于遗传算法的车间调度方法及其应用[D]，浙江：浙江工业大学，2002
27. Davis W, Jones A. A real-time Production scheduler for a stochastic manufacturing environment [J], International Journal of Computer Integrated Manufacturing, 1988, 1(2): 101-112
28. Gershwin S. Hierarchical flow control: a framework for scheduling and Planning discrete events in manufacturing systems[C]. Proceedings of IEEE Special Issue on Discrete Event Systems, 1989, 77: 195-209
29. Lun P B, Hoitomt F J, Max E. Scheduling generation and reconfiguration for Parallel machines[J], IEEE Transactions of Robotics and Automation, 1990, 6(6): 687-696
30. Chen H X, Cheng B C, Proth J M. A more efficient Lagrangian relaxation approach to job shop scheduling Problems[C]. Proceeds of IEEE International Conference on Robotics and Automation, Japan, 1995, 496-501
31. Fox M. Constraint-Directed Search: A case study of Job Shop Scheduling[D], Carnegie-Mellon University, 1983
32. Wysk R, Wu D, Yang R. A multi-pass expert control system(MPECS) for flexible manufacturing systems[J], NBS Special Publication, 1986, 724: 251-278
33. Zweben M, Fox M, San Francisco. OPIS: A methodology and architecture for reactive scheduling, Intelligent Scheduling[M], California: Morgan Kaufman, 1995, 29-66
34. Zweben M, Fox M, San Francisco. Scheduling as intelligent control of decision-making and constraint Propagation, Intelligent Scheduling[M], California: Morgan Kaufman, 1995, California: Morgan Kaufman, 1995, 67-98
35. Parunak H, Irish B, Kindrick J et al. Fractal actors for distributed manufacturing control[C]. Proceedings of the Second IEEE Conference on Artificial Intelligence Applications, 1985, 653-660
36. Daouas T, Ghedira K, Muller J. Distributed flow shop scheduling Problem versus local??optimization[C]. Proceedings of the First International Conference on Multi-Agent Systems, Cambridge, Massachusetts: MIT Press, 1995
37．饶运清，谢畅，李淑霞．基于多Agent的Job Shop调度方法研究[J]，中国机械工程，2004，15(10)：873-877
38．王太江，王时龙，龙雪峰．基于移动AGENT的敏捷车间调度控制系统建模[J]，机电一体化，2004，2：26-29
39. Rabelo L, Sahinoglu M, Avula X. Flexible manufacturing systems scheduling using QLearning[C]. Proceedings of. the World Congress on Neural Networks, San Diego, California: 1994, 1378-1385
40. Foo Y, Takefuji Y. Stochastic neural networks for solving job-shop scheduling: Part 2 Architecture and simulations[C]. Proceedings of the IEEE International Conference on Neural Networks, IEEE TAB 1988: 11283-11290
41. Zhou D, Cherkassky V, Baldwin T et al. Scaling neural networks for job shop scheduling[C], Proceedings of the International Conference on Neural Networks, 1990, 3: 889-894
42. Taillard E, Some efficient heuristic methods for the flow shop sequencing Problem[J], European Operation Research, 1990, 47(1): 65-74
43. Manuel L, Bames J W, Glover F. Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times[J], Applied Intelligence, 1993(3): 159-172
44．姜思杰，张付亮．基于遗传和禁忌算法求解一类车间调度问题，计算机集成制造系统—CIMS[J]，2003，9(11)：984-988
45. R. S. CINTIA, A. A. VINICIUS, L. MANUEL. Tardiness minimization in a flexible job shop: A tabu search approach[J], Journal of Intelligent Manufacturing, 2004, 15: 103-115
46. Vakharia A, Cheng Y. A simulated annealing approach to scheduling a manufacturing cell[J], Naval Research Logistics, 1990, 37: 559-577
47. Jeffcoat D, Bulfln R. Simulated annealing for resource-constrained scheduling[J], European Journal of Operational Research, 1993, 70: 43-51
48. A. M. EMIN, F. TERENCEC.. A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimization Problems[J], Journal of Heuristics, 2004, 10:??269-292
49. L.Chinyao, Y.Y.Jinn, I.H.Kai. A robust siulated annealing heuristic for flow shop scheduling problems[J],Int JAdv Manuf Technol, 2004,23:762-767
50. Slany W. Scheduling as a fuzzy multiple criteria optimization problem, CD-Technical Report, 1994, 94/62, Technical University of Vienna
51. Grabot B, Geneste L. Dispatching rules in scheduling: a fuzzy approach[J], International Journal of Production Research, 1994,32(4): 903-915
52. Tsujimura Y, Park S, Chang S et al. An effective method for solving flow shop scheduling problems with fuzzy processing times [J], Computers and Industrial Engineering, 1993,25:239-242
53. Kenneth N M, Vincent C S W. Unifying the theory and practice of production scheduling[J], Journal of Manufacturing Systems, 1999,18(4): 241-255
54. Sergio Cavalieri, Paolo Gaiardelli. Hybrid genetic algorithms for a multiple- objective scheduling problem[J], Journal of Intelligent Manufacturing, 1998, 9: 361-367
55. C. W. Zhao, Z. M.Wu. A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes[J], Journal of Heuristics, 2004,10:269-292
56. H. Z. Jia, A. Y. C. Nee et al. A modified genetic algorithm for distributed scheduling problems [J], Journal of Intelligent Manufacturing ,2003, 14:351-362
57. L. X. Tang, J. Y. Liu. A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time [J], Journal of Intelligent Manufacturing, 2002, 13:61-67
58. C. George, S. Velusamy. Dynamic scheduling of manufacturing job shops using genetic algorithms [J], Journal of Intelligent Manufacturing, 2001,12:281-293
59. W. M. Cheung, H. Zhou. Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times[J], Annals of Operations Research, 2001, 107:65-81
60. C. Oguz, Y.F. Fung et al. Parallel genetic algorithm for a flow shop problem with multiprocessor tasks[J], ICCS 2003, LNCS 2659, 2003,548-559
61. J. G. Qi, G. R. Bruns, D. K. Harrison. The application of parallel multipopulation genetic algorithms to dynamic job shop scheduling[J], The International Journal of Advanced Manufacturing Technology,2000,16:609-61562. L. Wang, L. Zhang, D. Z. Zheng. The ordinal optimization of genetic control parameters for flow shop scheduling[J], The International Journal of Advanced Manufacturing Technology, 2004, 23: 812-819
63. J. H. Chen, L. C. Fu, M. H. Lin, et al. Petri-net and GA based approach to modeling, scheduling, and performance evaluation for wafer fabrication[J], IEEE Transaction on Robotics and Automation, 2001, 17(5): 619-636
64．王笑蓉，吴铁军．基于Petri网仿真的柔性生产调度-蚁群-遗传递阶进化优化方法[J]，浙江大学学报(工学版)，2004，38(3)：286-291
65．郑锋，孙树栋，吴秀丽．基于遗传算法和模型仿真的调度规则决策方法[J]，计算机集成制造系统，2004，10(7)：808-814
66．蔡宗琰，王宁生等．基于赋时可重构Petri网的可重构制造系统调度算法[J]，西南交通大学学报，2004，39(3)：341-344
67. K. Ibrahim, M. Boleslaw, K. Khalid et al. Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods[J], Journal of Intelligent Manufacturing, 2003, 14: 107-12
68．熊惠明，徐国华．用Petri网实现FMS负载平衡调度[J]，现代生产与管理技术，成组技术与生产现代化，2004，21(1)：28-31
69．张建朝，刘振娟，李宏光．Petri网图形建模仿真系统的研究与开发[J]，北京化工大学学报，2004，31(2)：100-103
70．韩耀军，蒋昌俊，罗雪梅．基于Petri网合成与化简的分布式数据库系统并发控制的死锁检测[J]，小型微型计算机系统，2004，25(5)：821-826
71．郭彩芬，王宁生．串行生产线生产与库存的最优控制[J]，中国机械工程，2004，15(10)：891-894
72. H. X. Chen. Control synthesis of Petri nets based on S-Decreases[J], Discrete Event Dynamic Systems: Theory and Application, 2000, 10: 233-249
73. M. Ohbayashi, K. Hirasawa, et al. Nonlinear control system using learning Petri network[J], Electrical Engineering in Japan, 2000, 131(3): 58-69
74. S. BULACH, A. BRAUCHLE. Design and implementation of discrete event control systems: A Petri net based hardware approach[J], Discrete Event Dynamic Systems: Theory and Application, 2002, 12: 287-309
75. Yasutaka, Fujimoto. Design of discrete time polynomial nonlinear systems and its??application to sequential control[J], Electrical Engineering in Japan, 2004, 149(2): 60-72
76. N. A. Anisimov, E. A. Golenkov, D. I. Kharitonov. Compositional Petri net approach to the development of concurrent and distributed systems[J], Programming and Computer Software, 2001, 27(6): 309-319
77. K. JAN. Input-output relation and time-optimal control of a class of hybrid Petri nets using semiring[J], Discrete Event Dynamic Systems: Theory and Application, 2001, 11: 59-75
78. D. A. Zaitsev. Invadants of timed Petri nets[J], Cybernetics and Systems Analysis, 2004, 40(2): 226-237
79．江志斌．Petri网及其在制造系统建模与控制中的应用[M]，北京：机械工业出版社，2004
80. Holloway LE, Krogh BH. Synthesis of feedback logic for a class of controlled Petri nets[J], IEEE T-AC, 1990, 35(5): 514～523
81. Li Y, Wonham WM. Control of vector discrete-event systems Ⅰ——The base model[J], IEEE T-AC, 1993, 38(8): 1214～1227
82. Li Y, Wonham WM. Control of vector discrete-event systems Ⅱ——The base mode[J], IEEE T-AC, 1994, 39(3): 512～531
83. Yamalidou K, Moody JO, Lemmon MD, Antsaldis PJ. Feedback control of Petri nets based on place invadants[J], Automatica, 1996, 32(1): 15-28
84. Banaszak Z A, Krogh B H. Deadlock Avoidance in Flexible Manufacturing Systems with Concurrently Competing Process Flows[J], IEEE Trans. on Robotics and Automation, 1990, 6(6): 724-734
85. Barkaoui K, Abdallah I B. Deadlock Avoidance in FMS Based on Structural Theory of Petri Nets[C]. In: Proc. ofEFTA'95, Pads, 499-510
86. Yang, Y. Y., D. A. Linkens. Design of Petri net controllers to exclude forbidden states in manufacturing systems[C]. In pro. Of the 14th world congress of IFAC, Beijing. 1999, 379-384
87. Juan EYT, Tsai JJP, Murata T, Zhou Y. Reduction methods for real-time systems using delay time Petri nets[J], IEEE Transactions on Software Engineering, 2001, 27(5): 422-44888．王寿光，颜钢锋，蒋静坪．网简化技术在Petri网反馈控制器设计中的应用．软件学报[J]，2003，14(6)：1037-1042
89. Zhou M. Reduction of timed marked graphs and its applications to manufacturing systems[C]. In: Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 1994: 801～806 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
90. LEE JK. Reduction rules of Petri nets for verification of the communication protocol[C]. In: Proceedings of the IEEE Singapore International Conference on Information Engineering. 1995: 294～298 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
91. Mugarza JC, Camus H, Gentina JC, Teruel E, Silva M. Reducing the computational complexity of scheduling problems in Petri nets by means of transformation rules[C]. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics. 1998: 19～25 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
92．蔡宗琰．基于赋时可重构Petri网的可重构制造系统建模[J]，航空学报，2004，25(6)：615-618
93．吴维敏．离散事件系统的Petri网控制器综合[D]，浙江：浙江大学，2002．
94．王凌．车间调度及其遗传算法[M]，北京：清华大学出版社，2002
95. Dirk C Mattfeld, Christian Bierwirth. An efficient genetic algorithm for job shop scheduling with tardiness objectives[J], European Journal of Operational Research, 2004, 155: 616-630
96. S. Esquivel, S. Ferrero, et al. Enhanced evolutionary algorithms for single and multi-objective optimization in the job scheduling problem[J], Knowledge-Based Systems, 2003, 15: 13-25
97．吴云高，王万良．基于遗传算法的混合Flowshop调度[J]．计算机工程与应用，2002，12：82-84
98. L. Sousen, H. Shaoting. GA-based resource- constrained flow-shop scheduling model for mixed precast production[J], Automation in Construction, 2002, 11: 439-452
99．李敏强，寇纪淞等．遗传算法的基本理论与应用[M]，科学出版社，2002
100．王凌．智能优化算法及其应用[M]，北京：清华大学出版社，2001101．宋锦河．基于模拟退火算法的生产调度问题[J]，长春工程学院学报(自然科学版)，2004，5(1)：61-63
102. R. W. Cheng, M. Gen, Y. Tsujimura. A tutorial survey of job shop scheduling problems using genetic algorithms-I[J], Computers Industry Engineering, 1996, 130(4): 983-997
103．孙志峻．智能制造系统车间生产优化调度[D]，浙江：浙江工业大学，2002
104. J. Detand, J. P. Kruth, J. Kempenaers. A computer aided process planning system that increases the flexibility of manufacturing[J], IPDES(Espirit project 2590) Workshop, 1992
105. Chunwei Zhao, Zhiming Wu. A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes[J], The International Journal of Flexible Manufacturing Systems, 2001, 13: 71-88
106. Henry W. Thornton, John L. Hunsucker. A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage[J], European Journal of Operational Research, 2004, 152: 96-114
107. I. Sabuncuoglu, A. Comlekci. Operation-based flowtime estimation in a dynamic job shop[J], The International Journal of Management Science, 2002, 30: 423-442
108. Byung Joo Park, Hyung Rim Choi, Hyun Soo Kim. A hybrid genetic algorithm for the job shop scheduling problems[J], Computer & Industrial Engineering, 2003, 45: 597-613
109. Dirk C Mattfeld, Christian Bierwirth. An efficient genetic algorithm for job shop scheduling with tardiness objectives[J], European Journal of Operational Research, 2004, 155: 616-630
110. S. Esquivel, S. Ferrero, et al. Enhanced evolutionary algorithms for single and multi-objective optimization in the job scheduling problem[J], Knowledge-Based Systems, 2003, 15: 13-25
111. Jacek B la zewicz, Erwin Pesch, Ma lgorzata Sterna et al. Open shop scheduling problems with late work criteria[J], Discrete Applied Mathematics, 2004, 134: 1-24
112. Waiman Cheung, Hong Zhou. Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times[J], Annals of Operations Research, 2001, 107: 65-81
113．李言，李淑娟等．工艺设计对生产调度结果的影响[J]，中国机械工程，2000，11(4)：??402-404
114. Y. Seo. Integrated manufacturing systems design through process plan and AGV guide path selection [D], Department of Industrial and Management Systems Engineering, The Pennsylvania State University, 1993
115. Faizul Huq, Kenneth Cutright, Clarence Martin. Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study [J], The International Journal of Management Science, 2004, 32: 121-129
116. J. Fang, Y. G. Xi. A Rolling Horizon Job Shop Rescheduling Strategy in the Dynamic Environment[J], Advanced Manufacturing Technology, 1997,13:227-232
117. L. Monostori, B. Kadar, J. Hornyak. Approaches to Managing Changes and Uncertainties in Manufacturing[J], Annals of the CIRP, 1998,47(1): 365-368
2. K. Steinhofel, A. Albrecht, C.K. Wong. An experimental analysis of local minima to improve neighbourhood search[J], Computers & Operations Research , 2003, 30: 2157 -2173
3. Huang Wenqi, Yin Aihua. An improved shifting bottleneck procedure for the job shop scheduling problem[J], Computers & Operations Research, 2004, 31: 2093 - 2110
4. Masahiro Arakawa, Masahiko Fuyuki, Ichiro Inoue. An optimization-oriented method for simulation -based job shop scheduling incorporating capacity adjustment function[J], Int. J. Production Economics, 2003, 85 :359 - 369
5. Marco Pranzo. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times[J], European Journal of Operational Research , 2004, 153: 581 - 592
6. Gur Mosheiov, Uri Yovel. Comments on "Flow shop and open shop scheduling with a critical machine and two operations per job"[J], European Journal of Operational Research ,2004, 157: 257 - 261
7. M.S. Jayamohan, Chandrasekharan Rajendran. Development and analysis of cost-based dispatching rules for job shop scheduling [J], European Journal of Operational Research,2004, 157 :307 - 321
8. Ruedee Rangsaritratsamee, William G. Ferrell Jr., Mary Beth Kurz. Dynamic rescheduling that simultaneously considers efficiency and stability[J], Computers & Industrial Engineering, 2004, 46 : 1-15
9. Faizul Huq, Kenneth Cutright, Clarence Martin. Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study [J], Omega, 2004, 32: 121 -129
10. K. SteinhoK fel, A. Albrecht, C.K. Wong. Fast parallel heuristics for the job shop scheduling problem[J], Computers & Operations Research, 2002, 29:151-169.
11. Samir Allet. Handling flexibility in a "generalised job shop" with a fuzzy approach[J],??European Journal of Operational Research, 2003, 147 :312 - 333
12. Gerhard J. Woeginger. Inapproximability results for no-wait job shop scheduling[J], Operations Research Letters, 2004, 32: 320 - 325
13. Alessandro Mascis, Dario Pacciarelli. Job-shop scheduling with blocking and no-wait constraints [J], European Journal of Operational Research, 2002,143: 498 - 517
14. S.H. Yoon, J. A.Ventura. Minimizing the mean weighted absolute deviation from due dates in lot-streaming flow shop scheduling [J], Computers & Operations Research , 2002,29:1301-1315
15. Volker Lau, Frank Werner. On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties [J], Computers & Operations Research, 2004, 31 : 317-345
16. I. Sabuncuoglu, A. Comlekci. Operation-based flowtime estimation in a dynamic job shop[J], Omega, 2002, 30: 423 - 442
17. R.M. Aiex , S. Binatob, M.G.C. Resende. Parallel GRASP with path-relinking for job shop scheduling [J], Parallel Computing , 2003, 29: 393 - 430
18. Yazid Mati, Xiaolan Xie, The complexity of two-job shop problems with multi-purpose unrelated machines[J], European Journal of Operational Research , 2004, 152 : 159 -169
19. K. Steinhofel, A. Albrecht, C.K. Wong. The convergence of stochastic algorithms solving flow shop scheduling[J], Theoretical Computer Science, 2002, 285: 101 - 117
20. Ching-Fang Liaw, Chun-Yuan Cheng, Mingchih Chen, The total completion time open shop scheduling problem with a given sequence of jobs on one machine [J], Computers & Operations Research, 2002, 29:1251-1266
21. Berkin Toktas, Meral Azizoglub, Suna Kondakci Koksalan. Two-machine flow shop scheduling with two criteria: Maximum earliness and makespan [J], European Journal of Operational Research, 2004, 157 : 286 - 295
22. BEATRICE M. OMBUKI, MARIO VENTRESCA. Local Search Genetic Algorithms for the Job Shop Scheduling Problem[J], Applied Intelligence, 2004,21:99-109
23. IBRAHIM KATTAN. Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods[J], Journal of Intelligent Manufacturing, 2003, 14:107-121
24. ROGER Z. R'IOS-MERCADO, JONATHAN F. BARD. The Flow Shop Scheduling??Polyhedron with Setup Times[J], Journal of Combinatorial Optimization, 2003, 7: 291-318
25. STEPHEN OMAN, PADRAIG CUNNINGHAM. Using case retrieval to seed genetic algorithms[J], International Journal of Computational Intelligence and Applications, 2001, 1, (1): 71-82
26．吴云高，王万良．基于遗传算法的车间调度方法及其应用[D]，浙江：浙江工业大学，2002
27. Davis W, Jones A. A real-time Production scheduler for a stochastic manufacturing environment [J], International Journal of Computer Integrated Manufacturing, 1988, 1(2): 101-112
28. Gershwin S. Hierarchical flow control: a framework for scheduling and Planning discrete events in manufacturing systems[C]. Proceedings of IEEE Special Issue on Discrete Event Systems, 1989, 77: 195-209
29. Lun P B, Hoitomt F J, Max E. Scheduling generation and reconfiguration for Parallel machines[J], IEEE Transactions of Robotics and Automation, 1990, 6(6): 687-696
30. Chen H X, Cheng B C, Proth J M. A more efficient Lagrangian relaxation approach to job shop scheduling Problems[C]. Proceeds of IEEE International Conference on Robotics and Automation, Japan, 1995, 496-501
31. Fox M. Constraint-Directed Search: A case study of Job Shop Scheduling[D], Carnegie-Mellon University, 1983
32. Wysk R, Wu D, Yang R. A multi-pass expert control system(MPECS) for flexible manufacturing systems[J], NBS Special Publication, 1986, 724: 251-278
33. Zweben M, Fox M, San Francisco. OPIS: A methodology and architecture for reactive scheduling, Intelligent Scheduling[M], California: Morgan Kaufman, 1995, 29-66
34. Zweben M, Fox M, San Francisco. Scheduling as intelligent control of decision-making and constraint Propagation, Intelligent Scheduling[M], California: Morgan Kaufman, 1995, California: Morgan Kaufman, 1995, 67-98
35. Parunak H, Irish B, Kindrick J et al. Fractal actors for distributed manufacturing control[C]. Proceedings of the Second IEEE Conference on Artificial Intelligence Applications, 1985, 653-660
36. Daouas T, Ghedira K, Muller J. Distributed flow shop scheduling Problem versus local??optimization[C]. Proceedings of the First International Conference on Multi-Agent Systems, Cambridge, Massachusetts: MIT Press, 1995
37．饶运清，谢畅，李淑霞．基于多Agent的Job Shop调度方法研究[J]，中国机械工程，2004，15(10)：873-877
38．王太江，王时龙，龙雪峰．基于移动AGENT的敏捷车间调度控制系统建模[J]，机电一体化，2004，2：26-29
39. Rabelo L, Sahinoglu M, Avula X. Flexible manufacturing systems scheduling using QLearning[C]. Proceedings of. the World Congress on Neural Networks, San Diego, California: 1994, 1378-1385
40. Foo Y, Takefuji Y. Stochastic neural networks for solving job-shop scheduling: Part 2 Architecture and simulations[C]. Proceedings of the IEEE International Conference on Neural Networks, IEEE TAB 1988: 11283-11290
41. Zhou D, Cherkassky V, Baldwin T et al. Scaling neural networks for job shop scheduling[C], Proceedings of the International Conference on Neural Networks, 1990, 3: 889-894
42. Taillard E, Some efficient heuristic methods for the flow shop sequencing Problem[J], European Operation Research, 1990, 47(1): 65-74
43. Manuel L, Bames J W, Glover F. Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times[J], Applied Intelligence, 1993(3): 159-172
44．姜思杰，张付亮．基于遗传和禁忌算法求解一类车间调度问题，计算机集成制造系统—CIMS[J]，2003，9(11)：984-988
45. R. S. CINTIA, A. A. VINICIUS, L. MANUEL. Tardiness minimization in a flexible job shop: A tabu search approach[J], Journal of Intelligent Manufacturing, 2004, 15: 103-115
46. Vakharia A, Cheng Y. A simulated annealing approach to scheduling a manufacturing cell[J], Naval Research Logistics, 1990, 37: 559-577
47. Jeffcoat D, Bulfln R. Simulated annealing for resource-constrained scheduling[J], European Journal of Operational Research, 1993, 70: 43-51
48. A. M. EMIN, F. TERENCEC.. A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimization Problems[J], Journal of Heuristics, 2004, 10:??269-292
49. L.Chinyao, Y.Y.Jinn, I.H.Kai. A robust siulated annealing heuristic for flow shop scheduling problems[J],Int JAdv Manuf Technol, 2004,23:762-767
50. Slany W. Scheduling as a fuzzy multiple criteria optimization problem, CD-Technical Report, 1994, 94/62, Technical University of Vienna
51. Grabot B, Geneste L. Dispatching rules in scheduling: a fuzzy approach[J], International Journal of Production Research, 1994,32(4): 903-915
52. Tsujimura Y, Park S, Chang S et al. An effective method for solving flow shop scheduling problems with fuzzy processing times [J], Computers and Industrial Engineering, 1993,25:239-242
53. Kenneth N M, Vincent C S W. Unifying the theory and practice of production scheduling[J], Journal of Manufacturing Systems, 1999,18(4): 241-255
54. Sergio Cavalieri, Paolo Gaiardelli. Hybrid genetic algorithms for a multiple- objective scheduling problem[J], Journal of Intelligent Manufacturing, 1998, 9: 361-367
55. C. W. Zhao, Z. M.Wu. A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes[J], Journal of Heuristics, 2004,10:269-292
56. H. Z. Jia, A. Y. C. Nee et al. A modified genetic algorithm for distributed scheduling problems [J], Journal of Intelligent Manufacturing ,2003, 14:351-362
57. L. X. Tang, J. Y. Liu. A modified genetic algorithm for the flow shop sequencing problem to minimize mean flow time [J], Journal of Intelligent Manufacturing, 2002, 13:61-67
58. C. George, S. Velusamy. Dynamic scheduling of manufacturing job shops using genetic algorithms [J], Journal of Intelligent Manufacturing, 2001,12:281-293
59. W. M. Cheung, H. Zhou. Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times[J], Annals of Operations Research, 2001, 107:65-81
60. C. Oguz, Y.F. Fung et al. Parallel genetic algorithm for a flow shop problem with multiprocessor tasks[J], ICCS 2003, LNCS 2659, 2003,548-559
61. J. G. Qi, G. R. Bruns, D. K. Harrison. The application of parallel multipopulation genetic algorithms to dynamic job shop scheduling[J], The International Journal of Advanced Manufacturing Technology,2000,16:609-61562. L. Wang, L. Zhang, D. Z. Zheng. The ordinal optimization of genetic control parameters for flow shop scheduling[J], The International Journal of Advanced Manufacturing Technology, 2004, 23: 812-819
63. J. H. Chen, L. C. Fu, M. H. Lin, et al. Petri-net and GA based approach to modeling, scheduling, and performance evaluation for wafer fabrication[J], IEEE Transaction on Robotics and Automation, 2001, 17(5): 619-636
64．王笑蓉，吴铁军．基于Petri网仿真的柔性生产调度-蚁群-遗传递阶进化优化方法[J]，浙江大学学报(工学版)，2004，38(3)：286-291
65．郑锋，孙树栋，吴秀丽．基于遗传算法和模型仿真的调度规则决策方法[J]，计算机集成制造系统，2004，10(7)：808-814
66．蔡宗琰，王宁生等．基于赋时可重构Petri网的可重构制造系统调度算法[J]，西南交通大学学报，2004，39(3)：341-344
67. K. Ibrahim, M. Boleslaw, K. Khalid et al. Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods[J], Journal of Intelligent Manufacturing, 2003, 14: 107-12
68．熊惠明，徐国华．用Petri网实现FMS负载平衡调度[J]，现代生产与管理技术，成组技术与生产现代化，2004，21(1)：28-31
69．张建朝，刘振娟，李宏光．Petri网图形建模仿真系统的研究与开发[J]，北京化工大学学报，2004，31(2)：100-103
70．韩耀军，蒋昌俊，罗雪梅．基于Petri网合成与化简的分布式数据库系统并发控制的死锁检测[J]，小型微型计算机系统，2004，25(5)：821-826
71．郭彩芬，王宁生．串行生产线生产与库存的最优控制[J]，中国机械工程，2004，15(10)：891-894
72. H. X. Chen. Control synthesis of Petri nets based on S-Decreases[J], Discrete Event Dynamic Systems: Theory and Application, 2000, 10: 233-249
73. M. Ohbayashi, K. Hirasawa, et al. Nonlinear control system using learning Petri network[J], Electrical Engineering in Japan, 2000, 131(3): 58-69
74. S. BULACH, A. BRAUCHLE. Design and implementation of discrete event control systems: A Petri net based hardware approach[J], Discrete Event Dynamic Systems: Theory and Application, 2002, 12: 287-309
75. Yasutaka, Fujimoto. Design of discrete time polynomial nonlinear systems and its??application to sequential control[J], Electrical Engineering in Japan, 2004, 149(2): 60-72
76. N. A. Anisimov, E. A. Golenkov, D. I. Kharitonov. Compositional Petri net approach to the development of concurrent and distributed systems[J], Programming and Computer Software, 2001, 27(6): 309-319
77. K. JAN. Input-output relation and time-optimal control of a class of hybrid Petri nets using semiring[J], Discrete Event Dynamic Systems: Theory and Application, 2001, 11: 59-75
78. D. A. Zaitsev. Invadants of timed Petri nets[J], Cybernetics and Systems Analysis, 2004, 40(2): 226-237
79．江志斌．Petri网及其在制造系统建模与控制中的应用[M]，北京：机械工业出版社，2004
80. Holloway LE, Krogh BH. Synthesis of feedback logic for a class of controlled Petri nets[J], IEEE T-AC, 1990, 35(5): 514～523
81. Li Y, Wonham WM. Control of vector discrete-event systems Ⅰ——The base model[J], IEEE T-AC, 1993, 38(8): 1214～1227
82. Li Y, Wonham WM. Control of vector discrete-event systems Ⅱ——The base mode[J], IEEE T-AC, 1994, 39(3): 512～531
83. Yamalidou K, Moody JO, Lemmon MD, Antsaldis PJ. Feedback control of Petri nets based on place invadants[J], Automatica, 1996, 32(1): 15-28
84. Banaszak Z A, Krogh B H. Deadlock Avoidance in Flexible Manufacturing Systems with Concurrently Competing Process Flows[J], IEEE Trans. on Robotics and Automation, 1990, 6(6): 724-734
85. Barkaoui K, Abdallah I B. Deadlock Avoidance in FMS Based on Structural Theory of Petri Nets[C]. In: Proc. ofEFTA'95, Pads, 499-510
86. Yang, Y. Y., D. A. Linkens. Design of Petri net controllers to exclude forbidden states in manufacturing systems[C]. In pro. Of the 14th world congress of IFAC, Beijing. 1999, 379-384
87. Juan EYT, Tsai JJP, Murata T, Zhou Y. Reduction methods for real-time systems using delay time Petri nets[J], IEEE Transactions on Software Engineering, 2001, 27(5): 422-44888．王寿光，颜钢锋，蒋静坪．网简化技术在Petri网反馈控制器设计中的应用．软件学报[J]，2003，14(6)：1037-1042
89. Zhou M. Reduction of timed marked graphs and its applications to manufacturing systems[C]. In: Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 1994: 801～806 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
90. LEE JK. Reduction rules of Petri nets for verification of the communication protocol[C]. In: Proceedings of the IEEE Singapore International Conference on Information Engineering. 1995: 294～298 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
91. Mugarza JC, Camus H, Gentina JC, Teruel E, Silva M. Reducing the computational complexity of scheduling problems in Petri nets by means of transformation rules[C]. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics. 1998: 19～25 http://intl.ieeexplore.ieee.org/Xplore/DynWel.isp.
92．蔡宗琰．基于赋时可重构Petri网的可重构制造系统建模[J]，航空学报，2004，25(6)：615-618
93．吴维敏．离散事件系统的Petri网控制器综合[D]，浙江：浙江大学，2002．
94．王凌．车间调度及其遗传算法[M]，北京：清华大学出版社，2002
95. Dirk C Mattfeld, Christian Bierwirth. An efficient genetic algorithm for job shop scheduling with tardiness objectives[J], European Journal of Operational Research, 2004, 155: 616-630
96. S. Esquivel, S. Ferrero, et al. Enhanced evolutionary algorithms for single and multi-objective optimization in the job scheduling problem[J], Knowledge-Based Systems, 2003, 15: 13-25
97．吴云高，王万良．基于遗传算法的混合Flowshop调度[J]．计算机工程与应用，2002，12：82-84
98. L. Sousen, H. Shaoting. GA-based resource- constrained flow-shop scheduling model for mixed precast production[J], Automation in Construction, 2002, 11: 439-452
99．李敏强，寇纪淞等．遗传算法的基本理论与应用[M]，科学出版社，2002
100．王凌．智能优化算法及其应用[M]，北京：清华大学出版社，2001101．宋锦河．基于模拟退火算法的生产调度问题[J]，长春工程学院学报(自然科学版)，2004，5(1)：61-63
102. R. W. Cheng, M. Gen, Y. Tsujimura. A tutorial survey of job shop scheduling problems using genetic algorithms-I[J], Computers Industry Engineering, 1996, 130(4): 983-997
103．孙志峻．智能制造系统车间生产优化调度[D]，浙江：浙江工业大学，2002
104. J. Detand, J. P. Kruth, J. Kempenaers. A computer aided process planning system that increases the flexibility of manufacturing[J], IPDES(Espirit project 2590) Workshop, 1992
105. Chunwei Zhao, Zhiming Wu. A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes[J], The International Journal of Flexible Manufacturing Systems, 2001, 13: 71-88
106. Henry W. Thornton, John L. Hunsucker. A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage[J], European Journal of Operational Research, 2004, 152: 96-114
107. I. Sabuncuoglu, A. Comlekci. Operation-based flowtime estimation in a dynamic job shop[J], The International Journal of Management Science, 2002, 30: 423-442
108. Byung Joo Park, Hyung Rim Choi, Hyun Soo Kim. A hybrid genetic algorithm for the job shop scheduling problems[J], Computer & Industrial Engineering, 2003, 45: 597-613
109. Dirk C Mattfeld, Christian Bierwirth. An efficient genetic algorithm for job shop scheduling with tardiness objectives[J], European Journal of Operational Research, 2004, 155: 616-630
110. S. Esquivel, S. Ferrero, et al. Enhanced evolutionary algorithms for single and multi-objective optimization in the job scheduling problem[J], Knowledge-Based Systems, 2003, 15: 13-25
111. Jacek B la zewicz, Erwin Pesch, Ma lgorzata Sterna et al. Open shop scheduling problems with late work criteria[J], Discrete Applied Mathematics, 2004, 134: 1-24
112. Waiman Cheung, Hong Zhou. Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times[J], Annals of Operations Research, 2001, 107: 65-81
113．李言，李淑娟等．工艺设计对生产调度结果的影响[J]，中国机械工程，2000，11(4)：??402-404
114. Y. Seo. Integrated manufacturing systems design through process plan and AGV guide path selection [D], Department of Industrial and Management Systems Engineering, The Pennsylvania State University, 1993
115. Faizul Huq, Kenneth Cutright, Clarence Martin. Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study [J], The International Journal of Management Science, 2004, 32: 121-129
116. J. Fang, Y. G. Xi. A Rolling Horizon Job Shop Rescheduling Strategy in the Dynamic Environment[J], Advanced Manufacturing Technology, 1997,13:227-232
117. L. Monostori, B. Kadar, J. Hornyak. Approaches to Managing Changes and Uncertainties in Manufacturing[J], Annals of the CIRP, 1998,47(1): 365-368