基于遗传算法的作业车间多目标模糊调度问题研究
|
摘要
本文在综合国内外关于车间调度问题研究基础上,考虑现行作业车间运作的实际情况,将模糊逻辑与生产调度相结合,更加符合实际的生产情况,在制造企业提高生产效率、降低生产成本等方面起着积极作用。
论文的主要内容和创新之处如下:
1.建立了作业车间多目标模糊调度问题的数学模型,并结合合肥车桥厂项目给出了一个建模实例,提出了运用改进遗传算法求解作业车间调度的问题。
2.在同时考虑模糊加工时间和模糊交货期的基础上,对传统单一优化时间的遗传算法进行改进,建立了以生产时间、生产成本和生产利润为目标的优化模型,并将稳态繁殖、进化策略、模糊逻辑与种群多次产生法融入到遗传算法中,在满足用户不同调度需求的同时,还在一定程度上改善了遗传算法的性能。
3.最后对合肥车桥厂某调度实例进行了仿真研究,并用Visual Basic 6.0开发了具有人机交互界面的软件,取得了良好的效果,证明了此种方法的可行性和有效性。
On the basis of the technical review on the domestic and foreign research, this thesis has an extensive and systematic study on the job-shop scheduling by combining fuzzy logic, which has a great importance to improve productivity and reduce cost.
Main works and innovations of this dissertation are as follows.
1. Considering multi-objective of shop scheduling, the mathematical model of job-shop fuzzy scheduling for multi-objective is established. Meanwhile, a modeling example is given combining the project of Hefei Automobile Axle Co., Ltd. to solve this model and a corresponding genetic algorithm is developed.
2. Based on the model with both fuzzy processing time and fuzzy due date, traditional genetic algorithm is improved. A new method focused on optimizing production cost, makespan and profit is proposed. In this method, Steady State Reproduction, Fuzzy Logic, Evolutionary Strategy and Genetic Algorithm are combined to increase the convergence rate and decrease the probability of premature phenomena.
3. The corresponding software is developed with the highly visual computer language VB6.0. With the implement of this method in Hefei Automobile Axle Co., Ltd, it is proved to be feasible and efficient.
论文的主要内容和创新之处如下:
1.建立了作业车间多目标模糊调度问题的数学模型,并结合合肥车桥厂项目给出了一个建模实例,提出了运用改进遗传算法求解作业车间调度的问题。
2.在同时考虑模糊加工时间和模糊交货期的基础上,对传统单一优化时间的遗传算法进行改进,建立了以生产时间、生产成本和生产利润为目标的优化模型,并将稳态繁殖、进化策略、模糊逻辑与种群多次产生法融入到遗传算法中,在满足用户不同调度需求的同时,还在一定程度上改善了遗传算法的性能。
3.最后对合肥车桥厂某调度实例进行了仿真研究,并用Visual Basic 6.0开发了具有人机交互界面的软件,取得了良好的效果,证明了此种方法的可行性和有效性。
On the basis of the technical review on the domestic and foreign research, this thesis has an extensive and systematic study on the job-shop scheduling by combining fuzzy logic, which has a great importance to improve productivity and reduce cost.
Main works and innovations of this dissertation are as follows.
1. Considering multi-objective of shop scheduling, the mathematical model of job-shop fuzzy scheduling for multi-objective is established. Meanwhile, a modeling example is given combining the project of Hefei Automobile Axle Co., Ltd. to solve this model and a corresponding genetic algorithm is developed.
2. Based on the model with both fuzzy processing time and fuzzy due date, traditional genetic algorithm is improved. A new method focused on optimizing production cost, makespan and profit is proposed. In this method, Steady State Reproduction, Fuzzy Logic, Evolutionary Strategy and Genetic Algorithm are combined to increase the convergence rate and decrease the probability of premature phenomena.
3. The corresponding software is developed with the highly visual computer language VB6.0. With the implement of this method in Hefei Automobile Axle Co., Ltd, it is proved to be feasible and efficient.
引文
[1]戴绍利,谭跃进,汪浩.生产调度方法的系统研究系统工程[J].1999,17(1),p41-45
[2][日]玄光男,程润伟著.江定伟,唐加福,黄敏译.遗传算法与工程设计[M].北京:科学出版社,2000
[3]Chaitanya Swamy,Sachin Jain.Scheduling Algorithm B.Tech.Project Report,1999
[4]John B,Chambers,Wesley Barnes,Flexible Job Shop Scheduling by Tabu Search.International Journal of Computers and Industrial Engineering[J].1996,Vol.30,No.4,p983-997
[5]范玉顺,曹军威.多代理系统理论、方法与应用[M].清华大学出版社,1999
[6]Glover F.Future paths for integer programming and links to artificial intelligence.Computers and Operations Research[J],1986,p533-549
[7]Taillard E.Some efficient heuristic methods for the flow shop sequencing problem.European Operation Research[J],1990,p47-65
[8]Chambers J B,Barnes J W.Tabu search for the flexible-routing job shop problem Austin,Technical Report Series ORP 96-10,Department of Mechanical Engineering.The University of Texas at Austin,1996
[9]王伟.人工神经网络原理[M].北京:北京航空航天大学出版社,1995
[10]Foo Y S,Takefuji Y.Integer linear programming nenural networks for job-shop scheduling.IEEE Int Conf on NNS,San Diego,1998
[11]陈萍,郭金锋.对Hopfield神经网络求解TSP的研究.北京邮电大学学报[J],1999,22(2),p58-61
[12]王潮,宣国荣.人工神经网络求解JSP新方法.计算机应用与软件[J],2001,18(4),p59-64
[13]谢胜利,董金祥,黄强.基于遗传算法的车间作业调度问题求解.计算机工程与应用[J],2002,10,p79-82
[14]Croee F D,Tadei R,Volta G.A genetic algorithm for the Job Shop problem.Computer Ops.Res[J].,1995,22(1),p15-24
[15]Young Hae Lee,Chan Seok Jeong,Chiung Moon.Advanced planning and scheduling with outsourcing in manufacturing supply chain.Computers &Industrial engineering[J],2002,43,p351-374
[16]Van Laarhoven,et al.Job shop scheduling by simulated annealing.Operations Research[J],1992,40,p113-125
[17]郑璐,顾幸生.不确定条件下的含存储时间有限的Flow Shop生产调度.系统工程理论方法应用[J],2003,12(1),p91-96
[18]Sergio Cavalieri,Paolo Gaiardelli.Hybrid genetic algorithms for a multiple objective scheduling problem. Journal of Intelligent Manufacturing[J], 1998, 9,p361-367
[19] C.H.Dagli, K.Schierholt. Evaluating the performance of the genetic neuro-scheduler using constant as well as changing croosover and mutation rates.Computers and engineering[J], 1997,33, p253-256.
[20] C.H.Dagli, S.Sitisathanchai. Genetic neuro-scheduler: A new approach for job shop scheduling. Int.J. Production Economist[J],1995,41, p135-145
[21] Tadahiko Murata, Hisao Ishibuchi, Hideo Tanka. Multi-objective genetic algorithm and its application to flow shop scheduling. Computers and Engineering[J], 1996,30(4), p957-968.
[22] S.G.Ponnambalam, V.Ramkumar, N.Jawahar. A multi-objective genetic algorithm for job shop scheduling[J]. production planning & control ,2001,12(8),p764-774
[23] David C, Bushee, Joseph A. A bi-directional scheduling approach for job shops.Int.J.Prod.Res[J], 1999,37(16), p3823-3837.
[24] Nelson.R.T, Holloway.C.A, Wong.R.M. Centralized scheduling and priority implamentation heuristics for a dynamic job shop model with due dates and variable processing time[J]. AIE Transaction, 1977,19, p95-102.
[25] Yamamoto, NofS.Y. Scheduling/rescheduling in the manufacturing operation system environment. International Journal of Production Research[J],1985,23,p705-722.
[26] Church L, Uzsoy R. Analysis of periodic and event-driven rescheduling policies in dynamic shops[J]. International journal of Computer Integrated Manufacturing,1992,5(3),p153-163.
[27] Grabot.B, L.Geneste. Dispatching rules in scheduling: a fuzzy approach. International Journal of Production Research[J],1994,32(4), p903-915.
[28] Tsujimura.Y, S.Park, S.Chang. An effective method for solving flow shop scheduling problems with fuzzy processing times. Computer and Industrial Engineering[J], 1993,25,p239-243.
[29] Tadahiko Murata, Misuo Gen, Hisao Ishibuchi. Multi-Objective Scheduling with Fuzzy Due date. Computer and Industrial Engineering[J], 1998,35, p439-442.
[30] Masatoshi Sakawa, Tetsuya Mori. An effective genetic algorithm for job shop scheduling problems with fuzzy processing time and fuzzy due date. Computers and Industrial Engineering[J],1999,36, p325-341
[31] 李凡. 模糊信息处理系统, 北京：北京大学出版社, 1998
[32] Zadeh.L.A, Fuzzy sets, Information and Control[J], 1965, 8,p338-353
[33] MaCahonC.S, Lee.E.S. Fuzzy Job Sequencing for Flow Shop. European Journal of Operational Research[J].1992,62, p294-301
[34]Fortemps.P.Job Shop Scheduling with Imprecise Durations:A Fuzzy Approach.IEEE Trans on Fuzzy Systems[J].1997,5(4),p557-569
[35]汪应洛.系统工程理论、方法与应用[M].高等教育出版社,1998
[36]王凌.车间调度及其遗传算法[M].清华大学出版社,2003,p90-94
[37]Masatoshi Sakawa,Ryo Kubota.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms.European Journal of Operational Research[[J].2000,120,p393-407
[38]Bortonlan.G,Degani.R.A Review of Some Methods for Ranking Fuzzy Subsets.Fuzzy Sets and Systems[J].1985,15,p1-19
[39]Dubois.D,Prade.H.The Mean Value of a Fuzzy Number.Fuzzy Sets and Systems[J].1987,24,p279-300
[40]Forremps.P,Roubens M.Ranking and Defuzzification Methods Based Area Compensation.Fuzzy Sets and Systems.1996,82,p319-330
[41]Holland.Adaptation in nature and artificial systems[M].MIT Press,1992
[42]De Jong.K.An analysis of the behavior of a class of genetic adaptive systems.PhD Dissertation,University of Michigan,No.76-9381,1975
[43]韩祯祥,文福栓.模拟进化优化方法及其应用—遗传算法,计算机科学[J],1995,22(2),p47-57
[44]D.E.Goldberg,Genetic algorithms in search optimization and machine learning[M].Addison-Wesley,1989
[45]Goldberg.Genetic algorithms in search Optimization and Machine Learning[M].Addison-Wesley,1989
[46]程翔宇.基于遗传算法的多目标动态作业车间调度及应用研究.合肥工业大学硕士学位论文,2006.4
[47]谢胜利.求解JSP的遗传算法中不可行调度的方案.计算机集成制造系统[J],2002,8(11),p902-906
[48]刘勇,康立山,陈毓屏.非数值并行算法(第二册).遗传算法[M],科学出版社,1998
[49]M.Gen,R.Cheng.Genetic Algorithms and Engineering Design[M],John Wiley & Sons,New York,1997
[50]李歧强.生产过程的智能决策与调度[M].浙江杭州:浙江大学控制系,1998
[51]孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.控制与决策[J],1996,11(4),p425-431
[52]Schwefel.H.P.Numerical Optimization of Computer Models[M].Birkhauser,1977
[53]Schwefel H P.Evolution and Optimum Seeking[M].John Wiley & Sans,1995
[54]David.C,Bushee,Joseph.Abi-directional scheduling approach for job shops.Int.J.Prod.Res[J],1999,37(16),p3823-3837
[55]陈廷.决策分析[M].北京:科学出版社,1987
[56]徐光辉.运筹学基础手册[M].北京:科学出版社,1999.
[57]沈荣芳.王永安.运筹学[M],上海:同济大学出版社,1997
[58]Tadahiko Murata,Hisao Ishibuchi,Hideo Tanka.Multi-objective genetic algorithm and its application to flow shops scheduling.Computers and Engineering[J],1996,30(4),p957-968.
[2][日]玄光男,程润伟著.江定伟,唐加福,黄敏译.遗传算法与工程设计[M].北京:科学出版社,2000
[3]Chaitanya Swamy,Sachin Jain.Scheduling Algorithm B.Tech.Project Report,1999
[4]John B,Chambers,Wesley Barnes,Flexible Job Shop Scheduling by Tabu Search.International Journal of Computers and Industrial Engineering[J].1996,Vol.30,No.4,p983-997
[5]范玉顺,曹军威.多代理系统理论、方法与应用[M].清华大学出版社,1999
[6]Glover F.Future paths for integer programming and links to artificial intelligence.Computers and Operations Research[J],1986,p533-549
[7]Taillard E.Some efficient heuristic methods for the flow shop sequencing problem.European Operation Research[J],1990,p47-65
[8]Chambers J B,Barnes J W.Tabu search for the flexible-routing job shop problem Austin,Technical Report Series ORP 96-10,Department of Mechanical Engineering.The University of Texas at Austin,1996
[9]王伟.人工神经网络原理[M].北京:北京航空航天大学出版社,1995
[10]Foo Y S,Takefuji Y.Integer linear programming nenural networks for job-shop scheduling.IEEE Int Conf on NNS,San Diego,1998
[11]陈萍,郭金锋.对Hopfield神经网络求解TSP的研究.北京邮电大学学报[J],1999,22(2),p58-61
[12]王潮,宣国荣.人工神经网络求解JSP新方法.计算机应用与软件[J],2001,18(4),p59-64
[13]谢胜利,董金祥,黄强.基于遗传算法的车间作业调度问题求解.计算机工程与应用[J],2002,10,p79-82
[14]Croee F D,Tadei R,Volta G.A genetic algorithm for the Job Shop problem.Computer Ops.Res[J].,1995,22(1),p15-24
[15]Young Hae Lee,Chan Seok Jeong,Chiung Moon.Advanced planning and scheduling with outsourcing in manufacturing supply chain.Computers &Industrial engineering[J],2002,43,p351-374
[16]Van Laarhoven,et al.Job shop scheduling by simulated annealing.Operations Research[J],1992,40,p113-125
[17]郑璐,顾幸生.不确定条件下的含存储时间有限的Flow Shop生产调度.系统工程理论方法应用[J],2003,12(1),p91-96
[18]Sergio Cavalieri,Paolo Gaiardelli.Hybrid genetic algorithms for a multiple objective scheduling problem. Journal of Intelligent Manufacturing[J], 1998, 9,p361-367
[19] C.H.Dagli, K.Schierholt. Evaluating the performance of the genetic neuro-scheduler using constant as well as changing croosover and mutation rates.Computers and engineering[J], 1997,33, p253-256.
[20] C.H.Dagli, S.Sitisathanchai. Genetic neuro-scheduler: A new approach for job shop scheduling. Int.J. Production Economist[J],1995,41, p135-145
[21] Tadahiko Murata, Hisao Ishibuchi, Hideo Tanka. Multi-objective genetic algorithm and its application to flow shop scheduling. Computers and Engineering[J], 1996,30(4), p957-968.
[22] S.G.Ponnambalam, V.Ramkumar, N.Jawahar. A multi-objective genetic algorithm for job shop scheduling[J]. production planning & control ,2001,12(8),p764-774
[23] David C, Bushee, Joseph A. A bi-directional scheduling approach for job shops.Int.J.Prod.Res[J], 1999,37(16), p3823-3837.
[24] Nelson.R.T, Holloway.C.A, Wong.R.M. Centralized scheduling and priority implamentation heuristics for a dynamic job shop model with due dates and variable processing time[J]. AIE Transaction, 1977,19, p95-102.
[25] Yamamoto, NofS.Y. Scheduling/rescheduling in the manufacturing operation system environment. International Journal of Production Research[J],1985,23,p705-722.
[26] Church L, Uzsoy R. Analysis of periodic and event-driven rescheduling policies in dynamic shops[J]. International journal of Computer Integrated Manufacturing,1992,5(3),p153-163.
[27] Grabot.B, L.Geneste. Dispatching rules in scheduling: a fuzzy approach. International Journal of Production Research[J],1994,32(4), p903-915.
[28] Tsujimura.Y, S.Park, S.Chang. An effective method for solving flow shop scheduling problems with fuzzy processing times. Computer and Industrial Engineering[J], 1993,25,p239-243.
[29] Tadahiko Murata, Misuo Gen, Hisao Ishibuchi. Multi-Objective Scheduling with Fuzzy Due date. Computer and Industrial Engineering[J], 1998,35, p439-442.
[30] Masatoshi Sakawa, Tetsuya Mori. An effective genetic algorithm for job shop scheduling problems with fuzzy processing time and fuzzy due date. Computers and Industrial Engineering[J],1999,36, p325-341
[31] 李凡. 模糊信息处理系统, 北京：北京大学出版社, 1998
[32] Zadeh.L.A, Fuzzy sets, Information and Control[J], 1965, 8,p338-353
[33] MaCahonC.S, Lee.E.S. Fuzzy Job Sequencing for Flow Shop. European Journal of Operational Research[J].1992,62, p294-301
[34]Fortemps.P.Job Shop Scheduling with Imprecise Durations:A Fuzzy Approach.IEEE Trans on Fuzzy Systems[J].1997,5(4),p557-569
[35]汪应洛.系统工程理论、方法与应用[M].高等教育出版社,1998
[36]王凌.车间调度及其遗传算法[M].清华大学出版社,2003,p90-94
[37]Masatoshi Sakawa,Ryo Kubota.Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms.European Journal of Operational Research[[J].2000,120,p393-407
[38]Bortonlan.G,Degani.R.A Review of Some Methods for Ranking Fuzzy Subsets.Fuzzy Sets and Systems[J].1985,15,p1-19
[39]Dubois.D,Prade.H.The Mean Value of a Fuzzy Number.Fuzzy Sets and Systems[J].1987,24,p279-300
[40]Forremps.P,Roubens M.Ranking and Defuzzification Methods Based Area Compensation.Fuzzy Sets and Systems.1996,82,p319-330
[41]Holland.Adaptation in nature and artificial systems[M].MIT Press,1992
[42]De Jong.K.An analysis of the behavior of a class of genetic adaptive systems.PhD Dissertation,University of Michigan,No.76-9381,1975
[43]韩祯祥,文福栓.模拟进化优化方法及其应用—遗传算法,计算机科学[J],1995,22(2),p47-57
[44]D.E.Goldberg,Genetic algorithms in search optimization and machine learning[M].Addison-Wesley,1989
[45]Goldberg.Genetic algorithms in search Optimization and Machine Learning[M].Addison-Wesley,1989
[46]程翔宇.基于遗传算法的多目标动态作业车间调度及应用研究.合肥工业大学硕士学位论文,2006.4
[47]谢胜利.求解JSP的遗传算法中不可行调度的方案.计算机集成制造系统[J],2002,8(11),p902-906
[48]刘勇,康立山,陈毓屏.非数值并行算法(第二册).遗传算法[M],科学出版社,1998
[49]M.Gen,R.Cheng.Genetic Algorithms and Engineering Design[M],John Wiley & Sons,New York,1997
[50]李歧强.生产过程的智能决策与调度[M].浙江杭州:浙江大学控制系,1998
[51]孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.控制与决策[J],1996,11(4),p425-431
[52]Schwefel.H.P.Numerical Optimization of Computer Models[M].Birkhauser,1977
[53]Schwefel H P.Evolution and Optimum Seeking[M].John Wiley & Sans,1995
[54]David.C,Bushee,Joseph.Abi-directional scheduling approach for job shops.Int.J.Prod.Res[J],1999,37(16),p3823-3837
[55]陈廷.决策分析[M].北京:科学出版社,1987
[56]徐光辉.运筹学基础手册[M].北京:科学出版社,1999.
[57]沈荣芳.王永安.运筹学[M],上海:同济大学出版社,1997
[58]Tadahiko Murata,Hisao Ishibuchi,Hideo Tanka.Multi-objective genetic algorithm and its application to flow shops scheduling.Computers and Engineering[J],1996,30(4),p957-968.