New Bounds for the Identical Parallel Processor Weighted Flow Time Problem

Scott Webster
Additional contact information
Scott Webster: School of Business, University of Wisconsin-Madison, Madison, Wisconsin 53706

Management Science, 1992, vol. 38, issue 1, 124-136

Abstract: In 1964, Eastman, Even, and Isaacs (EEI) presented a polynomial time lower bound for the NP-hard problem of scheduling n jobs on m available and identical processors to minimize weighted flow time. A general bound, of which the EEI bound is a special case, is proposed. Four new bounds for the identical processor problem are given. All of the new bounds can be applied to problems with variable processor ready times. The EEI bound is limited to problems where all processors are initially available at the same time. Two of the four new bounds are shown to dominate the EEI bound. The two other bounds are found to be effective for a particular problem class. Two polynomial time lower bounds for problems with nonidentical processors are introduced. One bound is applicable to the uniform processor problem, the other bound can be applied to the general processor problem. No bounds have previously been proposed for these problems.

Keywords: scheduling; parallel processors; deterministic; bounds (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.38.1.124 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:38:y:1992:i:1:p:124-136

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().