运输能力有限的分段两阶段多车间调度问题
|
摘要
为有效解决船舶分段生产过程中存在的返工、运输能力限制以及堆场面积约束等问题,分析两阶段多车间调度的特点,构建了运输能力有限的分段两阶段多车间调度模型。模型综合考虑了分段批次内重调度、批次间的分割合并、分段返工以及缓冲面积和运输能力约束,目标是最小化分段的最大完工时间,建立分段在加工车间、装配车间以及堆场中的调度数学模型。利用基于路径选择的分段两阶段多车间调度启发式算法进行求解,并通过数值实验以及对比分析验证了模型的合理性和算法的有效性。
To solve problems of block reworking and constraints of transportation and stockyard, the property of twosatge and multi-workshop scheduling is analyzed and a new model called block two-stage and multi-workshop scheduling with transportation is developed. By considering the batch rescheduling, batch splitting and amalgamating, block reworking and constraints of capacity, this problem includes the scheduling in hybird flow shop, assembly shop and stockyard,minimizing of maximum completion time as the optimization goal. A two-stage and multi-workshop heuristic algorithm based on the path searching is put forward to solve this model, and this model's rationality and the arithmetic's effectiveness can be indicated by carrying out numerical experiments and comparing with other algorithms.
To solve problems of block reworking and constraints of transportation and stockyard, the property of twosatge and multi-workshop scheduling is analyzed and a new model called block two-stage and multi-workshop scheduling with transportation is developed. By considering the batch rescheduling, batch splitting and amalgamating, block reworking and constraints of capacity, this problem includes the scheduling in hybird flow shop, assembly shop and stockyard,minimizing of maximum completion time as the optimization goal. A two-stage and multi-workshop heuristic algorithm based on the path searching is put forward to solve this model, and this model's rationality and the arithmetic's effectiveness can be indicated by carrying out numerical experiments and comparing with other algorithms.
引文
[1]Ruiz R,J A.Invited review the hybrid flow shop scheduling problem[J].Eur J Oper Res,2010,205:1-18.
[2]Rinnooy Kan A H G.Machine scheduling problems[M].Hague:Martinus Nijhoff,1976.
[3]王圣尧,王凌,许烨.求解相同并行机混合流水车间调度问题的分布估计算法[J].计算机集成制造系统,2013,19(6):1304-1312.
[4]项洁,周炳海.基于DBR-GA的混合流水车间调度方法[J].计算机集成制造系统,2012,18(11):2485-2491.
[5]轩华.运输能力有限混合流水车间调度的改进拉格朗日松弛算法[J].计算机集成制造系统,2013,19(3):1633-1639.
[6]Lin Rock,Liao Chingjong.A case study of batch scheduling for an assembly shop[J].Int J Production Economics,2012,139:473-483.
[7]Cummings Mc Coy D H,Egbelu P J.Minimizing production flow time in a process and assembly job shop[J].International Journal of Production Research,1998,36(8):2315-2332.
[8]Doctor S R,Cavalier T M,Egbelu P J.Scheduling for machining and assembly in a job-shop environment[J].International Journal of Production Research,1993,31(6):1275-1297.
[9]Fry T D,Olife M D,Minor E D,et al.The effect of product structure and sequencing rule on assembly shop performance[J].International Journal of Production Research,1989,27(4):671-686.
[10]Cheng T C E,Wang G.Scheduling the fabrication and assembly of components in a two-machine flow shop[J].IIE Transactions,1999,311:135-143.
[11]Gicquel C,Hege L,Minoux M,et al.A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints[J].Computers&Operations Research,2012,39:629-636.
[12]Luo Hao,Huang G Q,Zhang Yingfeng,et al.Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm[J].Robotics and Computer Integrated Manufacturing,2009,25:962-971.
[13]Yokoyama M,Santos D L.Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times[J].European Journal of Operational Research,2005,161:754-770.
[14]Fattahi P.A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations[J].Applied Mathematical Modelling,2014,38:119-134.
[15]Ye Taofeng.Analysis on multi-stage lot streaming:The effect of transfer[J].Computers&Industrial Engineering,2012,62:1046-1054.
[16]王福吉,赵国凯.基于可行域遗传算法的装配作业调度[J].计算机集成制造系统,2010,16(1):115-120.
[17]Guinet A G P,Solomon M M.Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time[J].International Journal of Production Research,1996,34(6):1643-1654.
[18]孙立锋,徐克林.以JIT为目标的多阶段非等同并行机调度问题研究[J].现代制造系统,2011(10):32-36.
[19]刘心报,郭盈,程浩.一种基于NEH算法的有效求解半flowshop问题的迭代插入算法[J].仪器仪表学报,2009,30(6):261-265.
[20]张晓东,严洪森.多级车间生产计划和调度的优化集成[J].机械工程学报,2005,41(9):98-105.
[2]Rinnooy Kan A H G.Machine scheduling problems[M].Hague:Martinus Nijhoff,1976.
[3]王圣尧,王凌,许烨.求解相同并行机混合流水车间调度问题的分布估计算法[J].计算机集成制造系统,2013,19(6):1304-1312.
[4]项洁,周炳海.基于DBR-GA的混合流水车间调度方法[J].计算机集成制造系统,2012,18(11):2485-2491.
[5]轩华.运输能力有限混合流水车间调度的改进拉格朗日松弛算法[J].计算机集成制造系统,2013,19(3):1633-1639.
[6]Lin Rock,Liao Chingjong.A case study of batch scheduling for an assembly shop[J].Int J Production Economics,2012,139:473-483.
[7]Cummings Mc Coy D H,Egbelu P J.Minimizing production flow time in a process and assembly job shop[J].International Journal of Production Research,1998,36(8):2315-2332.
[8]Doctor S R,Cavalier T M,Egbelu P J.Scheduling for machining and assembly in a job-shop environment[J].International Journal of Production Research,1993,31(6):1275-1297.
[9]Fry T D,Olife M D,Minor E D,et al.The effect of product structure and sequencing rule on assembly shop performance[J].International Journal of Production Research,1989,27(4):671-686.
[10]Cheng T C E,Wang G.Scheduling the fabrication and assembly of components in a two-machine flow shop[J].IIE Transactions,1999,311:135-143.
[11]Gicquel C,Hege L,Minoux M,et al.A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints[J].Computers&Operations Research,2012,39:629-636.
[12]Luo Hao,Huang G Q,Zhang Yingfeng,et al.Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm[J].Robotics and Computer Integrated Manufacturing,2009,25:962-971.
[13]Yokoyama M,Santos D L.Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times[J].European Journal of Operational Research,2005,161:754-770.
[14]Fattahi P.A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations[J].Applied Mathematical Modelling,2014,38:119-134.
[15]Ye Taofeng.Analysis on multi-stage lot streaming:The effect of transfer[J].Computers&Industrial Engineering,2012,62:1046-1054.
[16]王福吉,赵国凯.基于可行域遗传算法的装配作业调度[J].计算机集成制造系统,2010,16(1):115-120.
[17]Guinet A G P,Solomon M M.Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time[J].International Journal of Production Research,1996,34(6):1643-1654.
[18]孙立锋,徐克林.以JIT为目标的多阶段非等同并行机调度问题研究[J].现代制造系统,2011(10):32-36.
[19]刘心报,郭盈,程浩.一种基于NEH算法的有效求解半flowshop问题的迭代插入算法[J].仪器仪表学报,2009,30(6):261-265.
[20]张晓东,严洪森.多级车间生产计划和调度的优化集成[J].机械工程学报,2005,41(9):98-105.