Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound |
| |
Authors: | Christian Artigues Michel Gendreau Louis-Martin Rousseau Adrien Vergnaud |
| |
Affiliation: | 1. LAAS–CNRS, Université de Toulouse, 7 avenue du Colonel Roche, 31077 Toulouse, France;2. CIRRELT, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, Canada QC H3C 3J7 |
| |
Abstract: | We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization. |
| |
Keywords: | Integrated decision problem" target="_blank">gif" overflow="scroll">Integrated decision problem Job-shop scheduling" target="_blank">gif" overflow="scroll">Job-shop scheduling Employee scheduling" target="_blank">gif" overflow="scroll">Employee scheduling Constraint programming Hybrid methods |
本文献已被 ScienceDirect 等数据库收录! |