实际生产系统中考虑任务相关性的作业计划规则调度算法研究与实现
|
摘要
Job-Shop调度问题是产品制造业中共存的问题，它是实际生产调度问题的高度简化。解决好这一问题，是有效利用企业现有的资源、合理制定企业和车间生产计划、保证按时交货、提高企业信誉、贏得更多的客户，使企业在竞争中得以生存的关键。Job-Shop调度问题属于一种难解的组合优化问题，人们为了解决这一难题已经付出了几十年的努力，取得了相当大的成果，但要彻底解决这一难题还需要作大量的工作。本文对这一领域的若干问题进行了较为深入的研究，取得了一些有益的成果。具体工作如下：
1)给出了单件车间调度问题的定义，分析了单件车间作业调度研究的特点及意义，回顾了研究求解单件车间作业调度问题的主要历程及其方法。
2)将项目管理中的相关性概念应用到单件车间的生产调度中。在以前的作业计划中，只考虑同一零件的各道工序之间的完成—开始相关，这显然不能完整准确地反映机械制造企业生产系统的实际情况，得出的作业计划也自然缺乏可行性。实际的机械生产系统可能存在着完成—开始(FS)、完成—完成(FF)、开始—开始(SS)、开始—完成(SF)四种类型。在本文中将上述的四种相关性均引入作业计划算法中加于考虑，从而完整地定义和反映了实际生产系统的各种加工技术约束，保证作业计划的可行性。
3)在综合分析和研究相关文献的基础上，针对实际生产系统的特点、对作业计划的要求及对算法时间复杂度与空间复杂度的考虑，本文采用了优先调度规则算法来求解作业计划问题。由于优先调度规则具有较强的问题依赖性，即不同的调度规则针对不同的问题和不同的输入表现出不同的性能，因此，本研究针对八种不同的优先调度规则，对各自的算法进行了详细的叙述；
4)利用Java语言编写了相应的应用程序。进一步地利用所编写的应用程序，对Job-Shopscheduling两个经典的benchmark问题(即标杆问题)FT06和FT10进行了运算；
5)设计了考虑相关性的FT06和FT10的变体问题，对两个变体问题也进行了相应的作业计划运算；
6)对四个问题的作业计划结果的进行了详细的分析，结果表明了算法的正确性和可行性；进一步对不同目标时各种调度规则的性能进行了分析和评价。
Job-Shop scheduling, a high simplification of practical production, is a coexistent problem in product manufacturing industry. Solving the problem well be the key to make the full use of resource, work out the rational production plan of workshop and enterprise, ensure the delivery just in time, increase the reputation of enterprise, gain the more consumers and get survival in the struggle. Job-Shop scheduling is a kind of combinatorial optimization problem very hard to solve. Many efforts have been made for several decades in order to solve the hard problem and made considerable achievement. But a large amount of work must be done if the problem is solved completely. Several problems in this field have been studied in depth and some good results have been obtained in this dissertation.
1) The definiton of Job-Shop scheduling problem is given. Its characteristics are analysed. The possibility and complexity of it are discussed. And the main techniques and methods of solving it are reviewed.
2) The concept of relativity between tasks, which is often concerned in project management, is taken into account in Job-Shop scheduling. In the past researches on Job-Shop scheduling, the relativity of finish-start is only conisderde in the same part's working procedures, which can't obviously reflect the reality of production system in machine facture enterprises accurately and intactly. The schedulings drawn form those researches are usually infeasible. There are possibly being four kinds of relativity in actual machine manufactural system, they are finish-start(FS), finish-finish(FF), start-start(SS) and start-finish(SF). Because the four relativities are introduced to actual job-shop schedulings in this research, thus various kinds of restraint of process technology in real production system are defined and reflected intactly and feasibility of Job-Shop scheduling are ensured.
3) On the base of reviewing and analysing the relevant papers synthetically, according to the characteristics in real production system, the requistion on scheduling and considering the time complexity and space complexity of the algorithm, priority dispatcher rules is used to solve scheduling problem by regular algorithms. For priority dispatcher rules are strongly problem denpendent, that is, different rule has different perfomance for different problem and different input, eight kinds of different priority dispatcher ruleses are taken into account in this researchand the algorithms are given respectively.
4) The corresponding application program is written in Java in this research. Ulteriorly, two classical benchmark issues on Job-Shop scheduling, namely FT06 and FT10, are carried on operation by utilizing the application program.
5) Two anamorphosises of FT06 and FT10 are designed by cosidering relativity, and they are also carried on operation by utilizing the application program.
6) The result of the four schedulings are analyzed in detail, the results validated the exactness and feasibility of the algorithm; the performances of the eight kinds of priority dispatcher rules, when used to different objectives, are analysed and evaluated further.
1)给出了单件车间调度问题的定义，分析了单件车间作业调度研究的特点及意义，回顾了研究求解单件车间作业调度问题的主要历程及其方法。
2)将项目管理中的相关性概念应用到单件车间的生产调度中。在以前的作业计划中，只考虑同一零件的各道工序之间的完成—开始相关，这显然不能完整准确地反映机械制造企业生产系统的实际情况，得出的作业计划也自然缺乏可行性。实际的机械生产系统可能存在着完成—开始(FS)、完成—完成(FF)、开始—开始(SS)、开始—完成(SF)四种类型。在本文中将上述的四种相关性均引入作业计划算法中加于考虑，从而完整地定义和反映了实际生产系统的各种加工技术约束，保证作业计划的可行性。
3)在综合分析和研究相关文献的基础上，针对实际生产系统的特点、对作业计划的要求及对算法时间复杂度与空间复杂度的考虑，本文采用了优先调度规则算法来求解作业计划问题。由于优先调度规则具有较强的问题依赖性，即不同的调度规则针对不同的问题和不同的输入表现出不同的性能，因此，本研究针对八种不同的优先调度规则，对各自的算法进行了详细的叙述；
4)利用Java语言编写了相应的应用程序。进一步地利用所编写的应用程序，对Job-Shopscheduling两个经典的benchmark问题(即标杆问题)FT06和FT10进行了运算；
5)设计了考虑相关性的FT06和FT10的变体问题，对两个变体问题也进行了相应的作业计划运算；
6)对四个问题的作业计划结果的进行了详细的分析，结果表明了算法的正确性和可行性；进一步对不同目标时各种调度规则的性能进行了分析和评价。
Job-Shop scheduling, a high simplification of practical production, is a coexistent problem in product manufacturing industry. Solving the problem well be the key to make the full use of resource, work out the rational production plan of workshop and enterprise, ensure the delivery just in time, increase the reputation of enterprise, gain the more consumers and get survival in the struggle. Job-Shop scheduling is a kind of combinatorial optimization problem very hard to solve. Many efforts have been made for several decades in order to solve the hard problem and made considerable achievement. But a large amount of work must be done if the problem is solved completely. Several problems in this field have been studied in depth and some good results have been obtained in this dissertation.
1) The definiton of Job-Shop scheduling problem is given. Its characteristics are analysed. The possibility and complexity of it are discussed. And the main techniques and methods of solving it are reviewed.
2) The concept of relativity between tasks, which is often concerned in project management, is taken into account in Job-Shop scheduling. In the past researches on Job-Shop scheduling, the relativity of finish-start is only conisderde in the same part's working procedures, which can't obviously reflect the reality of production system in machine facture enterprises accurately and intactly. The schedulings drawn form those researches are usually infeasible. There are possibly being four kinds of relativity in actual machine manufactural system, they are finish-start(FS), finish-finish(FF), start-start(SS) and start-finish(SF). Because the four relativities are introduced to actual job-shop schedulings in this research, thus various kinds of restraint of process technology in real production system are defined and reflected intactly and feasibility of Job-Shop scheduling are ensured.
3) On the base of reviewing and analysing the relevant papers synthetically, according to the characteristics in real production system, the requistion on scheduling and considering the time complexity and space complexity of the algorithm, priority dispatcher rules is used to solve scheduling problem by regular algorithms. For priority dispatcher rules are strongly problem denpendent, that is, different rule has different perfomance for different problem and different input, eight kinds of different priority dispatcher ruleses are taken into account in this researchand the algorithms are given respectively.
4) The corresponding application program is written in Java in this research. Ulteriorly, two classical benchmark issues on Job-Shop scheduling, namely FT06 and FT10, are carried on operation by utilizing the application program.
5) Two anamorphosises of FT06 and FT10 are designed by cosidering relativity, and they are also carried on operation by utilizing the application program.
6) The result of the four schedulings are analyzed in detail, the results validated the exactness and feasibility of the algorithm; the performances of the eight kinds of priority dispatcher rules, when used to different objectives, are analysed and evaluated further.
引文
[1] 王凌，车间调度及其遗传算法，清华大学出版社，2003
[2] 周绪、高连生等，车间作业计划问题的全局动态模型，中国机械工程，2001，(5)：112～115
[3] 熊锐、吴澄，车间生产调度问题的技术现状与发展趋势，清华大学学报(自然科学版)，1998，(10)：55～60
[4] 周永泰等，国内模具市场分析与预测，模具工业，1998，(1)：48～50
[5] 罗继相，浅析我国模具行业现状及发展趋势和对策，模具技术，2001，(3)：72～75
[6] 许发樾，模具企业的管理与建设，模具工业，1999，(12)：3～10
[7] William G. Bistline Sr.,Snehamay Banerjee, Avijit Banerjee. RTSS: An Interactive Decision Support System foe Solving Real Time Scheduling Problems Considering Customer and Job Priorities. with Schedule Interruptions. Computers and Operations Research, Computers Ops Res. 1998, 25(11): 981～995
[8] 黄红选、冯允成，JOb-Shop的工件序摄动分析算法，清华大学学报(自然科学版)，1998，(11)：125～128
[9] 何霆、马玉林，Job-Shop调度研究现状及发展趋势，专题报道，2000，(10)：19～21
[10] 韩丽敏、黄红选、冯允成，解JOb-Shop问题的一种组合模拟算法，北京航空航天大学学报，1998，(2)：75～78
[11] 常会友、刘丕娥、张淑丽等，基于效率函数求解的单件车间调度问题的解法，计算机集成制造系统，1998，(8)：51～56
[12] 蒋昌俊，Petri网理论与方法研究综述，控制与决策，1997，(11)：631～636
[13] J Peterson, Petri net theory and the modeling of system, Prentic-hall, Engle-wood, NJ, 1981
[14] T Murate. Petri nets:Properties analysis and applications. In:Proc of the IEEE. 1989.77(4)
[15] R Karp, R Miller. Parallel program schemata.J of Computer & Syst Sci, 1969, 3(4)
[16] A Finkel. The minimal coverability graph for Petri nets. LNCS, 1993,674:210～243
[17] S C Cheung, J Kramer. Enhancing compositional reachability analysis with
context constraints. ACMS of Tware Engineering Notes, 1993,18(5):115～125
[18] 陈永凤等，物资调运过程的PETRI网建模及仿真，计算机仿真，1997，(10)：27～31
[19] 王万良、吴启迪、赵燕伟等，流程工业CIMS中生产调度研究进展，机电工程，1999，(5)：13～16
[20] 程虎，Java语言的特点，现代科学仪器，1997，(2)：11～14
[21] 郁心、丁锂，Java语言的特色与作用，电子展望与决策，1997，(2)：45～47
[22] Java手册，科学出版社，1996年
[23] 衬庆章，引人注目的Java语言，计算机时代，1997，(2)：20～22
[24] 吴锋、刘文煌，车间作业计划编制问题的统一描述与应用，系统工程理论与实践，1998，(12)：30～34
[25] 卫军胡、孙国基础，一种新的制造系统仿真调度规则，系统仿真学报，1999，(10)：354～357
[26] 卢开澄，计算机算法导引—设计与分析，清华大学出版社，1996
[27] 赖朝安、孙延明等，抓住关键缩短模具开发周期，锻压机械，2001，(5)：49～51
[28] 成虎，工程项目管理，北京：中国建筑工业出版社，1997
[29] 李富国、叶飞帆，多功能机床环境下的Job-Shop问题研究，中国管理科学，2000，(12)：24～28
[30] Giffler B.,Thompson G L.,Algorithms for Solving Production Scheduling Problem, Operations Research, 1996, (8):487～503
[31] Gere W.S.,Heuristics in Job-Shop Scheduling, Management Science, 1996, (13):167～190
[32] Balas E.,Machine Scheduling via Disjunctive Graphs:An implicit Enumeration Algorithm, Operations Research, 1969, (17):941～957
[33] Vicente Valls, M. Angeles Perez, M. Sacramento Quintanilla, A Tabu Search to Machine Scheduling, European Journal of Operational Research, 1998, (106):277～300
[34] Carlier J.,Pinson E.,An Algorithm for Solving the Job-Shop Problem, Management Science, 1989, (35):164～176
[35] Carlier J.,Pinson E.,Practical Use of Jackson's Pre-emptive Schedule for Solving the Job-Shop Problem, Annals of Operations Research, 1990, (26):269～
287
[36] Applegate D.,Cook W.,A Computatinal Study of the Job-Shop Scheduling Problem, ORSA Journal on Computing, 1991, (3)2:149～156
[37] Sabuncuoglu I.,Gurgun B.,A Neural Network Model for Scheduling Problems, European Journal of Operations Research, 1996, (2)93:288～299
[38] 于海滨等，一种基于神经网络的调度方法，自动化学报，1999，(7)：449～456
[39] A.O. Awanied.,Project management techniques, New York Petrocelli Books, 1983
[40] 张金锁主编，工程项目管理学，科学出版社，2000，(3)
[41] 胡振华，工程项目管理，湖南人民出版社，2001
[42] 丛培经，工程项目管理(修行本)，中国建筑工业出版社，2003，(3)
[43] 罗耀辉，车间作业计划调度系统的研究与开发，西北工业大学硕士学位论文，2002，(3)：16～17
[44] 童刚，Job-Shop调度问题理论及方法的应用研究，天津大学博士学位论文，2000，(6)：8～12
[45] 吴江华、陈卓宁、宾鸿赞，单件车间的启发式调度策略，石油机械，2000，(3)28：50～52
[46] 周绪，面向多目标的全局动态作业计划系统的理论研究与实践，北京航空航天大学硕士学问论文，2001，(3)
[47] 成虎，工程项目管理，中国建筑工业出版社，1997
[48] 胡斌、黎志成，单件车间生产作业计划再生方法研究，华中理工大学学报，1999，(2)：16～18
[49] 潘家昭、刘丽文，现代生产管理学[M]，清华大学出版社，1996
[50] 康宁、王凤儒、刘丕娥等，有交货期的单件车间调度问题的逆序算法，系统工程理论与实践，1999，(12)：25～30
[51] 李琦、梁斌等，有顺序约束的单件车间调度问题的逆序算法，鞍山钢铁学院学报，2001，(12)：412～415
[52] 马玉芳，CIMS条件下，单件小批量生产的生产作业计划的编制方法及验证分析，中国管理科学，1999，(3)：36～41
[2] 周绪、高连生等，车间作业计划问题的全局动态模型，中国机械工程，2001，(5)：112～115
[3] 熊锐、吴澄，车间生产调度问题的技术现状与发展趋势，清华大学学报(自然科学版)，1998，(10)：55～60
[4] 周永泰等，国内模具市场分析与预测，模具工业，1998，(1)：48～50
[5] 罗继相，浅析我国模具行业现状及发展趋势和对策，模具技术，2001，(3)：72～75
[6] 许发樾，模具企业的管理与建设，模具工业，1999，(12)：3～10
[7] William G. Bistline Sr.,Snehamay Banerjee, Avijit Banerjee. RTSS: An Interactive Decision Support System foe Solving Real Time Scheduling Problems Considering Customer and Job Priorities. with Schedule Interruptions. Computers and Operations Research, Computers Ops Res. 1998, 25(11): 981～995
[8] 黄红选、冯允成，JOb-Shop的工件序摄动分析算法，清华大学学报(自然科学版)，1998，(11)：125～128
[9] 何霆、马玉林，Job-Shop调度研究现状及发展趋势，专题报道，2000，(10)：19～21
[10] 韩丽敏、黄红选、冯允成，解JOb-Shop问题的一种组合模拟算法，北京航空航天大学学报，1998，(2)：75～78
[11] 常会友、刘丕娥、张淑丽等，基于效率函数求解的单件车间调度问题的解法，计算机集成制造系统，1998，(8)：51～56
[12] 蒋昌俊，Petri网理论与方法研究综述，控制与决策，1997，(11)：631～636
[13] J Peterson, Petri net theory and the modeling of system, Prentic-hall, Engle-wood, NJ, 1981
[14] T Murate. Petri nets:Properties analysis and applications. In:Proc of the IEEE. 1989.77(4)
[15] R Karp, R Miller. Parallel program schemata.J of Computer & Syst Sci, 1969, 3(4)
[16] A Finkel. The minimal coverability graph for Petri nets. LNCS, 1993,674:210～243
[17] S C Cheung, J Kramer. Enhancing compositional reachability analysis with
context constraints. ACMS of Tware Engineering Notes, 1993,18(5):115～125
[18] 陈永凤等，物资调运过程的PETRI网建模及仿真，计算机仿真，1997，(10)：27～31
[19] 王万良、吴启迪、赵燕伟等，流程工业CIMS中生产调度研究进展，机电工程，1999，(5)：13～16
[20] 程虎，Java语言的特点，现代科学仪器，1997，(2)：11～14
[21] 郁心、丁锂，Java语言的特色与作用，电子展望与决策，1997，(2)：45～47
[22] Java手册，科学出版社，1996年
[23] 衬庆章，引人注目的Java语言，计算机时代，1997，(2)：20～22
[24] 吴锋、刘文煌，车间作业计划编制问题的统一描述与应用，系统工程理论与实践，1998，(12)：30～34
[25] 卫军胡、孙国基础，一种新的制造系统仿真调度规则，系统仿真学报，1999，(10)：354～357
[26] 卢开澄，计算机算法导引—设计与分析，清华大学出版社，1996
[27] 赖朝安、孙延明等，抓住关键缩短模具开发周期，锻压机械，2001，(5)：49～51
[28] 成虎，工程项目管理，北京：中国建筑工业出版社，1997
[29] 李富国、叶飞帆，多功能机床环境下的Job-Shop问题研究，中国管理科学，2000，(12)：24～28
[30] Giffler B.,Thompson G L.,Algorithms for Solving Production Scheduling Problem, Operations Research, 1996, (8):487～503
[31] Gere W.S.,Heuristics in Job-Shop Scheduling, Management Science, 1996, (13):167～190
[32] Balas E.,Machine Scheduling via Disjunctive Graphs:An implicit Enumeration Algorithm, Operations Research, 1969, (17):941～957
[33] Vicente Valls, M. Angeles Perez, M. Sacramento Quintanilla, A Tabu Search to Machine Scheduling, European Journal of Operational Research, 1998, (106):277～300
[34] Carlier J.,Pinson E.,An Algorithm for Solving the Job-Shop Problem, Management Science, 1989, (35):164～176
[35] Carlier J.,Pinson E.,Practical Use of Jackson's Pre-emptive Schedule for Solving the Job-Shop Problem, Annals of Operations Research, 1990, (26):269～
287
[36] Applegate D.,Cook W.,A Computatinal Study of the Job-Shop Scheduling Problem, ORSA Journal on Computing, 1991, (3)2:149～156
[37] Sabuncuoglu I.,Gurgun B.,A Neural Network Model for Scheduling Problems, European Journal of Operations Research, 1996, (2)93:288～299
[38] 于海滨等，一种基于神经网络的调度方法，自动化学报，1999，(7)：449～456
[39] A.O. Awanied.,Project management techniques, New York Petrocelli Books, 1983
[40] 张金锁主编，工程项目管理学，科学出版社，2000，(3)
[41] 胡振华，工程项目管理，湖南人民出版社，2001
[42] 丛培经，工程项目管理(修行本)，中国建筑工业出版社，2003，(3)
[43] 罗耀辉，车间作业计划调度系统的研究与开发，西北工业大学硕士学位论文，2002，(3)：16～17
[44] 童刚，Job-Shop调度问题理论及方法的应用研究，天津大学博士学位论文，2000，(6)：8～12
[45] 吴江华、陈卓宁、宾鸿赞，单件车间的启发式调度策略，石油机械，2000，(3)28：50～52
[46] 周绪，面向多目标的全局动态作业计划系统的理论研究与实践，北京航空航天大学硕士学问论文，2001，(3)
[47] 成虎，工程项目管理，中国建筑工业出版社，1997
[48] 胡斌、黎志成，单件车间生产作业计划再生方法研究，华中理工大学学报，1999，(2)：16～18
[49] 潘家昭、刘丽文，现代生产管理学[M]，清华大学出版社，1996
[50] 康宁、王凤儒、刘丕娥等，有交货期的单件车间调度问题的逆序算法，系统工程理论与实践，1999，(12)：25～30
[51] 李琦、梁斌等，有顺序约束的单件车间调度问题的逆序算法，鞍山钢铁学院学报，2001，(12)：412～415
[52] 马玉芳，CIMS条件下，单件小批量生产的生产作业计划的编制方法及验证分析，中国管理科学，1999，(3)：36～41