Premium
Makespan minimization for m parallel identical processors
Author(s) -
Ho Johnny C.,
Wong Johnny S.
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199509)42:6<935::aid-nav3220420606>3.0.co;2-d
Subject(s) - computer science , job shop scheduling , heuristics , parallel computing , minification , scheduling (production processes) , schedule , lexicographical order , sequence (biology) , algorithm , set (abstract data type) , heuristic , mathematical optimization , mathematics , combinatorics , artificial intelligence , biology , genetics , programming language , operating system
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.