Scheduling of parallel processors: A posterior bound on LPT sequencing and a two‐step algorithm

James D. Blocher and Suresh Chand

Naval Research Logistics (NRL), 1991, vol. 38, issue 2, 273-287

Abstract: This article considers the problem of scheduling parallel processors to minimize the makespan. The article makes two key contributions: (1) It develops a new lower bound on the makespan for an optimal schedule, and (2) it proposes an efficient two‐step algorithm to find schedules of any desired accuracy, or percent above optimal. In addition, a posterior bound on LPT (longest processing time) sequencing is developed in the article. It is proved that this bound dominates the previously reported bounds on LPT sequencing.

Date: 1991
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199104)38:23.0.CO;2-A

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:wly:navres:v:38:y:1991:i:2:p:273-287

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().