The Library
Tighter bound for MULTIFIT scheduling on uniform processors
Tools
Chen, Bo (1991) Tighter bound for MULTIFIT scheduling on uniform processors. Discrete Applied Mathematics, 31 (3). pp. 227-260. doi:10.1016/0166-218X(91)90053-Y ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/0166-218X(91)90053-Y
Abstract
We examine one of the basic, well studied problem of scheduling theory, that of nonpreemptive assignment of independent tasks on m parallel processors with the objective of minimizing the makespan. Because this problem is NP-complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near optimal schedules. Two well-known heuristic algorithms LPT (largest processing time first) and MULTIFIT, shortly MF, find schedules having makespans within 43, 1311, respectively, of the minimum possible makespan, when the m parallel processors are identical. If they are uniform, then the best worst-case performance ratio bounds we know are 1.583, 1.40, respectively. In this paper we tighten the bound to 1.382 for MF algorithm for the uniform-processor system. On the basis of some of our general results and other investigations, we conjecture that the bound could be tightend further to 1.366.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||
Library of Congress Subject Headings (LCSH): | Parallel scheduling (Computer scheduling) -- Mathematical models | ||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||
Publisher: | Elsevier Science Ltd. | ||||||
ISSN: | 0166-218X | ||||||
Official Date: | 1991 | ||||||
Dates: |
|
||||||
Volume: | 31 | ||||||
Number: | 3 | ||||||
Page Range: | pp. 227-260 | ||||||
DOI: | 10.1016/0166-218X(91)90053-Y | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |