面向快速制造的车间调度策略研究
|
摘要
车间资源的有限性制约着生产任务的完成，能否有效利用车间现有资源完成生产任务，以最快的速度响应市场需求，已经成为决定制造型企业能否赢得市场竞争的关键。因此，车间调度策略一直是制造业研究的热点。但是，资源约束和工艺约束的并存，使得车间调度成为一类NP-hard问题。同时，实际车间中的各种动态事件难以预测，以致车间调度问题异常复杂，迄今为止还没有一种通用有效的调度策略。
本文针对牵拉(Pull)型市场环境的特点，将遗传算法与多代理思想相结合，提出一种基于多代理系统(Multi-Agent System，MAS)和遗传算法(Genetic Algorithm，GA)的动态车间调度模型，并据此构建了一个实用且适应性广的动态车间调度原型系统。首先，本文介绍了车间调度的背景、类型和研究发展状况，并分析了GA和MAS在解决JSSP这类NP-Hard问题方面的前景。接着本文详细探讨了将GA运用在车间调度问题(Job Shop Scheduling Problem，JSSP)中的关键技术，同时对比了二／十进制编码方案的性能。特别地，在将GA应用于JSSP的过程中，死锁问题是讨论的重点，死锁的消除是用GA解决JSSP的前提。针对GA收敛速度较低的情况，文中提出了几种改进方法，使调度系统具有较高的收敛速度，并有柔性路径选择功能。在GA提供了求解JSSP的有效支持的基础上，本文引入多代理思想管理车间生产动态过程，以将动态JSSP分解为一系列静态JSSP，从而能通过GA方法求解。最后，大量的仿真实验证明了基于MAS和GA的车间调度系统在实际应用中的前景。
The insufficience of resources in the shopfloor holds back the accomplishment of production plans. In a sense, whether the enterprise can survive market competition is determined by whether it can meet customers' demands in time, which is further determined by how efficiently the limited resources are used. Consequently, extensive researches have been carried out concerning scheduling methods for shopfloor since scheduling methods help make best use of resources.
In real shopfloor scheduling scenarios, resource restriction coexists with process restriction, which makes shopfloor scheduling problems NP-hard. Meanwhile, the changeability of market demand together with the uncertainty in a real job shop adds to the complexity of JSSP. As a result, there exist no effective and widely applicable job shop scheduling methods.
This paper puts forward a MAS-GA based dynamic job-shop scheduling model. Our scheme combines the advantages of GA and MAS, taking into consideration the characteristics of the PULL Pattern market. Based on the model, we implemented an effective and widely applicable prototype system for dynamic JSSPs.
The first part of the paper introduces the background, the categories and the development of job shop scheduling. Meanwhile, the promising aspects of GA and MAS for solving NP-Hard problems are highlighted. The second chapter analyses in detail how to adapt GA for JSSP, and compares the performances of the GA in binary coding and decimal coding. Also, we put special emphasis on deadlock problems since deadlock is a big obstacle to GA-based JSSP solutions. Considering GA converges slowly, special adaptations are made to the GA constructed in the second chapter. The new GA converges much more quickly and can find the most suitable route for an operation. The fourth chapter introduces MAS mechanism to construct a dynamic job-shop scheduling system, with GA providing basic support. MAS mechanism decomposes a continuous and dynamic job-shop scheduling problem into series of JSSPs so that the predefined GA can work out the schedule. Finally, the results from simulation shows the MAS-GA based scheduling system is promising for practical job-shop scheduling.
本文针对牵拉(Pull)型市场环境的特点，将遗传算法与多代理思想相结合，提出一种基于多代理系统(Multi-Agent System，MAS)和遗传算法(Genetic Algorithm，GA)的动态车间调度模型，并据此构建了一个实用且适应性广的动态车间调度原型系统。首先，本文介绍了车间调度的背景、类型和研究发展状况，并分析了GA和MAS在解决JSSP这类NP-Hard问题方面的前景。接着本文详细探讨了将GA运用在车间调度问题(Job Shop Scheduling Problem，JSSP)中的关键技术，同时对比了二／十进制编码方案的性能。特别地，在将GA应用于JSSP的过程中，死锁问题是讨论的重点，死锁的消除是用GA解决JSSP的前提。针对GA收敛速度较低的情况，文中提出了几种改进方法，使调度系统具有较高的收敛速度，并有柔性路径选择功能。在GA提供了求解JSSP的有效支持的基础上，本文引入多代理思想管理车间生产动态过程，以将动态JSSP分解为一系列静态JSSP，从而能通过GA方法求解。最后，大量的仿真实验证明了基于MAS和GA的车间调度系统在实际应用中的前景。
The insufficience of resources in the shopfloor holds back the accomplishment of production plans. In a sense, whether the enterprise can survive market competition is determined by whether it can meet customers' demands in time, which is further determined by how efficiently the limited resources are used. Consequently, extensive researches have been carried out concerning scheduling methods for shopfloor since scheduling methods help make best use of resources.
In real shopfloor scheduling scenarios, resource restriction coexists with process restriction, which makes shopfloor scheduling problems NP-hard. Meanwhile, the changeability of market demand together with the uncertainty in a real job shop adds to the complexity of JSSP. As a result, there exist no effective and widely applicable job shop scheduling methods.
This paper puts forward a MAS-GA based dynamic job-shop scheduling model. Our scheme combines the advantages of GA and MAS, taking into consideration the characteristics of the PULL Pattern market. Based on the model, we implemented an effective and widely applicable prototype system for dynamic JSSPs.
The first part of the paper introduces the background, the categories and the development of job shop scheduling. Meanwhile, the promising aspects of GA and MAS for solving NP-Hard problems are highlighted. The second chapter analyses in detail how to adapt GA for JSSP, and compares the performances of the GA in binary coding and decimal coding. Also, we put special emphasis on deadlock problems since deadlock is a big obstacle to GA-based JSSP solutions. Considering GA converges slowly, special adaptations are made to the GA constructed in the second chapter. The new GA converges much more quickly and can find the most suitable route for an operation. The fourth chapter introduces MAS mechanism to construct a dynamic job-shop scheduling system, with GA providing basic support. MAS mechanism decomposes a continuous and dynamic job-shop scheduling problem into series of JSSPs so that the predefined GA can work out the schedule. Finally, the results from simulation shows the MAS-GA based scheduling system is promising for practical job-shop scheduling.
引文
[1] L.Beril Toktay,Two Topics in Supply Chain Management,Operations Research Center,1998．
[2] 张军强，有了ERP还需不需要SCM，CAD/CAM与制造业信息化，http://www.e-works.net.cn/,2003-3-4
[3] MESA (1994): The Benefits of MES: A Report from the Field, MESA International,1994, www.mesa.org
[4] MESA (1996): MES Software Evaluation/Selection, MESA International,http://www.mesa.org./
[5] MESA (1997): MES Explained: A High Level Vision, MESA International, http://www.mesa.org./
[6] 陈国良，王煦法等，遗传算法及其应用，人民邮电出版社(第1版)，1996，PP：1～10，pp：358～359
[7] Nicolas Beldiceanu, Mats Carlsson, A new multi-resource cumulatives constraint with negative heights, Technical Report T2001-11,2001.
[8] T. Gonzalez and S. Sahni, Flowshop and jobshop schedules: complexity and approximation, Operations Research, 1978(26): 36-52
[9] S. Arora, The approximability of NP-hard problems, Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, ACM, 1998, pp: 337-348
[10] M.Garey, D.Johnson, Strong NP-completeness results: motivation, examples and implications, Journal of the ACM, 1978(25): 499-508
[11] 张颖，刘艳秋等，软计算方法(第1版)，科学出版社，2002，PP：109
[12] L. Davis, Job-shop scheduling with genetic algorithm, Proc..Of the 1st Int. Conf. On Genetic Algorithms, Lawrence Erlbaum Associates, 1985, pp.136-140
[13] J.F Muth & G.L Thompson (1963),Industrial Scheduling, New Jersey, Prentice Hall, 1963
[14] H. V. D. Parunak, Applications of distributed artificial intelligence in industry,Foundations of Distributed Artificial Intelligence, G. M. P. O. Hare and N. R. Jennings, 1996, pp: 71-76
[15] 严隽琪，FMS调度研究的现状与发展，上海交通大学学报，1998，32(5)：124-127
[16] Ono, I., Yamamura, M., Kobayashi, A Genetic Algorithm for Job-shop Scheduling Problems Using Job-based Order Crossover, Proc. of ICEC'96, 1996, pp: 547-552
[17] R. Cheng and M. Gen, A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅱ: hybrid genetic search strategies, Computers & Industrial Engineering, 1999(36): 343-364
[18] Nakono R, Yamada T., Conventional Genetic Algorithm for Job Shop Problems, Proc
of 4th Int Conf on Genetic Algorithms and Their Applications, 1991,pp: 474～479
[19] M. Grey and D. Johnson, Strong NP-completeness results: motivation, examples and implications, Journal of ACM, 1978(25): 499-508
[20] 熊光楞，龚宇，具有机器学习能力的智能车间调度系统[J]．计算机集成制造系统，1996，4(2)：34～40
[21] R.J.M. Vaessens, E.H.L Aarts, and J.K. Lenstra, Job Shop Scheduling by local Search, NFORMS Journal on Computing, 1996(8):302-317
[22] J.P. Watson, A.E. Howe, and L.D. Whitley, An Analysis of Iterated Local Search for Job-Shop Scheduling, Proceedings of the Fifth Metaheuristics International Conference, 2003
[23] R. Cheng and M. Gen, A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation, Computers Industrial Engineering, 1996, 30(4): 983-997
[24] Ozsu.M.Tamer, Patrick Valdurez, Principles of distributed database systems, Prentice Hall, Inc.Upper Saddle River, New Jersey, 1991, pp:335～342, pp: 300～306
[25] Takeshi Yamada and Ryohei Nakano, Job-shop scheduling (Chapter 7), IEE control engineering series 55, 1997, pp: 134-160
[26] 李秀，集成环境下连续式生产模式车间管理控制器的研究，南京航空航天大学博士论文，2000，pp：55-63
[27] W.RM. Nuijten and E.H.L. Aarts, A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling, European Journal of Operational Research, 1996, 90(2): 269-284
[28] Nakono R, Yamada T., Conventional Genetic Algorithm for Job Shop Problems, Proc of 4th International Conference on Genetic Algorithms and Their Applications, 1991, pp: 474～479
[29] 孙志峻，乔冰，潘全科等，具有柔性加工路径的作业车间批量调度优化研究，机械科学与技术，2002
[30] Katia P.Sycara, Multiagent System, AI magazine, 1998, 19(2)
[31] Wooldridge, M.J., and Jennings, N.R, Agent Theories, Architectures and Languages: A Survey, Intelligent Agents-Theories, Architectures, and Languages I, Springer-Verlag Lecture Notes in AI, 1995, Vo.890
[32] D. L. Martin, A. J. Cheyer, and D. B. Moran, The open agent architecture: A framework for building distributed software systems, Applied Artificial Intelligence, 1999, 13(1-2): 91-128
[33] Jose M. Vidal, Paul Buhler, A Generic Agent Architecture for Multiagent Systems (2001),http://jmvidal.cse.sc.edu/papers/vidaltr0211.pdf
[34] 胡舜耕，张莉，钟守义，多Agent系统的理论、技术及其运用[J]，计算机科学，1999，26(9)：20-24
[35] K. Fisher, B. Chaib-draa et al, A simulation approach based on negotiation and
cooperation between Agents: a case study[J], IEEE Transactions on Systems, Man and Cybernetics, 1999,29(4):531-544
[36] R.Miraftabi, Agents on the Loose: An overview of agent technologies (2000), http://citeseer. ist.psu.edu/miraftabi00agents.html
[37] Kap Huan Kim, et al. A Distributed Scheduling and Shop Floor Control Method[J],Computer and Industrial Engineering, 1996,31 (3/4):583～586
[38] Kouiss K, et al, Using Multi-Agent Architecture in FMS for Dynamic Scheduling[J],Journal of Intelligent manufacturing,1997(8):41-47
[39] Lee, K. J., Chang, Y. S., and Lee, J. K., Time-Bound Negotiation Framework for Electronic Commerce Agents, Decision Support Systems, 2000(28):319-331
[40] 王正志，薄涛，进化计算(第1版)，国防科技大学出版社，2000，pp：99-101
[41] Christian Bierwirth, A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spektrum, 1995
[42] C. Bierwirth, A generalized permutation approach to job-shop scheduling with genetic algorithms, OR SPEKTRUM, 1995,17(2-3): 87-92
[43] Takeshi Yamada and Ryohei Nakano, Proceedings of Modern Heuristic for Decision Support, UNICOM seminar, London, 1997, pp: 67-81
[2] 张军强，有了ERP还需不需要SCM，CAD/CAM与制造业信息化，http://www.e-works.net.cn/,2003-3-4
[3] MESA (1994): The Benefits of MES: A Report from the Field, MESA International,1994, www.mesa.org
[4] MESA (1996): MES Software Evaluation/Selection, MESA International,http://www.mesa.org./
[5] MESA (1997): MES Explained: A High Level Vision, MESA International, http://www.mesa.org./
[6] 陈国良，王煦法等，遗传算法及其应用，人民邮电出版社(第1版)，1996，PP：1～10，pp：358～359
[7] Nicolas Beldiceanu, Mats Carlsson, A new multi-resource cumulatives constraint with negative heights, Technical Report T2001-11,2001.
[8] T. Gonzalez and S. Sahni, Flowshop and jobshop schedules: complexity and approximation, Operations Research, 1978(26): 36-52
[9] S. Arora, The approximability of NP-hard problems, Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, ACM, 1998, pp: 337-348
[10] M.Garey, D.Johnson, Strong NP-completeness results: motivation, examples and implications, Journal of the ACM, 1978(25): 499-508
[11] 张颖，刘艳秋等，软计算方法(第1版)，科学出版社，2002，PP：109
[12] L. Davis, Job-shop scheduling with genetic algorithm, Proc..Of the 1st Int. Conf. On Genetic Algorithms, Lawrence Erlbaum Associates, 1985, pp.136-140
[13] J.F Muth & G.L Thompson (1963),Industrial Scheduling, New Jersey, Prentice Hall, 1963
[14] H. V. D. Parunak, Applications of distributed artificial intelligence in industry,Foundations of Distributed Artificial Intelligence, G. M. P. O. Hare and N. R. Jennings, 1996, pp: 71-76
[15] 严隽琪，FMS调度研究的现状与发展，上海交通大学学报，1998，32(5)：124-127
[16] Ono, I., Yamamura, M., Kobayashi, A Genetic Algorithm for Job-shop Scheduling Problems Using Job-based Order Crossover, Proc. of ICEC'96, 1996, pp: 547-552
[17] R. Cheng and M. Gen, A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅱ: hybrid genetic search strategies, Computers & Industrial Engineering, 1999(36): 343-364
[18] Nakono R, Yamada T., Conventional Genetic Algorithm for Job Shop Problems, Proc
of 4th Int Conf on Genetic Algorithms and Their Applications, 1991,pp: 474～479
[19] M. Grey and D. Johnson, Strong NP-completeness results: motivation, examples and implications, Journal of ACM, 1978(25): 499-508
[20] 熊光楞，龚宇，具有机器学习能力的智能车间调度系统[J]．计算机集成制造系统，1996，4(2)：34～40
[21] R.J.M. Vaessens, E.H.L Aarts, and J.K. Lenstra, Job Shop Scheduling by local Search, NFORMS Journal on Computing, 1996(8):302-317
[22] J.P. Watson, A.E. Howe, and L.D. Whitley, An Analysis of Iterated Local Search for Job-Shop Scheduling, Proceedings of the Fifth Metaheuristics International Conference, 2003
[23] R. Cheng and M. Gen, A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation, Computers Industrial Engineering, 1996, 30(4): 983-997
[24] Ozsu.M.Tamer, Patrick Valdurez, Principles of distributed database systems, Prentice Hall, Inc.Upper Saddle River, New Jersey, 1991, pp:335～342, pp: 300～306
[25] Takeshi Yamada and Ryohei Nakano, Job-shop scheduling (Chapter 7), IEE control engineering series 55, 1997, pp: 134-160
[26] 李秀，集成环境下连续式生产模式车间管理控制器的研究，南京航空航天大学博士论文，2000，pp：55-63
[27] W.RM. Nuijten and E.H.L. Aarts, A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling, European Journal of Operational Research, 1996, 90(2): 269-284
[28] Nakono R, Yamada T., Conventional Genetic Algorithm for Job Shop Problems, Proc of 4th International Conference on Genetic Algorithms and Their Applications, 1991, pp: 474～479
[29] 孙志峻，乔冰，潘全科等，具有柔性加工路径的作业车间批量调度优化研究，机械科学与技术，2002
[30] Katia P.Sycara, Multiagent System, AI magazine, 1998, 19(2)
[31] Wooldridge, M.J., and Jennings, N.R, Agent Theories, Architectures and Languages: A Survey, Intelligent Agents-Theories, Architectures, and Languages I, Springer-Verlag Lecture Notes in AI, 1995, Vo.890
[32] D. L. Martin, A. J. Cheyer, and D. B. Moran, The open agent architecture: A framework for building distributed software systems, Applied Artificial Intelligence, 1999, 13(1-2): 91-128
[33] Jose M. Vidal, Paul Buhler, A Generic Agent Architecture for Multiagent Systems (2001),http://jmvidal.cse.sc.edu/papers/vidaltr0211.pdf
[34] 胡舜耕，张莉，钟守义，多Agent系统的理论、技术及其运用[J]，计算机科学，1999，26(9)：20-24
[35] K. Fisher, B. Chaib-draa et al, A simulation approach based on negotiation and
cooperation between Agents: a case study[J], IEEE Transactions on Systems, Man and Cybernetics, 1999,29(4):531-544
[36] R.Miraftabi, Agents on the Loose: An overview of agent technologies (2000), http://citeseer. ist.psu.edu/miraftabi00agents.html
[37] Kap Huan Kim, et al. A Distributed Scheduling and Shop Floor Control Method[J],Computer and Industrial Engineering, 1996,31 (3/4):583～586
[38] Kouiss K, et al, Using Multi-Agent Architecture in FMS for Dynamic Scheduling[J],Journal of Intelligent manufacturing,1997(8):41-47
[39] Lee, K. J., Chang, Y. S., and Lee, J. K., Time-Bound Negotiation Framework for Electronic Commerce Agents, Decision Support Systems, 2000(28):319-331
[40] 王正志，薄涛，进化计算(第1版)，国防科技大学出版社，2000，pp：99-101
[41] Christian Bierwirth, A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spektrum, 1995
[42] C. Bierwirth, A generalized permutation approach to job-shop scheduling with genetic algorithms, OR SPEKTRUM, 1995,17(2-3): 87-92
[43] Takeshi Yamada and Ryohei Nakano, Proceedings of Modern Heuristic for Decision Support, UNICOM seminar, London, 1997, pp: 67-81