Makespan minimization for m parallel identical processors

Johnny C. Ho and Johnny S. Wong

Naval Research Logistics (NRL), 1995, vol. 42, issue 6, 935-948

Abstract: We introduce an algorithm, called TMO (Two‐Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest‐processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m‐machine problem into a set of two‐machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.

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

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199509)42:63.0.CO;2-D

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:42:y:1995:i:6:p:935-948

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 ().