Integrating CPT into BAB algorithm for job shop scheduling
Mengguang Wang · Guanli kexue xuebao · 2005
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, OR (operation research) 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 the improving of 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.