Minimizing the weighted flow time on a single machine with the resumable availability constraint: worst case of the WSPT heuristic

Abstract

In this paper we study the single machine scheduling problem with the aim of minimizing the weighted flow time. The machine is unavailable during a given period. We consider the resumable case. We propose new properties of the worst-case performance of the WSPT heuristic. We give a tighter approximation of the worst-case error, and we show that the worst-case bound is equal to 2 under certain conditions. The results obtained complete the previous analysis of Lee, C-Y., Machine scheduling with an availability constraint. J. Glob. Optim., 1996, 9, 363–384.

Keywords:

• Scheduling
• Availability constraint
• Worst-case analysis

Acknowledgement

The authors would like to thank the anonymous referees for their helpful suggestions which improved the presentation of the paper.