基于混合遗传算法的有限能力作业车间调度
|
摘要
随着世界进入信息化时代,制造业所处的环境不断改变,大多数企业的生产模式己由过去的大批量生产转化为单件小批生产。在这种环境下,企业如何运用有限的资源,快速响应客户需求,提高效率,降低成本,保证按时交货,已成为制造企业在竞争中生存的一个重要条件。车间调度是制造系统生产管理的核心,它对于提高产品质量、降低成本、提高效率等生产管理的各个方面都起着至关重要的作用。车间调度已成为制造业生产领域中研究的热点问题之一,但由于车间调度具有动态随机性、计算复杂性的特点,至今尚未出现一套系统的方法和理论。探求有效的调度方法与优化技术,对于提高制造企业的现代化水平具有重要的理论意义和实用价值。
本文在综合研究国内外关于车间调度问题的基础上,考虑现行作业车间运作特点,对作业车间的生产调度问题进行了深入系统的研究。首先,针对经典作业车间调度问题的局限性,结合车间生产的实际情况,研究建立了有限能力作业车间调度模型。其次,针对传统遗传算法存在过早收敛及后期搜索效率低的问题,设计了混合遗传算法,该算法有效融合多种群遗传算法与模拟退火算法的优点,对该算法在有限能力作业车间调度优化的具体应用进行了详细地设计,并给出问题求解的仿真实验结果。最后基于有限能力作业车间调度模型和混合遗传算法,设计开发了有限能力作业车间调度系统。
Wiht the word entering informationization time, the environment which the manufacturing industry locates unceasingly changes, Majority enterprise's production pattern transformed by the past mass production as the single-piece and small-batch production.Nnder this kind of production environment, how the enterprise utilize the limited resources to fast response customer demand, reduce the production cost, guarante delivers on time, becomes the manufacture enterprise an important condition which survives in the competition. The job-shop scheduling is the core of manufacture productionsystem,it can improve the production efficiencyand product quality, reduce the cost, and so on .Therefore, the workshop scheduling is one of hot topics which in the manufacturing production studies. Because the workshop scheduling has the dynamic randomness, the computation complex characteristic, at present not yet appears the effective theory solves the workshop scheduling problem. Seeks the effective dispatch method and the optimization techniques, has the important theory significance and the practical value regarding the enhancement manufacture enterprise's modernized level.
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.Firstly,direct against the limitation of classical job-shop scheduling, combine the actual conditions of the workshop, deployment model of finite capacity job-shop scheduling. Secondly, In order to avoid permature convergence and slow convergent speed at later evolution process of traditional genetic algorithm,a hybrid algorithm was proposed to solve finite capacity job-shop scheduling problems. This algorith is effectively combined with the merits of simulated annealing and multigroup genetic, and simulation results validate the effectiveness of the proposed algorithm. Finally, develop the finite capacity job-shop scheduling system.
本文在综合研究国内外关于车间调度问题的基础上,考虑现行作业车间运作特点,对作业车间的生产调度问题进行了深入系统的研究。首先,针对经典作业车间调度问题的局限性,结合车间生产的实际情况,研究建立了有限能力作业车间调度模型。其次,针对传统遗传算法存在过早收敛及后期搜索效率低的问题,设计了混合遗传算法,该算法有效融合多种群遗传算法与模拟退火算法的优点,对该算法在有限能力作业车间调度优化的具体应用进行了详细地设计,并给出问题求解的仿真实验结果。最后基于有限能力作业车间调度模型和混合遗传算法,设计开发了有限能力作业车间调度系统。
Wiht the word entering informationization time, the environment which the manufacturing industry locates unceasingly changes, Majority enterprise's production pattern transformed by the past mass production as the single-piece and small-batch production.Nnder this kind of production environment, how the enterprise utilize the limited resources to fast response customer demand, reduce the production cost, guarante delivers on time, becomes the manufacture enterprise an important condition which survives in the competition. The job-shop scheduling is the core of manufacture productionsystem,it can improve the production efficiencyand product quality, reduce the cost, and so on .Therefore, the workshop scheduling is one of hot topics which in the manufacturing production studies. Because the workshop scheduling has the dynamic randomness, the computation complex characteristic, at present not yet appears the effective theory solves the workshop scheduling problem. Seeks the effective dispatch method and the optimization techniques, has the important theory significance and the practical value regarding the enhancement manufacture enterprise's modernized level.
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.Firstly,direct against the limitation of classical job-shop scheduling, combine the actual conditions of the workshop, deployment model of finite capacity job-shop scheduling. Secondly, In order to avoid permature convergence and slow convergent speed at later evolution process of traditional genetic algorithm,a hybrid algorithm was proposed to solve finite capacity job-shop scheduling problems. This algorith is effectively combined with the merits of simulated annealing and multigroup genetic, and simulation results validate the effectiveness of the proposed algorithm. Finally, develop the finite capacity job-shop scheduling system.
引文
[1] 朱剑英. 现代制造系统模式、建模方法及关键技术的新发展. 机械工程学报,2000,36(8):1-5
[2] 何霆,刘飞,马玉林等.车间生产调度问题研究.机械工程学报,2000,36(5):97-102
[3] 欧阳珍.基于遗传算法的车间调度研究与应用:[硕士学位论文]. 杭州:浙江大学,2004
[4] Graves S.A review of production scheduling.. Operations Research ,1981,29(4):646-675
[5] 潘全科.车间调度问题研究.聊城大学学报(自然科学版) ,2004,17(1):9-11
[6] I.J.Chen, C. H.Chung.Sequential modeling of the planning problems of flexible manufacturing systems. J. of the Operational Research Society, 1996,47:1216 -1228
[7] 郝文育,李亚白,王宁生.一种启发式车间作业调度算法的研究与应用.机械科学与技术,2005,24(7):861-864
[8] B.Gershwin et al.A control perspective on recent trends in manufacturing systems.IEEE Control Systems, Apr.,1986:3~15
[9] 胡瑜,陈涛.专家系统在生产制造系统(MES)中的应用.冶金设备 ,2005 152(4):43-46
[10] 熊惠明,徐国华.用 Petri 网实现 FMS 负载平衡调度.先进制造技术 ,2004 23(3):18-20
[11] 王国新,宁汝新.基于仿真的调度规则组合决策研究.北京理工大学学报,2006 26(7):598-601
[12] 耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究.计算机集成制造系统—CIMS,2002,8 (8):616-620
[13] 熊锐,陈浩勋,胡保生.一种生产计划与车间调度的集成模型及其拉氏松弛求解法.西安电子科技大学学报,1996,23 (4): 509--516
[14] 姬耀锋,张德贤.约束满足自适应神经网络求解车间调度问题.计算机与数学工程,2005 ,34(9):22-24
[15] Foo Y S, Takefuji Y.Integer linear programming nenural networks for job-shop scheduling. In: IEEE Int Conf on NNS,San Diego,1998
[16] 黄明,宫鹏,梁旭.启发式 Hopfield 神经网络在车间调度中的应用.大连铁道学院学报 ,2004,25(1):44-47
[17] 王万良,吴启迪,徐新黎.基于 Hopfield 神经网络的作业车间生产调度方法.自动化学报,2005,5(9):838-844
[18] 孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.控制与决策,1996,11 (4):425 一 431
[19] 谢胜利,董金祥,黄强.基于遗传算法的车间作业调度问题求解.计算机工程与应用,2002,10:79-82
[20] Croee F D,Tadei R,Volta G. A genetic algorithm for the Job Shop problem.Computer Ops.Res.,1995,22 (1):15-24
[21] Young hae lee, Chan seok jeong, Chiung Moon.Advanced planning and scheduling without sourcing in manufacturing supply chain.Computers & industrial engineering, 2002, 46:351-374
[22] 潘全科,孙志峻,朱剑英.基于遗传算法的作业车间双向调度优化问题.中国机械工程,2003 ,14 (1) :65-67
[23] 杨晓梅,曾建潮.遗传算法求解柔性 job-shop 调度问题.控制与决策,2004,19(10):1197-1200
[24] 余琦玮,赵亮,潘双夏.基于遗传算法的柔性作业车间调度优化.组合机床与自动化加工技术,2004,4:32-34.
[25] 姜思杰,徐晓飞,李全龙.基于遗传优化算法求解作业车间调度问题.计算机集成制造系统 ,2002 ,8(3):229-232
[26] 戚海英,李瑞,宋旭东.求解Job-Shop调度问题的禁忌搜索算法的研究. 计算机工程与科学. 2006,28(8):75-77
[27] 谢丽芳,费跃农.一种基于模拟退火算法的作业车间调度算法. 中国制造业信息化, 2006,35(9):50-53
[28] 陈雄,杨凤霞. Flow-shop调度问题的自适应模拟退火算法.控制理论与应用,2003,20(3)445-448
[29] 郑璐,顾幸生.不确定条件下的含存储时间有限的 flowshop 生产调度.系统工程理论方法应用,2003,12(1):91-96
[30] 赵良辉,邓飞其.用于作业车间调度的模拟退火算法. 制造业自动化,2006 ,28(3):10-13
[31] Dorigo M, Bonabeau E, Theraulaz G.Ant algorithm and stigmergy.Futer Generation Computer Systems, 2000, 16:851-871.
[32] Colorni A, Dorigo M, et al.Ant system for job shop scheduling.Belgian Journal of Operations Research Statistics and Computer Science, 1994, 34: 39-53.
[33] 刘民,孙元凯. TS+BS 混合算法及在 Job Shop 调度问题上的应用.清华大学学报:自然科学版,2002,42 (3 ) :424 -426
[34] 何霆,梁办平.一种新的 FMS 混合调度算法.控制理论与应用,2000 ,17(6):894-898
[35] 李钢,李金勇.混合遗传算法求解车间作业调度问题.天津大学学报:自然科学与工程技术版,2003,36 (2 ):239-242
[36] 李国富.一种基于遗传算法的 Job Shop 作业排序方法.宁波大学学报(理工版),1998,11(3),47-49
[37] 王常青,操云甫,戴国忠.用双向收敛蚁群算法解作业车间调度问题.计算机集成制造系统,2004,10 (7):820-824
[38] 饶运清,谢畅,李淑霞.基于多 Agent 的 Job Shop 调度方法研究.中国机械工程.2004,15(10):873-877
[39] 徐新黎,吴启迪,王万良.基于Hopfield神经网络的作业车间生产调度方法.自动化学报,2002,28 (5):839-844
[40] 周万坤,朱剑英,孙志俊.基于工作流技术的作业车间调度研究.南京航空航天大学学报,2004, 36 (1):125-129
[41] 王凌,车间调度及其遗传算法,清华大学出版社,2003 年 5 月第 1 版.
[42] 陈雄,李海刚,吴启迪.基于遗传算法的 Job-shop 调度问题研究.同济大学学报,2002, 30(1):88-91
[43] 金志勇.基于遗传算法的车间调度问题研究:[硕士学位论文].武汉:武汉理工大学,2006
[44] 孙艳丰,郑加齐,王德兴.基于遗传算法的约束优化方法评述.北京交通大学学报,2000,24(6):14-19
[45] 吴志远,邵惠鹤,吴欣余.遗传退火进化算法[J] .上海交通大学学报,1997,31(12):69-71
[46] 周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法.清华大学学报,1998,38(3):93-95
[47] 许晋.基于遗传模拟退火算法的生产调度过程中工作量规划[硕士学位论文].福州:福州大学, 2005
[48] 蔡良伟,张基宏,李霞作业车间调度问题的多种群遗传算法.电子学报,2005,33(6)991-994
[2] 何霆,刘飞,马玉林等.车间生产调度问题研究.机械工程学报,2000,36(5):97-102
[3] 欧阳珍.基于遗传算法的车间调度研究与应用:[硕士学位论文]. 杭州:浙江大学,2004
[4] Graves S.A review of production scheduling.. Operations Research ,1981,29(4):646-675
[5] 潘全科.车间调度问题研究.聊城大学学报(自然科学版) ,2004,17(1):9-11
[6] I.J.Chen, C. H.Chung.Sequential modeling of the planning problems of flexible manufacturing systems. J. of the Operational Research Society, 1996,47:1216 -1228
[7] 郝文育,李亚白,王宁生.一种启发式车间作业调度算法的研究与应用.机械科学与技术,2005,24(7):861-864
[8] B.Gershwin et al.A control perspective on recent trends in manufacturing systems.IEEE Control Systems, Apr.,1986:3~15
[9] 胡瑜,陈涛.专家系统在生产制造系统(MES)中的应用.冶金设备 ,2005 152(4):43-46
[10] 熊惠明,徐国华.用 Petri 网实现 FMS 负载平衡调度.先进制造技术 ,2004 23(3):18-20
[11] 王国新,宁汝新.基于仿真的调度规则组合决策研究.北京理工大学学报,2006 26(7):598-601
[12] 耿兆强,邹益仁.基于遗传算法的作业车间模糊调度问题的研究.计算机集成制造系统—CIMS,2002,8 (8):616-620
[13] 熊锐,陈浩勋,胡保生.一种生产计划与车间调度的集成模型及其拉氏松弛求解法.西安电子科技大学学报,1996,23 (4): 509--516
[14] 姬耀锋,张德贤.约束满足自适应神经网络求解车间调度问题.计算机与数学工程,2005 ,34(9):22-24
[15] Foo Y S, Takefuji Y.Integer linear programming nenural networks for job-shop scheduling. In: IEEE Int Conf on NNS,San Diego,1998
[16] 黄明,宫鹏,梁旭.启发式 Hopfield 神经网络在车间调度中的应用.大连铁道学院学报 ,2004,25(1):44-47
[17] 王万良,吴启迪,徐新黎.基于 Hopfield 神经网络的作业车间生产调度方法.自动化学报,2005,5(9):838-844
[18] 孙艳丰,王众托.遗传算法在优化问题中的应用研究进展.控制与决策,1996,11 (4):425 一 431
[19] 谢胜利,董金祥,黄强.基于遗传算法的车间作业调度问题求解.计算机工程与应用,2002,10:79-82
[20] Croee F D,Tadei R,Volta G. A genetic algorithm for the Job Shop problem.Computer Ops.Res.,1995,22 (1):15-24
[21] Young hae lee, Chan seok jeong, Chiung Moon.Advanced planning and scheduling without sourcing in manufacturing supply chain.Computers & industrial engineering, 2002, 46:351-374
[22] 潘全科,孙志峻,朱剑英.基于遗传算法的作业车间双向调度优化问题.中国机械工程,2003 ,14 (1) :65-67
[23] 杨晓梅,曾建潮.遗传算法求解柔性 job-shop 调度问题.控制与决策,2004,19(10):1197-1200
[24] 余琦玮,赵亮,潘双夏.基于遗传算法的柔性作业车间调度优化.组合机床与自动化加工技术,2004,4:32-34.
[25] 姜思杰,徐晓飞,李全龙.基于遗传优化算法求解作业车间调度问题.计算机集成制造系统 ,2002 ,8(3):229-232
[26] 戚海英,李瑞,宋旭东.求解Job-Shop调度问题的禁忌搜索算法的研究. 计算机工程与科学. 2006,28(8):75-77
[27] 谢丽芳,费跃农.一种基于模拟退火算法的作业车间调度算法. 中国制造业信息化, 2006,35(9):50-53
[28] 陈雄,杨凤霞. Flow-shop调度问题的自适应模拟退火算法.控制理论与应用,2003,20(3)445-448
[29] 郑璐,顾幸生.不确定条件下的含存储时间有限的 flowshop 生产调度.系统工程理论方法应用,2003,12(1):91-96
[30] 赵良辉,邓飞其.用于作业车间调度的模拟退火算法. 制造业自动化,2006 ,28(3):10-13
[31] Dorigo M, Bonabeau E, Theraulaz G.Ant algorithm and stigmergy.Futer Generation Computer Systems, 2000, 16:851-871.
[32] Colorni A, Dorigo M, et al.Ant system for job shop scheduling.Belgian Journal of Operations Research Statistics and Computer Science, 1994, 34: 39-53.
[33] 刘民,孙元凯. TS+BS 混合算法及在 Job Shop 调度问题上的应用.清华大学学报:自然科学版,2002,42 (3 ) :424 -426
[34] 何霆,梁办平.一种新的 FMS 混合调度算法.控制理论与应用,2000 ,17(6):894-898
[35] 李钢,李金勇.混合遗传算法求解车间作业调度问题.天津大学学报:自然科学与工程技术版,2003,36 (2 ):239-242
[36] 李国富.一种基于遗传算法的 Job Shop 作业排序方法.宁波大学学报(理工版),1998,11(3),47-49
[37] 王常青,操云甫,戴国忠.用双向收敛蚁群算法解作业车间调度问题.计算机集成制造系统,2004,10 (7):820-824
[38] 饶运清,谢畅,李淑霞.基于多 Agent 的 Job Shop 调度方法研究.中国机械工程.2004,15(10):873-877
[39] 徐新黎,吴启迪,王万良.基于Hopfield神经网络的作业车间生产调度方法.自动化学报,2002,28 (5):839-844
[40] 周万坤,朱剑英,孙志俊.基于工作流技术的作业车间调度研究.南京航空航天大学学报,2004, 36 (1):125-129
[41] 王凌,车间调度及其遗传算法,清华大学出版社,2003 年 5 月第 1 版.
[42] 陈雄,李海刚,吴启迪.基于遗传算法的 Job-shop 调度问题研究.同济大学学报,2002, 30(1):88-91
[43] 金志勇.基于遗传算法的车间调度问题研究:[硕士学位论文].武汉:武汉理工大学,2006
[44] 孙艳丰,郑加齐,王德兴.基于遗传算法的约束优化方法评述.北京交通大学学报,2000,24(6):14-19
[45] 吴志远,邵惠鹤,吴欣余.遗传退火进化算法[J] .上海交通大学学报,1997,31(12):69-71
[46] 周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法.清华大学学报,1998,38(3):93-95
[47] 许晋.基于遗传模拟退火算法的生产调度过程中工作量规划[硕士学位论文].福州:福州大学, 2005
[48] 蔡良伟,张基宏,李霞作业车间调度问题的多种群遗传算法.电子学报,2005,33(6)991-994