Article ID: | iaor20013901 |
Country: | United Kingdom |
Volume: | 28 |
Issue: | 7 |
Start Page Number: | 705 |
End Page Number: | 717 |
Publication Date: | Jun 2001 |
Journal: | Computers and Operations Research |
Authors: | Ho Johnny C., Gupta Jatinder N.D. |
Keywords: | optimization, heuristics |
We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a cumputational study to compare the performance of the proposed algorithms with a known heuristic show that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.