考虑最小化最大完工时间间隔的三台平行机调度

Three parallel machines scheduling with minimizing the maximum inter-completion time

针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进而给出最优方案的基本性质;其次,基于最优解的性质证明了目标值的一个下界并设计了O(n^(2))时间的算法来求解该下界值;最后运用预留尽可能多的空闲时间(RMST)在一台机器上的思想,设计了改进的RMST算法(IRMST)来求解该问题.通过利用数值仿真实验与RMST算法,遗传算法等其它算法及下界进行对比,验证了该算法的有效性.

This work studies the processing schedules of parallel machines with strong response abilities to unexpected and urgent jobs.We consider the job scheduling on three parallel machines,aiming to minimize the maximum difference between the completion times of any two consecutively completed jobs,in other words,to minimize the maximum inter-completion time.We first give two upper bounds of the workload of machines which is the sufficient condition of feasible solutions.Based on the sufficient condition,we first give several basic properties of the optimal solution.Secondly,we further prove a lower bound of the objective value and design an O(n^(2))time algorithm to calculate the lower bound.Finally,we develop an improved algorithm based on the RMST algorithm to solve the considered problem,in which the RMST algorithm considers the case that one may reserve as much spare time as possible on one of the machines.Through computational comparisons between the improved algorithm and RMST algorithm together with the genetic algorithm and the lower bound of objective value,it is shown that our algorithm outperforms the other two algorithms.Numerical experiments verify the effectiveness of the improved algorithm.