Premium
SCHEDULING TO MINIMIZE MAKESPAN ON UNEQUAL PARALLEL PROCESSORS
Author(s) -
De Prabuddha,
Morton Thomas E.
Publication year - 1980
Publication title -
decision sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.238
H-Index - 108
eISSN - 1540-5915
pISSN - 0011-7315
DOI - 10.1111/j.1540-5915.1980.tb01163.x
Subject(s) - heuristics , job shop scheduling , computer science , scheduling (production processes) , mathematical optimization , heuristic , simple (philosophy) , parallel computing , mathematics , routing (electronic design automation) , computer network , philosophy , epistemology
The problem of scheduling n independent jobs on m unequal parallel processors to minimize makespan is known to be very difficult for the nonpreemptive case. Until recently, research on this problem has consisted primarily of investigating the “worst case” behavior for simple approximation algorithms for the special cases of equal or uniform processors. Recently, Ibarra and Kim [10] have completed a similar analysis on five simple heuristics for general unequal processors. The approach in the present paper is to investigate the “average” behavior via large‐scale computational testing. A new heuristic is devised. It is tested on a large number of problems (about 9,000) for both uniform and general processors, and the results are compared with the best solutions obtained from a truncated branch‐and‐bound procedure. It is observed that, although the heuristic takes negligible time compared to the branch‐and‐bound procedure, on the average it is within 5 percent of the latter in the uniform case and within 1.3 percent in the general case. It also performs better than a composite heuristic whose output, for any given problem, is the best of all previously suggested heuristics.