An Improved Method for Scheduling Independent Tasks

Abstract

Abstract A computationally efficient algorithm is developed for scheduling an independent task set, characterized by deterministic processing times and due dates, on a single processor so that total tardiness is minimized. The performance index is assumed to be a loss function of the form max (0, Ci - Di) where Ci is the calendar completion time of task i and Di, is its due date. The method is in general sub-optimal, but conditions are given for which an optimal schedule is always obtained. In addition, a technique is presented for improving suboptimal solutions by merely interchanging certain nonadjacent pairs of tasks.