Article ID: | iaor20012753 |
Country: | Netherlands |
Volume: | 34 |
Issue: | 4 |
Start Page Number: | 793 |
End Page Number: | 806 |
Publication Date: | Sep 1998 |
Journal: | Computers & Industrial Engineering |
Authors: | Dessouky M.M. |
We consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 100,000 iterations with n less than or equal to 80 and m less than or equal to 3. For larger values of m, the heuristics provided approximate solutions close to the optimal values.