基于固定对象流水线作业班组调度问题研究
|
摘要
车间调度问题一直是研究的热点。而船舶制造企业是一个大型、单件、小批量生产系统、具有新产品多、更新换代快、约束条件多、生产组织复杂等特点。目前,传统的生产流水线在船舶制造企业生产组织中存在的突出问题是:生产计划管理模式落后、管理方法粗放、计划指导性差,从而导致生产周期长、误工误期严重、库存占用高。这显然与形势发展对船舶制造企业的要求不相适应。因此,根据行业激烈竞争的市场需求以及针对企业实际,深入研究造船企业车间内部的作业班组调度问题,具有重要的意义。
本文借鉴了关于车间调度的国内外最新研究成果,并提出了固定对象流水线这种生产模式及其主要原理;分别简单评述了实现固定对象流水线中四个关键问题:作业班组的组建、生产节拍的确定、作业班组的指派问题、设备资源冲突时的消解方法。针对作业班组的指派问题提出两个关键的数学问题,一是作业班组构建的数学模型,二是作业班组指派问题的数学模型。通过采用基于混合行为的蚁群算法,以“工期最短”为目标提出最优的指派方案。
为便于固定对象流水线在船舶类企业的应用,本文分析了南通中远船务分段车间生产作业组织的现状和存在的问题,将固定对象流水线组织方法应用于船务公司多分段车间调度问题中,并用相关算法得到最后作业班组的调度结果。最后,应用witness仿真的方法,验证了固定对象流水线下作业班组调度结果的可行性和有效性,这对我国船舶企业有效采用固定对象流水线具有一定的借鉴意义。
Production planning and scheduling problems is always the hot topic of research. Shipbuilding enterprise is a large, single, small batch production system, with more new products,quickly renewal, more constraints and more complex organization and so on. At present, the outstanding question of the traditional production flow line in shipbuilding enterprise is: the management mode of plan is backward, extensive management, planning guidance is poor, and thus lead to the production cycle is long, project period delayed seriously, occupancy of inventory is high. This is clearly can not meet with the requirements of the development of the situation which ask the shipbuilding enterprises. Thus, according to the demand of fierce competition in the market and the fact of corporate, it has important significance studies the problem of production planning and scheduling.
Based on the research findings both here and abroad,the paper proposed the fixed-location production line model and its main principles. This paper briefly comment on four key issues to carry out the fixed-location production flow line ,such as the formation of operating groups, production time, the assignment of groups and the resolution method when equipments or resources conflict. And then introduced two key issues of mathematical models of the organization the fixed-location production flow line: firstly, a mathematical model of operators’group; secondly, mathematical model of assignment problem. As "shortest duration" the goal,the paper use ant colony algorithm, get the optimal assignment program.
In order to use the fixed-location production line in ship building enterprises,introduced the basic situation of the plant, and analyzes the status and problems of the organization of hull subsection shop. Then, by collecting data of the production system,the method that organization of the fixed-location production flow line presented in this paper was successfully applied to hull curved block in shipbuilding. Finally, the application of simulation methods to verify obvious advantages of the fixed-location production flow line, further illuminate the feasibility and effectiveness,which is very important influence for the ship building enterprises in our country to implement fixed-location production line.
本文借鉴了关于车间调度的国内外最新研究成果,并提出了固定对象流水线这种生产模式及其主要原理;分别简单评述了实现固定对象流水线中四个关键问题:作业班组的组建、生产节拍的确定、作业班组的指派问题、设备资源冲突时的消解方法。针对作业班组的指派问题提出两个关键的数学问题,一是作业班组构建的数学模型,二是作业班组指派问题的数学模型。通过采用基于混合行为的蚁群算法,以“工期最短”为目标提出最优的指派方案。
为便于固定对象流水线在船舶类企业的应用,本文分析了南通中远船务分段车间生产作业组织的现状和存在的问题,将固定对象流水线组织方法应用于船务公司多分段车间调度问题中,并用相关算法得到最后作业班组的调度结果。最后,应用witness仿真的方法,验证了固定对象流水线下作业班组调度结果的可行性和有效性,这对我国船舶企业有效采用固定对象流水线具有一定的借鉴意义。
Production planning and scheduling problems is always the hot topic of research. Shipbuilding enterprise is a large, single, small batch production system, with more new products,quickly renewal, more constraints and more complex organization and so on. At present, the outstanding question of the traditional production flow line in shipbuilding enterprise is: the management mode of plan is backward, extensive management, planning guidance is poor, and thus lead to the production cycle is long, project period delayed seriously, occupancy of inventory is high. This is clearly can not meet with the requirements of the development of the situation which ask the shipbuilding enterprises. Thus, according to the demand of fierce competition in the market and the fact of corporate, it has important significance studies the problem of production planning and scheduling.
Based on the research findings both here and abroad,the paper proposed the fixed-location production line model and its main principles. This paper briefly comment on four key issues to carry out the fixed-location production flow line ,such as the formation of operating groups, production time, the assignment of groups and the resolution method when equipments or resources conflict. And then introduced two key issues of mathematical models of the organization the fixed-location production flow line: firstly, a mathematical model of operators’group; secondly, mathematical model of assignment problem. As "shortest duration" the goal,the paper use ant colony algorithm, get the optimal assignment program.
In order to use the fixed-location production line in ship building enterprises,introduced the basic situation of the plant, and analyzes the status and problems of the organization of hull subsection shop. Then, by collecting data of the production system,the method that organization of the fixed-location production flow line presented in this paper was successfully applied to hull curved block in shipbuilding. Finally, the application of simulation methods to verify obvious advantages of the fixed-location production flow line, further illuminate the feasibility and effectiveness,which is very important influence for the ship building enterprises in our country to implement fixed-location production line.
引文
[1]我国船舶工业与日韩差距缩小,《国防科技工业》,2007,2:70;
[2]徐学光:先进制造技术与造船业的发展,《自然杂志》,1999,21(2):92-98;
[3]陈强.中心制造船模式的研究与应用[博士论文].黑龙江哈尔滨工程大学.2001.
[4]徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展,2004,2: 257-267.
[5] Graves S. A review of production scheduling [J]. Operations Research, 1981, 29 (4):646-675.
[6]范路桥,常会友,林荣辉.有交货期的job-shop调度问题的改进倒排算法[J].计算机工程与应用,2005.4.46-50.
[7]张翠军,贺毅朝,王金山.敏捷制造中制造资源选择问题的遗传算法[J].计算机工程与应用,2007.43.216-218.
[8]宫俊,汪定伟.敏捷化产品开发中调度问题的研究[J].控制与决策,2002,17.704-709.
[9]李淑霞,单鸿波.基于敏捷制造单元的车间动态重构[J].计算机集成制造系统,2007,13(3):520-526.
[10]曹岩,郭颜军,赵汝嘉.面向敏捷制造生产调度与控制的基于MAS的制造系统[J].机床与液压,2007,35(9):85-90.
[11]王东成,何卫平,王邦龙.基于混合遗传算法的敏捷车间调度研究[J].航空精密制造技术,2006,42(1):43-47.
[12] Sergio Cavaliers, Paolo Gaiardelli. Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of Intelligent Manufacturing [J], 1998, 9:361-367.
[13] C H Dagli, S Sittisathanchai. Genetic neuro-scheduler: A new approach for job shop scheduling. Int. J. Production Economisc [J],2005, 41:135-145.
[14] S G Ponnambalam, V.Ramlcumar, N.Jawahar. A multiobjective genetic algorithm for job shop scheduling [J]. Production planning&control, 2001, 12(8):764-774.
[15]胡国强,康玲.敏捷制造生产方式下企业的成本控制[J].财会月刊(理论) ,2008,2.62-64.
[16]张维存,郑玉谬,吴晓丹.基于蚁群粒子群算法求解多目标柔性调度问题[J].计算机应用.2007.4:936-941.
[17]方叶祥,钱存华等.基于遗传禁忌算法的双资源约束下并行生产线调度研究[J].运筹与管理.2007.5:153-158.
[18]沈益民,范玉顺.带有跨工序约束的柔性job shop调度问题[J].计算机应用研究.2008.7:2023-2026.
[19]段丛斌,杨建军.敏捷制造车间控制系统及有限能力调度研究[J].机械加工与自动化.2002,7.4-6.
[20]姬耀锋,张德贤.约束满足自适应神经网络求解车间调度问题[J].计算机与数学工程,2005,34(9):22-24.
[21] M Garey, D Johnson. Strong NP-completeness results: motivation, examples and implication [J]. Journal of the ACM, 1978(25):499-508.
[22] S Arora. The approximability of NP-hard problems [J]. Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,ACM,1998:337-348.
[23] Wu Jian yu,He Xiao rong,Chen Bing zhen,QiuTong.A new continuous time MILP model for scheduling of multi-product batch plants[J].Journalof Chemical Industry & Engineering,2005,54 (9):1251-1256.
[24] E.W. Schuster and S.J. Allen. Reordering Algorithm for Complex Industrial Scheduling and Rescheduling[J]. Raw Material Management at Welch's, Computers&Che Inc. 1998, 28(5): 13-24.
[25] J. Roslof, I. Harjunkoski, J.B. rkqvist, S. Karlsson, and T. Westerlund. An MILP-based reordering algorithm for complex industrial scheduling and rescheduling [J]. Computers and Chemical Engineering, 2007, 25: 821–828.
[26]吴建显等.新的多产品间歇生产调度的MLIP模型[J].化工学报,2003,9:1251-1256.
[27] N.J. Nilsson. Problem-solving Methods in Artificial Intelligence [J]. New York: McGraw-Hill. 1971.
[28] Sadeh, N. and M. S. Fox. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem [J]. Artificial Intelligence, 1996, 86: 19-41.
[29] R. Tadei, M. Trubian, J. L. Avendano, F. Della Croce, and G Menga. Aggregate Planning and Scheduling in the Food Industry: A Case Study [J]. European Journal of Operational Research, 1995, 87(3): 564-573.
[30]乔佩利,张宏芳,李小平,高祥.FLOW SHOP调度问题的启发式算法[J].电机与控制学报.2008.1:109-112.
[31] A.Artiba and F. Riane. An Application of a Planning and Scheduling Multi-model Approach in the Chemical Industry [J].Computers in Industry, 1998, 36: 209-229.
[32] M. Zhang and C. Zhang. The Consensus of Uncertainties in Distributed Expert Systems. In: Proceedings of the First International Conference on Multi-Agent Systems[M]. Cambridge, Massachusetts: MIT Press, 1995.
[33]王珂.生产环境不确定条件下的生产调度优化[D].山东大学硕士学位论文,2005,7-8.
[34]李进,面向快速制造的车间调度策略研究[D].南京航空航天大学硕士学位论文,2004.
[35] M.Dorigo,L.M.Gambardella. Art colories for the traveling salesman problem. Biosystems,1997,43(2):73-81.
[36] E. G. Talbi, O. Roux,C. FonluPt,D. Robillard. Parallel ant colonies for the quadratic assignment problem. Future Generation Computer Systems 2001,17(4):441-449.
[37] Colorni A,et al. Ant system for job-shop scheduling[J].JORBEL,1994,34(1):39-53.
[38] Carlier J, Pinson E. Adjusting heads and tails for the job shop scheduling [J]. European Journal of Operational Research, 1994, 78(3):146-161.
[39] Walter J.Gutjahr. A Graph based Ant System and Its Convergence [J].Future Generation Computer Sytems, 2000(16):873-888.
[40] Thomas Stutzle, Marco Dorigo.A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms [J].IEEE Trans on Evolutionary Computation, 2002, 6 (4); 358-365.
[41]朱庆保.蚁群优化算法的收敛性分析[J].控制与决策,2006,21(7).
[42]王晓平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[43] T. Starkweather, D. Whitley, K. Mathias and S. McDaniel. Sequence Scheduling with Genetic Algorithms. In: Proceedings of the US/German Conference on New Directions for OR in Manufacturing, 1992:130-148.
[44] Cheng R,Gen M,Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms representation [J].Computers&Industrial Engineering, 1996,30(4):983-987.
[45]高家全,何桂霞等.解家纺企业生产计划问题的并行混合遗传算法[J] .系统仿真学报,2007, 9:3903-3905.
[46] Duffie N.A., Chitturi R., Mou J. Fault-tolerant heterarchical control of heterogeneous manufacturing system entities [J]. Journal of Manufacturing Systems, 1988, 7(4):315-327.
[47]潘家招等编著,现代生产管理学,清华大学出版社,1994.
[48]王承文:现代造船模式研究[博士论文].黑龙江哈尔滨工程大学.2006.
[49]季建华等编著.成组生产管理.陕西科学技术出版社,1995.
[50]张美玉等译.相似性理论的原理与实践,成组技术与生产现代化,1996No.1, 25-28.
[51] Black J.T. Cellular Manufacturing Systems, in Voss, C.A., ed. [M].Just-In-Time Manufacture,1987.
[52] Pena-Mora F, Anumba CJ, Solari J, et al. Conflict, Mitigation System for Collaborative Engineering Design, Analysis and Manufacturing, 2005,9(1):101-124.
[53] Kiriyama T. A Model Integration Framework for Cooperative Design [A]. Sriram D, Logcher R, FukudaS. Computer-Aided Cooperative Product Development[C].Berlin: Spring-Verlag,1991:126-139.
[54] Brazier F M T, Van langen, Pieter H C, et a1. Modeling Conflict Management in Design: An Explicit Approach [J]. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 1995, 9 (3):353-366.
[55] Blazewicz J, Pesch E, Sterna M. The disjunctive graph machine representation of the job shop scheduling problem [J]. European Journal of Operational Research, 2000, 127(2):317-331.
[56]傅廷亮.计算机模拟技术[M].合肥:中国科学技术大学出版社,2001:1-12.
[57]肖田元,张燕云,陈加栋.系统仿真导论[M].北京:清华大学出版社,2000:2-7.
[58]韩文民.造船工期的计算机模拟预测[J].造船技术,1998,12:29-33.
[59]王亚超,马汉武等.生产物流系统建模与仿真-Witness系统及应用.2006.北京科学出版社.
[2]徐学光:先进制造技术与造船业的发展,《自然杂志》,1999,21(2):92-98;
[3]陈强.中心制造船模式的研究与应用[博士论文].黑龙江哈尔滨工程大学.2001.
[4]徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展,2004,2: 257-267.
[5] Graves S. A review of production scheduling [J]. Operations Research, 1981, 29 (4):646-675.
[6]范路桥,常会友,林荣辉.有交货期的job-shop调度问题的改进倒排算法[J].计算机工程与应用,2005.4.46-50.
[7]张翠军,贺毅朝,王金山.敏捷制造中制造资源选择问题的遗传算法[J].计算机工程与应用,2007.43.216-218.
[8]宫俊,汪定伟.敏捷化产品开发中调度问题的研究[J].控制与决策,2002,17.704-709.
[9]李淑霞,单鸿波.基于敏捷制造单元的车间动态重构[J].计算机集成制造系统,2007,13(3):520-526.
[10]曹岩,郭颜军,赵汝嘉.面向敏捷制造生产调度与控制的基于MAS的制造系统[J].机床与液压,2007,35(9):85-90.
[11]王东成,何卫平,王邦龙.基于混合遗传算法的敏捷车间调度研究[J].航空精密制造技术,2006,42(1):43-47.
[12] Sergio Cavaliers, Paolo Gaiardelli. Hybrid genetic algorithms for a multiple-objective scheduling problem. Journal of Intelligent Manufacturing [J], 1998, 9:361-367.
[13] C H Dagli, S Sittisathanchai. Genetic neuro-scheduler: A new approach for job shop scheduling. Int. J. Production Economisc [J],2005, 41:135-145.
[14] S G Ponnambalam, V.Ramlcumar, N.Jawahar. A multiobjective genetic algorithm for job shop scheduling [J]. Production planning&control, 2001, 12(8):764-774.
[15]胡国强,康玲.敏捷制造生产方式下企业的成本控制[J].财会月刊(理论) ,2008,2.62-64.
[16]张维存,郑玉谬,吴晓丹.基于蚁群粒子群算法求解多目标柔性调度问题[J].计算机应用.2007.4:936-941.
[17]方叶祥,钱存华等.基于遗传禁忌算法的双资源约束下并行生产线调度研究[J].运筹与管理.2007.5:153-158.
[18]沈益民,范玉顺.带有跨工序约束的柔性job shop调度问题[J].计算机应用研究.2008.7:2023-2026.
[19]段丛斌,杨建军.敏捷制造车间控制系统及有限能力调度研究[J].机械加工与自动化.2002,7.4-6.
[20]姬耀锋,张德贤.约束满足自适应神经网络求解车间调度问题[J].计算机与数学工程,2005,34(9):22-24.
[21] M Garey, D Johnson. Strong NP-completeness results: motivation, examples and implication [J]. Journal of the ACM, 1978(25):499-508.
[22] S Arora. The approximability of NP-hard problems [J]. Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,ACM,1998:337-348.
[23] Wu Jian yu,He Xiao rong,Chen Bing zhen,QiuTong.A new continuous time MILP model for scheduling of multi-product batch plants[J].Journalof Chemical Industry & Engineering,2005,54 (9):1251-1256.
[24] E.W. Schuster and S.J. Allen. Reordering Algorithm for Complex Industrial Scheduling and Rescheduling[J]. Raw Material Management at Welch's, Computers&Che Inc. 1998, 28(5): 13-24.
[25] J. Roslof, I. Harjunkoski, J.B. rkqvist, S. Karlsson, and T. Westerlund. An MILP-based reordering algorithm for complex industrial scheduling and rescheduling [J]. Computers and Chemical Engineering, 2007, 25: 821–828.
[26]吴建显等.新的多产品间歇生产调度的MLIP模型[J].化工学报,2003,9:1251-1256.
[27] N.J. Nilsson. Problem-solving Methods in Artificial Intelligence [J]. New York: McGraw-Hill. 1971.
[28] Sadeh, N. and M. S. Fox. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem [J]. Artificial Intelligence, 1996, 86: 19-41.
[29] R. Tadei, M. Trubian, J. L. Avendano, F. Della Croce, and G Menga. Aggregate Planning and Scheduling in the Food Industry: A Case Study [J]. European Journal of Operational Research, 1995, 87(3): 564-573.
[30]乔佩利,张宏芳,李小平,高祥.FLOW SHOP调度问题的启发式算法[J].电机与控制学报.2008.1:109-112.
[31] A.Artiba and F. Riane. An Application of a Planning and Scheduling Multi-model Approach in the Chemical Industry [J].Computers in Industry, 1998, 36: 209-229.
[32] M. Zhang and C. Zhang. The Consensus of Uncertainties in Distributed Expert Systems. In: Proceedings of the First International Conference on Multi-Agent Systems[M]. Cambridge, Massachusetts: MIT Press, 1995.
[33]王珂.生产环境不确定条件下的生产调度优化[D].山东大学硕士学位论文,2005,7-8.
[34]李进,面向快速制造的车间调度策略研究[D].南京航空航天大学硕士学位论文,2004.
[35] M.Dorigo,L.M.Gambardella. Art colories for the traveling salesman problem. Biosystems,1997,43(2):73-81.
[36] E. G. Talbi, O. Roux,C. FonluPt,D. Robillard. Parallel ant colonies for the quadratic assignment problem. Future Generation Computer Systems 2001,17(4):441-449.
[37] Colorni A,et al. Ant system for job-shop scheduling[J].JORBEL,1994,34(1):39-53.
[38] Carlier J, Pinson E. Adjusting heads and tails for the job shop scheduling [J]. European Journal of Operational Research, 1994, 78(3):146-161.
[39] Walter J.Gutjahr. A Graph based Ant System and Its Convergence [J].Future Generation Computer Sytems, 2000(16):873-888.
[40] Thomas Stutzle, Marco Dorigo.A Short Convergence Proof for a Class of Ant Colony Optimization Algorithms [J].IEEE Trans on Evolutionary Computation, 2002, 6 (4); 358-365.
[41]朱庆保.蚁群优化算法的收敛性分析[J].控制与决策,2006,21(7).
[42]王晓平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[43] T. Starkweather, D. Whitley, K. Mathias and S. McDaniel. Sequence Scheduling with Genetic Algorithms. In: Proceedings of the US/German Conference on New Directions for OR in Manufacturing, 1992:130-148.
[44] Cheng R,Gen M,Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms representation [J].Computers&Industrial Engineering, 1996,30(4):983-987.
[45]高家全,何桂霞等.解家纺企业生产计划问题的并行混合遗传算法[J] .系统仿真学报,2007, 9:3903-3905.
[46] Duffie N.A., Chitturi R., Mou J. Fault-tolerant heterarchical control of heterogeneous manufacturing system entities [J]. Journal of Manufacturing Systems, 1988, 7(4):315-327.
[47]潘家招等编著,现代生产管理学,清华大学出版社,1994.
[48]王承文:现代造船模式研究[博士论文].黑龙江哈尔滨工程大学.2006.
[49]季建华等编著.成组生产管理.陕西科学技术出版社,1995.
[50]张美玉等译.相似性理论的原理与实践,成组技术与生产现代化,1996No.1, 25-28.
[51] Black J.T. Cellular Manufacturing Systems, in Voss, C.A., ed. [M].Just-In-Time Manufacture,1987.
[52] Pena-Mora F, Anumba CJ, Solari J, et al. Conflict, Mitigation System for Collaborative Engineering Design, Analysis and Manufacturing, 2005,9(1):101-124.
[53] Kiriyama T. A Model Integration Framework for Cooperative Design [A]. Sriram D, Logcher R, FukudaS. Computer-Aided Cooperative Product Development[C].Berlin: Spring-Verlag,1991:126-139.
[54] Brazier F M T, Van langen, Pieter H C, et a1. Modeling Conflict Management in Design: An Explicit Approach [J]. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 1995, 9 (3):353-366.
[55] Blazewicz J, Pesch E, Sterna M. The disjunctive graph machine representation of the job shop scheduling problem [J]. European Journal of Operational Research, 2000, 127(2):317-331.
[56]傅廷亮.计算机模拟技术[M].合肥:中国科学技术大学出版社,2001:1-12.
[57]肖田元,张燕云,陈加栋.系统仿真导论[M].北京:清华大学出版社,2000:2-7.
[58]韩文民.造船工期的计算机模拟预测[J].造船技术,1998,12:29-33.
[59]王亚超,马汉武等.生产物流系统建模与仿真-Witness系统及应用.2006.北京科学出版社.