Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
Authors:
- Bryan L. DeuermeyerBDBryan L. Deuermeyer
- Donald K. FriesenDFDonald K. Friesen
- Michael A. LangstonMLMichael A. Langston
- 1 June 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 3 (2) , 190-196
Abstract
This investigation considers the problem of nonpreemptively assigning a set of independent tasks to a system of identical processors to maximize the earliest processor finishing time. While this goal is a nonstandard scheduling criterion, it does have natural applications in certain maintenance scheduling and deterministic fleet sizing problems. The problem is NP-hard, justifying an analysis of heuristics such as the well-known LPT algorithm in an effort to guarantee near-optimal results. It is proved that the worst-case performance of the LPT algorithm has an asymptotically tight bound of $\frac{4}{3}$ times the optimal.
Keywords
This publication has 4 references indexed in Scilit:
- Analysis of Greedy Solutions for a Replacement Part Sequencing ProblemMathematics of Operations Research, 1981
- An Application of Bin-Packing to Multiprocessor SchedulingSIAM Journal on Computing, 1978
- On a Fleet Sizing and Allocation ProblemManagement Science, 1977
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969