Integer programming and constraint programming in solving a multi-machine assignment scheduling problem with deadlines and release dates

摘要

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 formulation with a global constraint testing single machine feasibility. All the algorithms have been implemented in the Mosel modelling and optimization language.