Makespan minimization for m parallel identical processors

Makespan minimization for m parallel identical processors

0.00 Avg rating0 Votes
Article ID: iaor1996502
Country: United States
Volume: 42
Issue: 6
Start Page Number: 935
End Page Number: 948
Publication Date: Sep 1995
Journal: Naval Research Logistics
Authors: ,
Abstract:

The authors 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, the authors 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.

Reviews

Required fields are marked *. Your email address will not be published.