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

 

Abstract:
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" [...]

 

  cash advance . If you have already decided to take Levitra For Sale, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.