摘要
随着全球经济一体化和企业间竞争的愈演愈烈,改善企业内部生产管理的生产调度技术受到了高度的重视,目前已产生了大量关于生产调度技术的理论研究成果,但是这些研究成果大多只是理论研究,并没有应用到实际生产当中。该文在将遗传算法改进的基础上,对流水车间调度、混合流水车间调度和作业车间调度分别做了算法设计,并通过Flexsim进行了系统仿真,真实地呈现了改进遗传算法实现的车间调度过程和合理性。
该文首先对遗传算法做了大量的研究和分析,发现传统的遗传算法解决车间调度问题存在局部收敛和收敛概率偏低的问题,针对该问题提出了一种并行算法结构的改进遗传算法,该算法融入了动态自适应策略和混合启发式等方法,通过与传统遗传算法的对比验证了算法在保证局部搜索速度的前提下还尽可能的保证全局搜索,避免陷入局部最优,提高了最优率。
在应用改进的遗传算法基础上,针对流水车间调度、混合流水车间调度和作业车间调度分别给出了不同的算法实现方案,并在算法实现的过程中做了适当的调整和改进,然后通过对经典调度模型、汽车发动机车间模型和机车厂车间模型实例化验证了算法实现的效果。
最后实现了对流水车间调度、混合流水车间调度和作业车间调度的系统实现和Flexsim仿真,可动态地观察整个调度过程,进一步地证明了遗传算法在实际调度应用中的可行性和有效性。
该文提出的改进遗传算法改善了遗传算法中收敛概率低的问题,目标函数能满足客户对车间调度现实问题的需要。应用改进遗传算法实现的车间调度系统和仿真对实际生产有一定的指导作用。
Due to economic globalization and fierce competition in companies, optimizing shop scheduling of inner manufacturing management has played an important role. Now lots of theoretical investigation of shop scheduling has been done, however, most of them haven't been applied in practical production. This thesis has optimized the traditional Genetic Algorithm (GA) to solve Flow Shop Scheduling Problem (FSP), Hybrid Flow-shop Scheduling Problem (HFSP) and Job Shop Scheduling Problem (JSSP). Flexsim software is used to simulate these problems. The simulation results prove that applying Improved Genetic Algorithm (IGA) to solve the shop scheduling problem is feasible and robust.
Firstly, the thesis has improved upon the structure of GA to a parallel structure of algorithm aiming at the problem that GA is easy to run into local optima, appear premature convergence and has low probability of convergence after research and analysis. And the IGA, including dynamic self-adapting method and hybrid heuristic method, can search the global optimum rather than local optimum, and enhance the optimum rate based on fast searching rate.
Secondly, the thesis has solved FSP, HFSP and JSSP by different implementation methods of IGA and optimized the procedure. This algorithm has some better results by means of vefifying the problem of the benchmarks of shop scheduling problem, automobile engine model and locomotive model.
Finally, the thesis has established IGA procedure, designed a visual programming interface, and achieved dynamic simulation of Flexsim on FSP, HFSP and JSSP. The whole scheduling process of dynamic simulation can be observed, which proves the IGA feasible and efficient in practice.
IGA could improve the problem of low probability of convergence. Objective function could fulfill the need of client on the shop scheduling. The paper is of profound practical significance.
引文
[1]王凌.车间调度及其遗传算法.北京:清华大学出版社,2003.
[2]王小平,曹立明.遗传算法-理论、应用与软件实现.西安:西安交通大学出版社,2002.
[3]丁书斌.基于混合遗传算法的车间调度方法研究与应用:(硕士学位论文).大连:大连理工大学,2006.
[4]王万雷.制造执行系统(MES)若干关键技术研究:(博士学位论文).大连:大连理工大学,2005.
[5]Xing Yingjie,Chen Zhentong,Sun Jing etc.An Improved Adaptive Genetic Algorithm for Job-Shop Scheduling Problem.ICNC,2007:287-291.
[6]陈振同.基于改进遗传算法的车间调度问题研究与应用:(硕士学位论文).大连:大连理工大学,2007.
[7]Sambong Kim,Jungyoup Woo,Sungsik Park,et al.Integrated development of nonlinear process planning and simulation-based shop floor control.Proceedings of the 2002Winter Simulation Conference.Piscataway,NJ,USA,2002:1465-1468.
[8]程光,邬洪迈,陈永刚.工业工程与系统仿真.北京:冶金工业出版社,2007:200.
[9]唐恒永,赵传立.排序引论.北京:科学出版社,2002.
[10]吴云高.基于遗传算法的车间调度方法及应用:(硕士学位论文).浙江工业大学,2002.
[11]Davis L.Handbook of genetic algorithm.New York:Van Nostrand Reinhold,1991.
[12]何燕.基于遗传算法的车间调度优化及其仿真:(硕士学位论文).武汉:武汉理工大学,2006.
[13]邝航宇,金晶,苏勇。自适应遗传算法交叉变异算子的改进.计算工程与应用.2006.12:93-96.
[14]金志勇.基于遗传算法的车间调度系统研究:(硕士学位论文).武汉:武汉理工大学,2006.
[15]黄明,王佳,梁旭.双阀值控制的遗传算法求解作业车间调度问题.计算机集成制造系统.2007,13(2):329-332.
[16]王凌,郑大钟,李清生.混沌优化方法的研究进展.计算技术与自动化.2001,20(1):1-5.
[17]欧阳珍.基于遗传算法的车间调度研究与应用:(硕士学位论文).杭州:浙江大学,2004.
[18]吴怡,刘民,吴澄.JSSP基本约束特点分析及调度算法.清华大学学报(自然科学版).2004.44(10):1380-1383.
[19]刘世平,张洁,饶运清,李培根.分布式车间管理控制系统研究.中国机械工程.2001,12(12):1432-1435.
[20]李斌,钟毅芳,肖人彬.基于人机集成的生产过程管理系统研究与开发.工业工程与管理.2004,3(5):58-62.
[21]余舟毅,陈宗基,周锐.基于遗传算法的动态资源调度问题研究.控制与决策.2004,19(11):1309-1311.
[22]Miltenburg G L.Changing MRP' s Costing Procedures to Suite JIT.Production and Inventory Management J.1990,2:77-83.
[23]ChudaBasnet a,Joe H.Mize.Scheduling and Control of Flexible Manufacturing Systems:A Critical Review.Int.J.of Computer Integrated Manufacturing.1994,7(6):335-340.
[25]Johnson S M.Optimal Two- and Three- Stage Production Scheduling with Set-up Times Included.Naval Research Logistics Quarterly.1954,1:61-68.
[26]Story A E,Wagner H M.Computational Experience whit Integer Programming for Job-shop Schdeling.Industrial Scheduling,Chap.14,Prentice-Hall,1963.
[27]Gavet J W.Three Heuristic Rules for Sequencing Jobs to a Single Production Facility.Mgmt.Sci.,1965,11:B166-B176.
[28]Panwalker S,Wafik I.A Survey of Scheduling.Ops.Res.1977,25(1):45-61.
[29]张超勇,饶运清,李培根等.求解作业车间调度问题的一种改进遗传算法.计算机集成制造系统.2004:10(8).
[30]Nakano R.Conventional genetic algorithm for job shop problems.Proceedings of the Fourth International Conference on Genetic Algorithms,1991:474-479.
[31]Nowicki E,Smutnicki C.A fast taboo search algorithm for the job shop problem.Management Science.1996,42(6):797-813.
[32]Monte Z,Brian D,Eugene D et al.Scheduling and Rescheduling.Intelligent Scheduling,Morgan Kaufmann,ed:Michael B.Morgan,1994:241-256.
[33]Pascal Y H.Scheduling and Packing in the Constraint Language CC(FD).Intelligent Scheduling,Morgan Kaufmann,ed:Michael B.Morgan,1994:137-168.
[34]Kirkpatric S,Gelatt C D,Vecchi M P.Operational by simulated annealing.Science.1983,220:671-680.
[35]RoyChowdhury P,Singh Y P,Chansarkar R A.Hybridization of gradient decent algorithms with dynamic tunneling methods for global optimization.IEEE Transactions on Systems,Man,and Cybernetics.2000,30(3):384-390.
[36]Reeves C R.A genetic algorithm for flow shop sequencing.Computers and Operations Research.1995,22(1):5-13.
[37]Croce F D,Tadei R,Volta G.A genetic algorithm for the job-shop problem.Computers and Operations Research.1995,22(1):15-24.
[38]刘烨,季石磊.C#编程及应用程序(第二版).北京:清华大学出版社,2007.
[39]郑阿奇.SQL Server实用教程.北京:电子工业出版社,2004.
[40]薛家兵,鄂明成.基于Flexsim仿真的FMS车间级控制系统开发.中国制造业信息化.2007.
[41]林鑫.基于Flexsim的混合生产线投产方案的研究.湖北工业大学学报.2008.
[42]李海真,许维胜,王中杰.基于MAS的车间调度控制系统研究.计算机辅助工程.2004,13(3):37-41.