NEARLY ON LINE SCHEDULING OF PREEMPTIVE INDEPENDENT TASKS

We discuss the problem of scheduling preemptive independent tasks, subject to release dates and due dates, on identical processors, so as to minimize the maximum lateness. This problem was solved by a polynomial flow based algorithm, but the major drawback of this approach is its off-line character. We study a priority algorithm, the equivalent of a list scheduling method in the non-preemptive case, in which tasks are ordered according to their due dates. This algorithm is nearly on-line and of low complexity. It builds an optimal schedule when the release dates are equal. In the general case, it provides an absolute performance gurantee. These results hold when the number of available machines is allowed to vary with time in a zigzag way (the number of machines is either K, or K - 1).