Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound Export

@article{citeulike:4383805, 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.}, author = {Artigues, C. and Gendreau, M. and Rousseau, L. and Vergnaud, A.}, citeulike-article-id = {4383805}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.cor.2008.08.013}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0305054808001445}, doi = {10.1016/j.cor.2008.08.013}, issn = {03050548}, journal = {Computers \& Operations Research}, keywords = {branch, heuristics, jobshop, phd, scheduling}, month = {August}, number = {8}, pages = {2330--2340}, posted-at = {2009-04-23 08:47:51}, priority = {2}, title = {Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound}, url = {http://dx.doi.org/10.1016/j.cor.2008.08.013}, volume = {36}, year = {2009} }

TY - JOUR ID - citeulike:4383805 L3 - citeulike-article-id:4383805 N2 - 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. IS - 8 JF - Computers & Operations Research SN - 03050548 EP - 2340 TI - Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound VL - 36 SP - 2330 KW - branch KW - heuristics KW - jobshop KW - phd KW - scheduling AU - Artigues, C AU - Gendreau, M AU - Rousseau, L AU - Vergnaud, A PY - 2009/08// UR - http://dx.doi.org/10.1016/j.cor.2008.08.013 ER -