CCIT Report #522, March 2005

Bounds on modified SPT heuristics for single machine flow-time scheduling
with a single breakdown

Omer Gurewitz, Igal Adiri, Technion

Consider the problem of scheduling n jobs with known processing time on a single machine. The machine
undergoes a breakdown at a fixed point in time, known in advance, during the processing of the jobs. The job
preempted due to the breakdown has to be restarted from the beginning. The objective function is minimizing
the sum of completion times of the jobs. It was found that the problem is NP-hard and the SPT heuristic has
a tight bound of 9/7. In this paper, we present a scheme of a series of heuristic algorithms as a function of the
number of jobs scheduled before the breakdown. Every algorithm is characterized, for the worst case, by its bound
and complexity. Thus, we provide the scheduler with a simple tool for determining his/her choice in the trade-off
between accuracy of the solution (deviation from the optimum) and the computational effort.