带恶化工件的不相关并行机调度优化
|
摘要
研究了以最小化最大完工时间为目标的不相关并行机环境下带恶化工件的车间调度问题,工件的加工时间随着开始时间的不同而改变,将其表示为开始时间的增函数,假设每个工件在不同机器上有各自的恶化系数。针对该NP-hard问题,建立数学规划模型,设计基于两段式编码和遗传参数自适应调节策略的改进遗传算法以合理地进行工件排序及机器分配。通过测试不同规模问题的仿真实验,对比结果表明所设计的算法在求解时间和求解质量上均具有较大优势。
Unrelated parallel machine scheduling problem with deteriorating jobs is studied with the objective of minimizing the maximum completion time. The processing time of a job varies with its beginning time which is denoted as an increasing function of its starting time. It is assumed that each job has its own different deterioration rate on each machine. A mathematical programming model is formulated for the NP-hard problem. An improved genetic algorithm based on two segment coding and self-adaptive adjustment of genetic parameters is then designed to make job scheduling and machine allocation more reasonable. Through the simulation experiments of different sized problems, the results show that the proposed algorithm has more advantages in both resolution time and solution quality.
Unrelated parallel machine scheduling problem with deteriorating jobs is studied with the objective of minimizing the maximum completion time. The processing time of a job varies with its beginning time which is denoted as an increasing function of its starting time. It is assumed that each job has its own different deterioration rate on each machine. A mathematical programming model is formulated for the NP-hard problem. An improved genetic algorithm based on two segment coding and self-adaptive adjustment of genetic parameters is then designed to make job scheduling and machine allocation more reasonable. Through the simulation experiments of different sized problems, the results show that the proposed algorithm has more advantages in both resolution time and solution quality.
引文
[1]Ji M,Cheng T C E.Parallel-machine scheduling of simple linear deteriorating jobs[J].Theoretical Computer Science(S0304-3975),2009,410:3761-3768.
[2]胡大勇,姚振强.调整时间与顺序相关的等同并行机调度[J].机械工程学报,2011,47(16):160-165.Hu Dayong,Yao Zhenqiang.Identical parallel machines scheduling with sequence-dependent setup times[J].Journal of Mechanical Engineering,2011,47(16):160-165.
[3]Beez?o A C,Cordeau J F,Laporte G,et al.Scheduling identical parallel machines with tooling constraints[J].European Journal of Operational Research(S0377-2217),2017,257(3):834-844.
[4]吴楚格,王凌,郑晓龙.求解不相关并行机调度的一种自适应分布估计算法[J].控制与决策,2016,31(12):2177-2182.Wu Chuge,Wang Ling,Zheng Xiaolong.An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J].Control and Decision,2016,31(12):2177-2182.
[5]许晓晴,崔文田,林军,等.基于最小最大遗憾的同型并行机鲁棒调度模型[J].系统工程学报,2013,28(6):729-737.Xu Xiaoqing,Cui Wentian,Lin Jun,et al.Robust identical parallel machines scheduling model based on min-max regret criterion[J].Journal of Systems Engineering,2013,28(6):729-737.
[6]Eduardo L R,Stefan V.Modeling the parallel machine scheduling problem with step deteriorating jobs[J].European Journal of Operational Research(S0377-2217),2016,255(1):21-33.
[7]Wang X Y,Zhou Z L,Ji P,et al.Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times[J].Computers and Industrial Engineering(S0360-8352),2014,74:88-91.
[8]Zhang Q,Luo C X.Uniform parallel-machine scheduling with deteriorating jobs and rejection[J].Applied Mechanics and Materials,2014,644/650:2030-2033.
[9]Rostami M,Pilerood A E,Mazdeh M M.Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment[J].Computers and Industrial Engineering(S0360-8352),2015,85:206-215.
[10]于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(8):1483-1488.Yu Yingying,Chen Yan,Li Taoying.Improved genetic algorithm for solving TSP[J].Control and Decision,2014,29(8):1483-1488.
[11]Liu M H,Peng X F.Improved adaptive genetic algorithms for job shop scheduling problems[J].Advanced Materials Research(S0363-7425),2010,97/101:2473-2476.
[12]李玲,唐秋华,张利平.文化基因算法求解多工艺路线炼钢-连铸生产调度问题[J].武汉科技大学学报,2017,40(1):17-22.Li Ling,Tang Qiuhua,Zhang Liping.Memetic algorithm for steelmaking-continuous casting production scheduling with multiple process routes[J].Journal of Wuhan University of Science and Technology,2017,40(1):17-22.
[2]胡大勇,姚振强.调整时间与顺序相关的等同并行机调度[J].机械工程学报,2011,47(16):160-165.Hu Dayong,Yao Zhenqiang.Identical parallel machines scheduling with sequence-dependent setup times[J].Journal of Mechanical Engineering,2011,47(16):160-165.
[3]Beez?o A C,Cordeau J F,Laporte G,et al.Scheduling identical parallel machines with tooling constraints[J].European Journal of Operational Research(S0377-2217),2017,257(3):834-844.
[4]吴楚格,王凌,郑晓龙.求解不相关并行机调度的一种自适应分布估计算法[J].控制与决策,2016,31(12):2177-2182.Wu Chuge,Wang Ling,Zheng Xiaolong.An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J].Control and Decision,2016,31(12):2177-2182.
[5]许晓晴,崔文田,林军,等.基于最小最大遗憾的同型并行机鲁棒调度模型[J].系统工程学报,2013,28(6):729-737.Xu Xiaoqing,Cui Wentian,Lin Jun,et al.Robust identical parallel machines scheduling model based on min-max regret criterion[J].Journal of Systems Engineering,2013,28(6):729-737.
[6]Eduardo L R,Stefan V.Modeling the parallel machine scheduling problem with step deteriorating jobs[J].European Journal of Operational Research(S0377-2217),2016,255(1):21-33.
[7]Wang X Y,Zhou Z L,Ji P,et al.Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times[J].Computers and Industrial Engineering(S0360-8352),2014,74:88-91.
[8]Zhang Q,Luo C X.Uniform parallel-machine scheduling with deteriorating jobs and rejection[J].Applied Mechanics and Materials,2014,644/650:2030-2033.
[9]Rostami M,Pilerood A E,Mazdeh M M.Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment[J].Computers and Industrial Engineering(S0360-8352),2015,85:206-215.
[10]于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(8):1483-1488.Yu Yingying,Chen Yan,Li Taoying.Improved genetic algorithm for solving TSP[J].Control and Decision,2014,29(8):1483-1488.
[11]Liu M H,Peng X F.Improved adaptive genetic algorithms for job shop scheduling problems[J].Advanced Materials Research(S0363-7425),2010,97/101:2473-2476.
[12]李玲,唐秋华,张利平.文化基因算法求解多工艺路线炼钢-连铸生产调度问题[J].武汉科技大学学报,2017,40(1):17-22.Li Ling,Tang Qiuhua,Zhang Liping.Memetic algorithm for steelmaking-continuous casting production scheduling with multiple process routes[J].Journal of Wuhan University of Science and Technology,2017,40(1):17-22.