An improved tabu search method for the weighted constraint satisfaction problem

Aiming at developing a general problem solver for combinatorial optimizatio n problems, we consider in this paper the weighted constraint satisfaction problem (WCSP), which, given a number of constraints and their weights of i mportance, asks to minimize the total weight of unsatisfied constraints. We propose a tabu search algorithm for WCSP with the features that it uses an evaluation function, defined in terms of the modified weights of constrain ts, for guiding the search, and that it incorporates an automatic control m echanism of the weights in the evaluation function. Using this code, we sol ved a number of problems including those from real applications such as gen eralized assignment, set covering, parallel shop scheduling, timetabling an d nurse scheduling. Many problems that arise in cellular manufacturing can also be formulated as WCSP, including the problems of cell formation and to ol selection. Our computational results indicate that the control mechanism of weights makes our tabu search more powerful, and our algorithm is pract ically usable.