A new when-to-schedule policy in online scheduling based on cumulative task delays

摘要

This paper proposes a new when-to-schedule policy in online scheduling, which considers timing of rescheduling based on the concept of a control limit policy and rolling schedules. Under the proposed policy, rescheduling is carried out based on a cumulative delay which can be a measure to determine suitable timing of rescheduling. Some computational experiments demonstrate the effectiveness of the proposed policy by applying it to single-machine dynamic scheduling with sequence-dependent setup times and urgent jobs, where total setups are minimized as well as rescheduling frequency. It is also demonstrated that the proposed policy can outperform typical rescheduling policies.