Oscar H. Ibarra
Abstract
The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n.
- 1 BRUNO, J , COFFMAN, E G. JR, AND SETHI, R. Scheduhng independent tasks to reduce mean finishing time. Cumin ACM 17, 7 (July 1974), 382-387 Google Scholar
- 2 BRUNO, J , COFFMAN, E G. JR , AND SETHI, R Algorithm for mmlmizang mean flow time information Processing 74, North-Holland, Amsterdam, pp 504-510Google Scholar
- 3 COFFMAN, E.G. JR, AND SETHI, R A generalized bound on LPT sequencing Proc Int. Syrup. Comptr{ Performance Modehng, Measurement and Evaluation, March 1976, pp 306-317. (available from ACM). Google Scholar
- 4 CONWAY, R W., MAXWELL, W L , AND MILLER, L W Theory of Scheduhng, Addison-Wesley Pubhshmg Co , Reading, Mass , 1967Google Scholar
- 5 GONZALEZ, T, IBARRA, O H , AND SAHNI, S Bounds for LPT schedules on uniform processors. Comptr Scl Tech Pep No 75-1, U of Minnesota, Mmneapohs, Minn , 1974Google Scholar
- 6 GRAHAM, R L Bounds on multlprocessmg timing anomalies. SIAM J Apphed Math 17, 2 (March 1969), 416-429Google Scholar
- 7 HOROWlTZ, E, AND SAHNt, S Exact and approximate algorithms for scheduhng nomdentlcal processors I ACM 23, 2 (Apnl 1976), 317-327 Google Scholar
- 8 KARP, R M Reducibility among combinatorial problems In Complexity of Computer Computatlons, R E Miller and J W. Thatcher, Eds , Plenum Press, New York, 1972, pp, 85-103Google Scholar
- 9 SAHNI, S Computatlonally related problems SIAM J Comptg 3, 4 (Dec 1974), 262-279Google Scholar
Index Terms
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
Recommendations
Scheduling Independent Multiprocessor Tasks
We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model,...
Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors
In this paper we consider the problem of scheduling “n” independent fades on “m” parallel processors. Each job consists of a single operation with a specific processing time and due date. The processors are identical and the operation of the system is ...
Comments