Rescheduling to minimize makespan on a changing number of identical processors

Craig A. Tovey

Naval Research Logistics Quarterly, 1986, vol. 33, issue 4, 717-724

Abstract: We consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP‐hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.

Date: 1986
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800330414

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:navlog:v:33:y:1986:i:4:p:717-724

Access Statistics for this article

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