Nearly on line scheduling of preemptive independent tasks

Nearly on line scheduling of preemptive independent tasks

0.00 Avg rating0 Votes
Article ID: iaor1997861
Country: Netherlands
Volume: 57
Issue: 2/3
Start Page Number: 229
End Page Number: 241
Publication Date: Feb 1995
Journal: Discrete Applied Mathematics
Authors:
Abstract:

The paper discusses 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. The paper studies 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 guarantee. 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).

Reviews

Required fields are marked *. Your email address will not be published.