基于遗传算法的Job-Shop车间调度问题研究
|
摘要
如何提高单件产品作业车间调度型(Job-Shop型)的生产制造效率是人们一直关注和希冀解决的问题。由于其计算复杂性、动态约束性等特点,Job-Shop车间调度问题已经被证明是一个NP(非确定性多项式)难问题,一直以来人们提出了各种智能算法和程序来加以解决,其中遗传算法作为求解该类问题的一种重要手段之一,得到越来越多国内外学者的重视。但是在这些研究和应用过程中,较慢的收敛速度和较低的求解准确度一直是这一研究的瓶颈。为了改善目前求解这类问题的遗传算法的性能,加快搜索最优调度解的速度,本文以某企业分厂模具制造车间为研究背景,从遗传算法的角度进行了Job-Shop生产方式下的车间调度算法研究。
本文共分为三个部分:
第一部分为基础理论部分(第一章),指出了论文选题的重要性,并对该课题的国内外研究现状进行了评述;
第二部分为项目背景部分(第二章),对该项目企业分厂模具车间的生产环境、现状、计划控制流程以及生产特点进行详细阐述、分析与诊断;
第三部分为算法分析部分(第三章、第四章),在基于工序编码方式的基础上,设计了保存基因片段逆序交叉的遗传算子,将其运用于基于模糊加工时间和交货期Job-Shop问题中,并通过经典理论算例和实际生产案例,验证了算法的有效性。
研究结果表明:该遗传交叉方式不仅保证了遗传后代的可行性和多样性,而且提高了搜索最优调度解的准确度。
How to improve the productivity under the Job-Shop manufacturing mode has always been an issue of concern to the people. Because of its complicated calculation, dynamic multi-restriction, Job-Shop scheduling problem (JSP) has been proved as NP-hard (Non-deterministic Polynomial-hard) problem, and many intelligent computation methods are introduced into this field in recent years. Among these, genetic algorithm (GA) is one of the most popular methods getting an increasing attention by domestic and overseas experts recently. But slow convergence and low precision still exist in these applications and research. To improve the performance of the existing GA for JSP and speed up searching for the optimal scheduling solution, based on the background of a mould manufacturing shop, this dissertation studied JSP using an improved GA.
Three parts were contained:
1. Chapter 1(basic theory), introducing the importance of the subject, the status of present worldwide research in this field.
2. Chapter 2(project background), describing and analyzing the environment, status, and characteristics of production, the process of plan and control, etc.
3. Chapter 3&4(algorithm analysis), based on operation-based representation, designing keeping-fragments-reverse-crossover, which was applied to JSP with fuzzy processing time and duedate, then classical and realistic numeric examples were given which validated the effectiveness and efficiency of the proposed method.
The results showed that: this improved algorithm not only ensured validity and diversification of the evolving descendants, but also improved precision of optimal schedule.
本文共分为三个部分:
第一部分为基础理论部分(第一章),指出了论文选题的重要性,并对该课题的国内外研究现状进行了评述;
第二部分为项目背景部分(第二章),对该项目企业分厂模具车间的生产环境、现状、计划控制流程以及生产特点进行详细阐述、分析与诊断;
第三部分为算法分析部分(第三章、第四章),在基于工序编码方式的基础上,设计了保存基因片段逆序交叉的遗传算子,将其运用于基于模糊加工时间和交货期Job-Shop问题中,并通过经典理论算例和实际生产案例,验证了算法的有效性。
研究结果表明:该遗传交叉方式不仅保证了遗传后代的可行性和多样性,而且提高了搜索最优调度解的准确度。
How to improve the productivity under the Job-Shop manufacturing mode has always been an issue of concern to the people. Because of its complicated calculation, dynamic multi-restriction, Job-Shop scheduling problem (JSP) has been proved as NP-hard (Non-deterministic Polynomial-hard) problem, and many intelligent computation methods are introduced into this field in recent years. Among these, genetic algorithm (GA) is one of the most popular methods getting an increasing attention by domestic and overseas experts recently. But slow convergence and low precision still exist in these applications and research. To improve the performance of the existing GA for JSP and speed up searching for the optimal scheduling solution, based on the background of a mould manufacturing shop, this dissertation studied JSP using an improved GA.
Three parts were contained:
1. Chapter 1(basic theory), introducing the importance of the subject, the status of present worldwide research in this field.
2. Chapter 2(project background), describing and analyzing the environment, status, and characteristics of production, the process of plan and control, etc.
3. Chapter 3&4(algorithm analysis), based on operation-based representation, designing keeping-fragments-reverse-crossover, which was applied to JSP with fuzzy processing time and duedate, then classical and realistic numeric examples were given which validated the effectiveness and efficiency of the proposed method.
The results showed that: this improved algorithm not only ensured validity and diversification of the evolving descendants, but also improved precision of optimal schedule.
引文
1.罗鸿.ERP原理设计实施.[M].第三版.北京:电子工业出版社,2005
2.熊锐.车间生产调度问题的技术现状与发展趋势.[J].清华大学学报(自然科学版).1998,38(10):55-60
3.熊禾根.模具企业动态车间作业计划研究.[D].武汉:华中科技大学,2005
4.K.R.Baker.Introduction to Sequencing and Scheduling.[M].New York:John Wiley and Sons,1974
5.M.R.Garey.The complexity of flow shop and job-shop scheduling.[J].Math Operation Research,1976,5(1):117-129
6.康宁,王凤儒.有交货期的单件车间调度问题的逆序算法.[J].系统工程理论与实践.1999,6(12):25-30
7.Y.Zinder.An iterative algorithm for scheduling UET tasks with due dates and Release times.[J].2003,149(2):326-338
8.李莉,李大卫.带有交货期窗口的调度问题及算法.[J].系统工程学报.1998,13(4):16-23
9.Z.L.Chen.Parallel machine scheduling with a common due window.European Journal of Operational Research.[J].2002,136(2):512-527
10.吴悦,汪定伟.模糊交货期窗口下极大化顾客满意数的最优调度.[J].系统工程理论方法应用,1999,8(1):33-38
11.陈秋双,齐向彤.JOB SHOP投入控制与调度研究.[J].系统工程学报.1997,12(2):49-56
12.史蒂文森.生产与运作管理.[M].北京:机械工业出版社,2000
13.王成尧,高麟.模糊加工时间调度问题的研究.[J].系统工程学报.1999,14(3):238-242
14.潘群.模糊加工时间的车间调度优化.[J].经济师.2004,2(5):283-284
15.Y.K.Mikhail.Single machine batch scheduling with deadlines and resource dependent processing time.[J].Operations Research Letters.1995,17(5):243-249
16.贾春福.加工时间服从指数分布单机随机调度.[J].系统工程.2002,20(6):58-61
17.孙志峻,乔冰.具有柔性加工路径的作业车间批量调度优化研究.[J].机械科学与技术.2002,21(3):348-354
18.S.T.Christoph.Job shop scheduling with alternative process Production Economics.[J].2001,74(1-3):125-134
19.K.K.Yeo.A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling.[J].Computers & Operations Research.2003,30(8):1151-1171
20.A.Makoto,O.Hiroshi.Single machine scheduling to meet due times under hutdown constraints.[J].Int.J.Production Economics.1999,60-61:537-547
21.O.Holthaus.Scheduling in job shops with machine breakdowns:an experimental study.[J].Computers & Industrial Engineering.1999,36(1):137-162
22.陈仕平,何勇.一类带机器准备时间的排序复杂性及算法.[J].应用数学学报.1998,21(3):474-476
23.金宏,王宏安.模糊动态抢占调度算法.[J].计算机学报.2004,27(6):812-817
24.J.A.Ho-ogeveen.Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing.[J].European Journal of Operational Research.2000,126(1):131-151
25.C.A.Yano.Algorithms for a class of single-machine weighted tardiness and earliness problems.[J].European Journal of Operational Research.1995,81(3):663-664
26.R.Ghaith,M.Mansooreh,Anagnostopoulos.A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time.[J].Computers & Operations Research.2004,31(10):1727-1751
27.郑大钟,赵千川.离散事件动态系统.[M].第一版.北京:清华大学出版社,2001
28.F.Pezzella,E.Merelli.A tabu search method guided by shifting bottleneck for the job shop scheduling problem.[J].European Journal of Operational Research.2000,120(2):297-310
29.姚倡锋,张定华.基于遗传算法的网络化制造单元选择问题研究.[J].计算机集成制造系统.2004,10(12):1555-1560
30.Goldberg D.E.Genetic Algorithms in Search.[J].Optimization and Machine Learning.1997,24(2):193-198
31.P.Hansen,N.Mladenovic.Variable neighborhood search:Principles and applications.[J].European Journal of Operational Research.2001,130(3):449-467
32.任守纲.基于人工神经网络的制造执行系统软件库构件提取方法研究.[J].中国机械工程.2004,15(12):1059-1062
33.王亚超,马汉武.生产物流系统建模与仿真——Witness系统与应用.[M].北京:科学出版社,2006
34.王凌.车间调度及其遗传算法.[M].北京:清华大学出版社,2003
35.Nakano R,Yamada T.Conventional genetic algorithm for job shop problems.[J].In: Proc 4~(th)Int Conf Genetic algorithms and their Applications.1991,474-479
36.Shi G.A genetic algorithm applied to a classic job-shop scheduling problem.[J].International Journal of Systems Science.1997,28(1):25-32
37.Cheng R W,Gen M,Tsujimura Y.A tutorial survey of job-shop scheduling problems using genetic algorithms Ⅱ-hybrid genetic search strategies.[J].Computers and Industrial Engineering.1999,36(2):343-364
38.Qi J G,Burns G R,Harrison D K.The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling.[J].International Journal of Advanced Manufacturing Technology.2000,16(8):609-615
39.Tadei R,Croce F D,Advanced search techniques for the job-shop problem-a comparison.[J].Rairo-RO-Oper Res.1993,29(2):179-194
40.Kurbel K,Rohmann T.A comparison of job-shop scheduling techniques:simulated annealing,genetic algorithms,and mathematical optimization.[J].Wirtschaftsinformatik.1995,37(6):581-593
41.Ponnambalam S G,Jawahar N.A simulated annealing algorithm for job shop scheduling.[J].Production Planning and Control.1999,10(8):767-777
42.Dagli C H,Sittisathanchai S.Genetic neuro-scheduler for job-shop scheduling.[J].Computers and Industrial Engineering,25(1-4):267-270
43.Kolonko M.Some new results on simulated annealing applied to the job shop scheduling problem.[J].European Journal of Operational Research.1999,113(1):123-136
44.Cai L W,Wu Q H.A genetic algorithm with local search for solving job shop problems.[J].Lecture Notes in Computer Science.2000,1803:107-116
45.Lee I,Sikora R,Shaw M J.A genetic algorithm-based approach to flexible flow-line scheduling with variable lot sizes.[J].IEEE Transactions on Systems,Man,and Cybernetics-B.1997,27(1):36-54
46.Ozdamar L,Birbil S I.Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions.[J].European Journal of Operational Research.1998,110(3):525-547
47.Sakawa M,Mori T.An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate.[J].Computers and Industrial Engineering.1999,36:325-341
48.杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题.[J].计算机集成制造系统.2004,10(9):1114-1119
49.李春延.基于遗传的作业车间调度问题研究.[D].燕山:燕山大学,2007
50.J.E.C Arroyo,V.A Armentano.Genetic Local Search for Multi-objective Flowshop Scheduling Problems.[J].European Journal of Operational Research.2005,167:717-738
51.C.G Wu,X.L Xing,Y.C Liang.Genetic Algorithm Application on the Job Shop Scheduling Problem.[J].Proceedings of the third International Conference on Machine Learning and Cybernetics.2004,3:2102-2106
52.陈国良,王煦法,庄镇泉等.遗传算法及其应用.[M].北京:人民邮电出版社,1996
53.周明,孙树栋.遗传算法原理及应用.[M].北京:国防工业出版社,1999
54.B.Roy,B.Sussmann.Les problèmes d'ordonnancement avec constraints disjonctives.[J].SEMA Note D.S.No.9 Paris,1964
55.孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.[J].控制与决策.1996,11(4):425-431
56.Fisher H,Thompson G L.Probabilistic learning combinations of local job-shop scheduling rules.[J].In:Muth J F and Thompson G L,ed.Industrial Scheduling.Prentice-Hall,Englewood Cliffs.1963,NJ:225-251
57.Slowinski R,Hapke M.Scheduling under fuzziness.[M].New York:Physica-Verlag.2000
58.Inés González-Rodríguez,Camino R.Vela.Study of Objective Functions in Fuzzy Job-Shop Problem.[M].ICAISC 2006,LNAI 4029,360-369
59.王小平,曹立明.遗传算法——理论、应用与软件实现.第一版.[M].西安:西安交通大学出版社,2002
60.李富明,朱云龙,尹朝万.可变机器约束的模糊作业车间调度问题研究.[J].计算机集成制造系统—CIMS.2006,12(2):169-173
2.熊锐.车间生产调度问题的技术现状与发展趋势.[J].清华大学学报(自然科学版).1998,38(10):55-60
3.熊禾根.模具企业动态车间作业计划研究.[D].武汉:华中科技大学,2005
4.K.R.Baker.Introduction to Sequencing and Scheduling.[M].New York:John Wiley and Sons,1974
5.M.R.Garey.The complexity of flow shop and job-shop scheduling.[J].Math Operation Research,1976,5(1):117-129
6.康宁,王凤儒.有交货期的单件车间调度问题的逆序算法.[J].系统工程理论与实践.1999,6(12):25-30
7.Y.Zinder.An iterative algorithm for scheduling UET tasks with due dates and Release times.[J].2003,149(2):326-338
8.李莉,李大卫.带有交货期窗口的调度问题及算法.[J].系统工程学报.1998,13(4):16-23
9.Z.L.Chen.Parallel machine scheduling with a common due window.European Journal of Operational Research.[J].2002,136(2):512-527
10.吴悦,汪定伟.模糊交货期窗口下极大化顾客满意数的最优调度.[J].系统工程理论方法应用,1999,8(1):33-38
11.陈秋双,齐向彤.JOB SHOP投入控制与调度研究.[J].系统工程学报.1997,12(2):49-56
12.史蒂文森.生产与运作管理.[M].北京:机械工业出版社,2000
13.王成尧,高麟.模糊加工时间调度问题的研究.[J].系统工程学报.1999,14(3):238-242
14.潘群.模糊加工时间的车间调度优化.[J].经济师.2004,2(5):283-284
15.Y.K.Mikhail.Single machine batch scheduling with deadlines and resource dependent processing time.[J].Operations Research Letters.1995,17(5):243-249
16.贾春福.加工时间服从指数分布单机随机调度.[J].系统工程.2002,20(6):58-61
17.孙志峻,乔冰.具有柔性加工路径的作业车间批量调度优化研究.[J].机械科学与技术.2002,21(3):348-354
18.S.T.Christoph.Job shop scheduling with alternative process Production Economics.[J].2001,74(1-3):125-134
19.K.K.Yeo.A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling.[J].Computers & Operations Research.2003,30(8):1151-1171
20.A.Makoto,O.Hiroshi.Single machine scheduling to meet due times under hutdown constraints.[J].Int.J.Production Economics.1999,60-61:537-547
21.O.Holthaus.Scheduling in job shops with machine breakdowns:an experimental study.[J].Computers & Industrial Engineering.1999,36(1):137-162
22.陈仕平,何勇.一类带机器准备时间的排序复杂性及算法.[J].应用数学学报.1998,21(3):474-476
23.金宏,王宏安.模糊动态抢占调度算法.[J].计算机学报.2004,27(6):812-817
24.J.A.Ho-ogeveen.Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing.[J].European Journal of Operational Research.2000,126(1):131-151
25.C.A.Yano.Algorithms for a class of single-machine weighted tardiness and earliness problems.[J].European Journal of Operational Research.1995,81(3):663-664
26.R.Ghaith,M.Mansooreh,Anagnostopoulos.A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time.[J].Computers & Operations Research.2004,31(10):1727-1751
27.郑大钟,赵千川.离散事件动态系统.[M].第一版.北京:清华大学出版社,2001
28.F.Pezzella,E.Merelli.A tabu search method guided by shifting bottleneck for the job shop scheduling problem.[J].European Journal of Operational Research.2000,120(2):297-310
29.姚倡锋,张定华.基于遗传算法的网络化制造单元选择问题研究.[J].计算机集成制造系统.2004,10(12):1555-1560
30.Goldberg D.E.Genetic Algorithms in Search.[J].Optimization and Machine Learning.1997,24(2):193-198
31.P.Hansen,N.Mladenovic.Variable neighborhood search:Principles and applications.[J].European Journal of Operational Research.2001,130(3):449-467
32.任守纲.基于人工神经网络的制造执行系统软件库构件提取方法研究.[J].中国机械工程.2004,15(12):1059-1062
33.王亚超,马汉武.生产物流系统建模与仿真——Witness系统与应用.[M].北京:科学出版社,2006
34.王凌.车间调度及其遗传算法.[M].北京:清华大学出版社,2003
35.Nakano R,Yamada T.Conventional genetic algorithm for job shop problems.[J].In: Proc 4~(th)Int Conf Genetic algorithms and their Applications.1991,474-479
36.Shi G.A genetic algorithm applied to a classic job-shop scheduling problem.[J].International Journal of Systems Science.1997,28(1):25-32
37.Cheng R W,Gen M,Tsujimura Y.A tutorial survey of job-shop scheduling problems using genetic algorithms Ⅱ-hybrid genetic search strategies.[J].Computers and Industrial Engineering.1999,36(2):343-364
38.Qi J G,Burns G R,Harrison D K.The application of parallel multipopulation genetic algorithms to dynamic job-shop scheduling.[J].International Journal of Advanced Manufacturing Technology.2000,16(8):609-615
39.Tadei R,Croce F D,Advanced search techniques for the job-shop problem-a comparison.[J].Rairo-RO-Oper Res.1993,29(2):179-194
40.Kurbel K,Rohmann T.A comparison of job-shop scheduling techniques:simulated annealing,genetic algorithms,and mathematical optimization.[J].Wirtschaftsinformatik.1995,37(6):581-593
41.Ponnambalam S G,Jawahar N.A simulated annealing algorithm for job shop scheduling.[J].Production Planning and Control.1999,10(8):767-777
42.Dagli C H,Sittisathanchai S.Genetic neuro-scheduler for job-shop scheduling.[J].Computers and Industrial Engineering,25(1-4):267-270
43.Kolonko M.Some new results on simulated annealing applied to the job shop scheduling problem.[J].European Journal of Operational Research.1999,113(1):123-136
44.Cai L W,Wu Q H.A genetic algorithm with local search for solving job shop problems.[J].Lecture Notes in Computer Science.2000,1803:107-116
45.Lee I,Sikora R,Shaw M J.A genetic algorithm-based approach to flexible flow-line scheduling with variable lot sizes.[J].IEEE Transactions on Systems,Man,and Cybernetics-B.1997,27(1):36-54
46.Ozdamar L,Birbil S I.Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions.[J].European Journal of Operational Research.1998,110(3):525-547
47.Sakawa M,Mori T.An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate.[J].Computers and Industrial Engineering.1999,36:325-341
48.杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题.[J].计算机集成制造系统.2004,10(9):1114-1119
49.李春延.基于遗传的作业车间调度问题研究.[D].燕山:燕山大学,2007
50.J.E.C Arroyo,V.A Armentano.Genetic Local Search for Multi-objective Flowshop Scheduling Problems.[J].European Journal of Operational Research.2005,167:717-738
51.C.G Wu,X.L Xing,Y.C Liang.Genetic Algorithm Application on the Job Shop Scheduling Problem.[J].Proceedings of the third International Conference on Machine Learning and Cybernetics.2004,3:2102-2106
52.陈国良,王煦法,庄镇泉等.遗传算法及其应用.[M].北京:人民邮电出版社,1996
53.周明,孙树栋.遗传算法原理及应用.[M].北京:国防工业出版社,1999
54.B.Roy,B.Sussmann.Les problèmes d'ordonnancement avec constraints disjonctives.[J].SEMA Note D.S.No.9 Paris,1964
55.孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.[J].控制与决策.1996,11(4):425-431
56.Fisher H,Thompson G L.Probabilistic learning combinations of local job-shop scheduling rules.[J].In:Muth J F and Thompson G L,ed.Industrial Scheduling.Prentice-Hall,Englewood Cliffs.1963,NJ:225-251
57.Slowinski R,Hapke M.Scheduling under fuzziness.[M].New York:Physica-Verlag.2000
58.Inés González-Rodríguez,Camino R.Vela.Study of Objective Functions in Fuzzy Job-Shop Problem.[M].ICAISC 2006,LNAI 4029,360-369
59.王小平,曹立明.遗传算法——理论、应用与软件实现.第一版.[M].西安:西安交通大学出版社,2002
60.李富明,朱云龙,尹朝万.可变机器约束的模糊作业车间调度问题研究.[J].计算机集成制造系统—CIMS.2006,12(2):169-173