考虑成本限制的最小化最大延迟时间平行机调度问题
|
摘要
以绿色制造为背景,假定机器设备具有不同的能源消耗成本或维护成本,研究了一类考虑成本限制的平行机调度问题.调度的目标是最小化最大延迟时间.为该问题建立了整数规划模型MIP,设计了改进的EDD (earliest due date firstly)算法,命名为MEDD.由于考虑成本限制,证明了MEDD算法的可行性,并进而理论分析了算法的最坏误差界.通过算例说明了算法的执行情况,同时采用大量随机数据实验验证算法的性能.对于小规模问题,将MEDD的解与MIP的精确解进行了对比;对于大规模问题,由于MIP精确解难以获得,以MIP对应的线性规划松弛模型MLP的最优值为下界对MEDD算法的解进行了衡量.实验结果表明了所构建MEDD算法的有效性.
In this paper, we assumed that machines have different energy consumptions or maintenance costs in the context of green manufacturing, and tried to solve the parallel machine scheduling problem under the condition of cost constraints. To minimize the maximum lateness, an integer programming model MIP was established and an improved algorithm for EDD(earliest due date firstly) — MEDD was designed. Then the feasibility of the MEDD algorithm was proved under the condition of cost constraints,and the worst error bound of the algorithm was also analyzed theoretically. By giving an example, we proved the feasibility of the algorithm. And its performance was verified by a large number of random data experiments. For a small scale, the solution of MEDD was compared with the exact solution of MIP. While the exact solution of MIP is too hard to obtain when it comes to a large scale, the optimal value of MLP of the linear programming relaxation model corresponding to MIP was taken as the lower bound to measure the solution of MEDD algorithm. All these results showed a great effectiveness of MEDD algorithm.
In this paper, we assumed that machines have different energy consumptions or maintenance costs in the context of green manufacturing, and tried to solve the parallel machine scheduling problem under the condition of cost constraints. To minimize the maximum lateness, an integer programming model MIP was established and an improved algorithm for EDD(earliest due date firstly) — MEDD was designed. Then the feasibility of the MEDD algorithm was proved under the condition of cost constraints,and the worst error bound of the algorithm was also analyzed theoretically. By giving an example, we proved the feasibility of the algorithm. And its performance was verified by a large number of random data experiments. For a small scale, the solution of MEDD was compared with the exact solution of MIP. While the exact solution of MIP is too hard to obtain when it comes to a large scale, the optimal value of MLP of the linear programming relaxation model corresponding to MIP was taken as the lower bound to measure the solution of MEDD algorithm. All these results showed a great effectiveness of MEDD algorithm.
引文
[1] Imreh C, Noga J. Scheduling with machine cost[C]//RANDOM-APPROX'99, Lecture Notes in Computer Science, 1999, 1671:168-176.
[2] Dosa G, Tan Z. New upper and lower bounds for online scheduling with machine cost[J]. Discrete Optimization,2010, 7:125-135.
[3] Dosa G, Imreh C. The generalization of scheduling with machine cost[J]. Theoretical Computer Science, 2013,510:102-110.
[4] Rustogi K, Strusevich V A. Parallel machine scheduling:Impact of adding extra machines[J]. Operations Research, 2013, 61(5):1243-1257.
[5] Cao D, Chen M, Wan G. Parallel machine selection and job scheduling to minimize machine cost and job tardiness[J]. Computers&Operations Research, 2005, 32:1995-2012.
[6] Leung J Y T, Lee K, Pinedo M L. Bi-criteria scheduling with machine assignment costs[J]. International Journal of Production Economics, 2012, 139:321-329.
[7] Lee K, Leung J Y T, Jia Z H, et al. Fast approximation algorithms for bi-criteria scheduling with machine assignment costs[J]. European Journal of Operations Research, 2014, 238:54-64.
[8] Jiang Y, Hu J, Liu L, et al. Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost[J]. Information Sciences an International Journal, 2014, 269(11):128-141.
[9] Li K, Zhang X, Leung J Y T. Parallel machine scheduling problems in green manufacturing industry[J]. Journal of Manufacturing Systems, 2016, 38:98-106.
[10]汪恭书,唐立新.并行机实时调度问题的LR&CG算法[J].控制与决策,2013, 28(6):829-836.Wang G S, Tang L X. LR CG algorithm for parallel machine real-time scheduling problem[J]. Control and Decision, 2013, 28(6):829-836.
[11]王东军,刘翱,刘克,等.基于优先规则的复杂并行机调度问题研究[J].系统工程理论与实践,2016, 36(3):779-786.Wang D J, Liu A, Liu K, et al. Priority rule-based complex identical parallel machines scheduling[J]. Systems Engineering—Theory&Practice, 2016, 36(3):779-786.
[12]许晓晴,崔文田,林军,等.基于最小最大遗憾的同型并行机鲁棒调度模型[J].系统工程学报,2013, 28(6):729-737.Xu X Q, Cui W T, Lin J, et al. Rubust identical parallel machines scheduling model based on min-max regret criterion[J]. Journal of Systems Engineering, 2013, 28(6):729-737.
[13]王建军,刘晓盼,刘锋,等.随机机器故障下加工时间可控的并行机鲁棒调度[J].中国管理科学,2017, 25(3):111-120.Wang J J, Liu X P, Liu F, et al. Robust scheduling of unrelated parallel machines subject to stochastic breakdowns and controllable processing times[J]. Chinese Journal of Management Science, 2017, 25(3):111-120.
[14]吴楚格,王凌,郑晓龙.求解不相关并行机调度的一种自适应分布估计算法[J].控制与决策,2016, 31(12):2177-2182.Wu C G, Wang L, Zheng X L. An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J]. Control and Decision, 2016, 31(12):2177-2182.
[15] Li K, Zhang H J, Cheng B Y, et al. Uniform parallel machine scheduling problems with fixed machine cost[J].Optimization Letters, 2016:1-14.
[16] Jackson J R. Scheduling a production line to minimize maximum tardiness[R]. University of California at Los Angeles, CA,1955.
[17]刘乐,周泓.新工件到达干扰下单机最大延迟时间重调度[J].系统工程学报,2014(4):494-506.Liu L,Zhou H. Single-machine rescheduling of minimizing the maximum lateness with the disruptive of new jobs[J], Journal of Systems Engineering, 2014(4):494-506.
[18] Zinder Y, Walker S. Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness[J]. Discrete Applied Mathematics, 2015, 196:28-53.
[19] Li K, Yang S L, Ma H W. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines[J]. Mathematical&Computer Modeling, 2011, 53(5-6):854-860.
[20] Liu Q, Yuan J. Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness[J].Journal of Combinatorial Optimization, 2016, 32(2):1-11.
[21] He H. Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effect[J]. Computers&Industrial Engineering, 2016, 97:73-83.
[22] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling:A survey[J]. Annals of Discrete Mathematics, 1979, 5(1):287-326.
[23] Garey M R, Johnson D S. Strong NP-completeness results:Motivation, examples and implications[J]. Journal of Association for Computing Machinery, 1978, 25:499-508.
[24] Masuda T, Ishii H, Nishida T. Some bounds on approximation algorithms for n/m/I/Lmax and n/2/F/Lmax scheduling problems[J]. Journal of the Operations Research Society of Japan, 1983, 26(3):212-225.
[2] Dosa G, Tan Z. New upper and lower bounds for online scheduling with machine cost[J]. Discrete Optimization,2010, 7:125-135.
[3] Dosa G, Imreh C. The generalization of scheduling with machine cost[J]. Theoretical Computer Science, 2013,510:102-110.
[4] Rustogi K, Strusevich V A. Parallel machine scheduling:Impact of adding extra machines[J]. Operations Research, 2013, 61(5):1243-1257.
[5] Cao D, Chen M, Wan G. Parallel machine selection and job scheduling to minimize machine cost and job tardiness[J]. Computers&Operations Research, 2005, 32:1995-2012.
[6] Leung J Y T, Lee K, Pinedo M L. Bi-criteria scheduling with machine assignment costs[J]. International Journal of Production Economics, 2012, 139:321-329.
[7] Lee K, Leung J Y T, Jia Z H, et al. Fast approximation algorithms for bi-criteria scheduling with machine assignment costs[J]. European Journal of Operations Research, 2014, 238:54-64.
[8] Jiang Y, Hu J, Liu L, et al. Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost[J]. Information Sciences an International Journal, 2014, 269(11):128-141.
[9] Li K, Zhang X, Leung J Y T. Parallel machine scheduling problems in green manufacturing industry[J]. Journal of Manufacturing Systems, 2016, 38:98-106.
[10]汪恭书,唐立新.并行机实时调度问题的LR&CG算法[J].控制与决策,2013, 28(6):829-836.Wang G S, Tang L X. LR CG algorithm for parallel machine real-time scheduling problem[J]. Control and Decision, 2013, 28(6):829-836.
[11]王东军,刘翱,刘克,等.基于优先规则的复杂并行机调度问题研究[J].系统工程理论与实践,2016, 36(3):779-786.Wang D J, Liu A, Liu K, et al. Priority rule-based complex identical parallel machines scheduling[J]. Systems Engineering—Theory&Practice, 2016, 36(3):779-786.
[12]许晓晴,崔文田,林军,等.基于最小最大遗憾的同型并行机鲁棒调度模型[J].系统工程学报,2013, 28(6):729-737.Xu X Q, Cui W T, Lin J, et al. Rubust identical parallel machines scheduling model based on min-max regret criterion[J]. Journal of Systems Engineering, 2013, 28(6):729-737.
[13]王建军,刘晓盼,刘锋,等.随机机器故障下加工时间可控的并行机鲁棒调度[J].中国管理科学,2017, 25(3):111-120.Wang J J, Liu X P, Liu F, et al. Robust scheduling of unrelated parallel machines subject to stochastic breakdowns and controllable processing times[J]. Chinese Journal of Management Science, 2017, 25(3):111-120.
[14]吴楚格,王凌,郑晓龙.求解不相关并行机调度的一种自适应分布估计算法[J].控制与决策,2016, 31(12):2177-2182.Wu C G, Wang L, Zheng X L. An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J]. Control and Decision, 2016, 31(12):2177-2182.
[15] Li K, Zhang H J, Cheng B Y, et al. Uniform parallel machine scheduling problems with fixed machine cost[J].Optimization Letters, 2016:1-14.
[16] Jackson J R. Scheduling a production line to minimize maximum tardiness[R]. University of California at Los Angeles, CA,1955.
[17]刘乐,周泓.新工件到达干扰下单机最大延迟时间重调度[J].系统工程学报,2014(4):494-506.Liu L,Zhou H. Single-machine rescheduling of minimizing the maximum lateness with the disruptive of new jobs[J], Journal of Systems Engineering, 2014(4):494-506.
[18] Zinder Y, Walker S. Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness[J]. Discrete Applied Mathematics, 2015, 196:28-53.
[19] Li K, Yang S L, Ma H W. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines[J]. Mathematical&Computer Modeling, 2011, 53(5-6):854-860.
[20] Liu Q, Yuan J. Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness[J].Journal of Combinatorial Optimization, 2016, 32(2):1-11.
[21] He H. Minimization of maximum lateness in an m-machine permutation flow shop with a general exponential learning effect[J]. Computers&Industrial Engineering, 2016, 97:73-83.
[22] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling:A survey[J]. Annals of Discrete Mathematics, 1979, 5(1):287-326.
[23] Garey M R, Johnson D S. Strong NP-completeness results:Motivation, examples and implications[J]. Journal of Association for Computing Machinery, 1978, 25:499-508.
[24] Masuda T, Ishii H, Nishida T. Some bounds on approximation algorithms for n/m/I/Lmax and n/2/F/Lmax scheduling problems[J]. Journal of the Operations Research Society of Japan, 1983, 26(3):212-225.