Tuesday, 13:45 - 14:10 h, Room: H 3003A


Chris Beck
Loosely coupled hybrids: Tabu search, constraint programming and mixed integer programming for job shop scheduling

Coauthors: Ti K. Feng, Wen-Yang Ku, Jean-Paul Watson


Since their introduction, metaheuristic algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming (CP) community and substantial increase in the power of commercial mixed integer programming (MIP) solvers. Building on observations of the performance characteristics of metaheuristic, CP, and MIP solvers, we investigate simple, loosely coupled hybrid algorithms for job-shop scheduling. Our hypothesis is that the fast, broad search capabilities of modern tabu search algorithms are able to very quickly converge on a set of very good, but likely sub-optimal, solutions. CP or MIP can then be seeded with these solutions to improve them and search for optimality proofs.


Talk 2 of the invited session Tue.2.H 3003A
"CP hybrids for scheduling" [...]
Cluster 5
"Constraint programming" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Buy Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.