Solving the open shop scheduling problem

Only few exact solution methods are available for the open shop scheduling problem. We describe a branch-and-bound algorithm for solving this problem which performs better than other existing algorithms. The key to the effici ency of our algorithm lies in the following approach: instead of analysing and improving the search strategies for finding solutions, we focus on cons traint propagation based methods for reducing the search space. Extensive c omputational experiments on several sets of well-known benchmark problem in stances are reported. For the first time, many problem instances are solved to optimality in a short amount of computation time. Copyright (C) 2001 Jo hn Wiley & Sons, Ltd.