Article ID: | iaor2003194 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 9 |
Start Page Number: | 1251 |
End Page Number: | 1266 |
Publication Date: | Aug 2002 |
Journal: | Computers and Operations Research |
Authors: | Chen Mingchih, Liaw Ching-Fang, Cheng Chun-Yuan |
Keywords: | heuristics, programming: branch and bound |
This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense; however, it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.