Approximation Algorithms For Scheduling On Uniform Processors
- 1 February 1993
- journal article
- research article
- Published by Taylor & Francis in INFOR: Information Systems and Operational Research
- Vol. 31 (1) , 16-23
- https://doi.org/10.1080/03155986.1993.11732210
Abstract
The problem of scheduling independent tasks on uniform processors in order to minimize the maximum completion time of the schedule is strongly NP-complete. Therefore, the existence of a polynomial or even a pseudo-polynomial time algorithm is very unlikely unless P = NP. This paper deals with approximation schemes which attempt to find a solution in polynomial time that is close to the optimal solution. Specifically, two variants of LPT scheduling are shown: one which is polynomial time and the other a probabilistically good algorithm.Keywords
This publication has 0 references indexed in Scilit: