571 EFFICIENT ALGORITHMS FOR CYCLIC SCHEDULING
F. Gasperoni, U. Schwiegelshohn, July 1991
This work addresses the problem of non-preemptively scheduling a cyclic set of interdependent operations, representing for instance a program loop, when p identical processors are available. For p = 1 we give a simple, efficient, polynomial time algorithm producing optimum results. When p ! 1 the problem becomes NP-hard and a slight modification of our algorithm generates provably close to optimum results. 572 AN OPTIMAL SCHEDULING ALGORITHM WITH A COMPETITIVE FACTOR FOR REALTIME SYSTEMS G. Koren, D. Shasha, July 1991
We consider real-time systems in which the value of a task is proportional to its computation time. The system obtains the value of a given task if the task completes by its deadline. Otherwise, the system obtains no value for the task.
When such a system is underloaded (i.e. there exists a schedule for which all tasks meet their deadlines), Dertouzos showed that the earliest deadline first algorithm will achieve 100% of the possible value. We consider the case of a possibly overloaded system and present an algorithm which: 1. behaves like the earliest deadline first algorithm when the system is underloaded. 2. obtains at least 1/4 of the maximum value that an optimal clairvoyant algorithm could obtain even when the system is overloaded.
We implement our algorithm with an amortized cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant.