考虑成本限制的最小化最大延迟时间平行机调度问题

Parallel machine scheduling problem with machine cost to minimize the maximal lateness

以绿色制造为背景,假定机器设备具有不同的能源消耗成本或维护成本,研究了一类考虑成本限制的平行机调度问题.调度的目标是最小化最大延迟时间.为该问题建立了整数规划模型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.