考虑定期维护时段的平行机调度问题

摘要

研究了一类作业不可中断且具有周期性维护时段的平行机调度问题.假定有m台含有不确定可用时间段Tji(i表示第i个机器,j表示第j个可用时段)和相同时间的不可用时段T的平行机.调度的目标是加工完所有给定的作业,并最小化最大完工时间Cmax.基于对经典的LPT(Longest Processing Time first,长作业优先)、FFD法(First Fit Decreasing,降序首次适应算法)的改进,提出了MFFD-LPT算法及其修正算法DA(Displace Algorithm).理论证明了MFFD-LPT算法的最坏误差界为9/5.大量数据实验验证了MFFD-LPT算法的有效性,同时,DA算法的修正率一般在20％-30％范围之内,体现了很好的修正作用.