Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan
Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan
复制标题
DOI：
10.1016/j.cor.2006.08.015
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
Dehua Xu;Kaibiao Sun;Hongxing Li
中科院分区：
文献类型：
--
作者：
Dehua Xu;Kaibiao Sun;Hongxing Li
我们介绍并研究了具有几乎周期性维护活动的并行机器调度问题。如果机器的任意两次连续维护活动之间的时间差在 ɛ 以内，我们就说机器的维护是 ɛ——几乎周期性的。目标是最小化完工时间 Cmax，即上次完成维护的完成时间。假设最小和最大维护间距分别为 T 和 T′=T+ɛ，那么我们的问题可以描述为 Pm,MS[T,T′]||Cmax。我们证明这个问题是 NP 困难的，除非 P=NP，否则对于任何 ρ<2，这个问题没有多项式时间 ρ 逼近算法。然后我们提出了一种名为 BFD-LPT 的多项式时间 2T′/T 近似算法来解决该问题。因此，如果T′=T，BFD-LPT算法是最好的近似算法。此外，如果作业的总处理时间大于 2m(T′+TM) 且 min{pi}⩾T，其中 TM 是执行一项维护活动所需的时间，则 BFD-LPT 算法得出的完工时间不超过最佳完工时间的 32。最后，我们证明，如果 min{pi}⩾T，其中 σ=TM/T′，则 BFD-LPT 算法的渐近最坏情况界限为 1+σ/(1+2σ)。
We introduce and study a parallel machine scheduling problem with almost periodic maintenance activities. We say that the maintenance of a machine is ɛ-almost periodic if the difference of the time between any two consecutive maintenance activities of the machine is within ɛ. The objective is to minimize the makespan Cmax, i.e., the completion time of the last finished maintenance. Suppose the minimum and maximum maintenance spacing are T and T′=T+ɛ, respectively, then our problem can be described as Pm,MS[T,T′]||Cmax. We show that this problem is NP-hard, and unless P=NP, there is no polynomial time ρ-approximation algorithm for this problem for any ρ<2. Then we propose a polynomial time 2T′/T-approximation algorithm named BFD-LPT to solve the problem. Thus, if T′=T, BFD-LPT algorithm is the best possible approximation algorithm. Furthermore, if the total processing time of the jobs is larger than 2m(T′+TM) and min{pi}⩾T, where TMis the amount of time needed to perform one maintenance activity, then the makespan derived from BFD-LPT algorithm is no more than 32 that of the optimal makespan. Finally, we show that the BFD-LPT algorithm has an asymptotic worst-case bound of 1+σ/(1+2σ) if min{pi}⩾T, where σ=TM/T′.