具有维修时间的两台平行机在线排序

On-line Scheduling Problems of Two Parallel Machines with Maintenance Time

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的。对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形。通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法。

In scheduling problems,the machines need to be repaired because of breakdowns or other reasons.Therefore,maintenance time during the processing of jobs is considered.For scheduling problems of two parallel identical machines with common maintenance time intervals and resumable availability,its on-line version was researched.In this paper,the lower bound of competitive ratio no less than 2 for arbitrary on-line algorithm by analysing different cases is proved.Moreover,a best possible on-line algorithm with competitive ratio no more than 2 is given.