Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Request Changes to record.

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:
DateEvent
1991Published
25 July 1989Submitted
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us