Article ID: | iaor20071193 |
Country: | United States |
Volume: | 18 |
Issue: | 2 |
Start Page Number: | 209 |
End Page Number: | 217 |
Publication Date: | Mar 2006 |
Journal: | INFORMS Journal On Computing |
Authors: | Wolsey Laurence A., Sadykov Ruslan |
Keywords: | programming: constraints, programming: integer |
We consider both branch-and-cut and column-generation approaches for the problem of finding a minimum-cost assignment of jobs with release dates and deadlines to unrelated parallel machines. Results are presented for several variants both with and without constraint programming. Among the variants, the most effective strategy is to combine a tight and compact, but approximate, mixed integer programming (MIP) formulation with a global constraint testing single machine feasibility. Instances with up to nine machines and 54 jobs have been solved. All the algorithms have been implemented in the Mosel modeling and optimization language.