Integer Programming and Constraint Programming in Solving a Multimachine Assignment Scheduling Problem with Deadlines and Release Dates

INFORMS Journal on Computing · 2006 · Volume 18 · Issue 2

Abstract

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.

Keywords

hybrid algorithms, integer programming, constraint programming, multimachine scheduling

Enable JavaScript for citation tools and additional paper interactions.