Minimizing the sum of job completion times on capacitated two-parallel machines

• DOI: 10.1016/j.ejor.2008.07.018
• Publication Date: 2008-07-30T08:33:34Z
• Authors: Ching-Jong Liao; Chien-Wen Chao; Chien-Hung Lin
• Keywords: 0209 industrial biotechnology; Parallel machine scheduling; Availability constraints; 02 engineering and technology; Branch and bound algorithm

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.