Methods for Solving Practical Problems of Job-Shop Scheduling Modelled in CLP(FD)

Constraint logic programming with linear constraints over finite integer domains, CLP(FD), has been established as a practical tool for solving discrete scheduling problems. A scheduling problem can be suitably modelled in terms of a set of constraints. To generate a solution, however, a search is neccessary, and the choice of an adequate strategy is a problem. The goal of our investigations is the development of methods for solving job-shop scheduling problems using CLP(FD) such that good (near-to-optimum) solutions can be fast computed. At first, a generalization of the "labelling" search strategy is described. The assignment of a value to the selected variable is replaced by reduction of the domain of the variable. Furthermore, the following basic search method is proposed: the number of permitted backtracking steps is restricted and different heuristics are tried out. Our experience has shown that the domain-reducing strategy is suitable as a basic search strategy for solving job-s..