Integrating constraint propagation technique into branch-and-bound algorithm for job shop scheduling

CSP (constraint satisfactory problem) has the advantage of solving complicated constraints to obtain satisfying solutions, but does not guarantee the quality of the solution. In contrast, Operations Research (OR) has the advantage of obtaining optimization solution or near optimization solution. But it is very difficult to solve the optimization problems with complicated constraints. CPT (constraint propagation technique) is the main search approach of CSP. BAB (branch-and-bound) is one of the optimization algorithms that are usually used in OR. In this paper, we propose a hybrid algorithm that integrated CPT into BAB to solve the job shop scheduling problem with universality and challenge it from a new point of view. The characteristics of this hybrid algorithm focus on improving the optimization performance and the enlarging application area of BAB, by imbedding the dynamic adjustable time window constraints of CSP and search methods of CPT into BAB. Experiments show that hybrid algorithm is promising.