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

作者：Liao Ching Jong^*; Chao Chien Wen; Lin Chien Hung

来源：European Journal of Operational Research, 2009, 197(2): 475-481.

DOI：10.1016/j.ejor.2008.07.018

• Parallel machine scheduling
• Availability constraints
• 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.

• 出版日期2009-9-1