The Library
Tighter bound for MULTIFIT scheduling on uniform processors
Tools
Tools
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
Research output not available from this repository, contact author.
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 |
