Column generation based approaches for a tour scheduling problem with multi-skill heterogeneous workforce
hal.structure.identifier | Asys [Paris] | |
dc.contributor.author | GÉRARD, Matthieu | |
hal.structure.identifier | Université de Bordeaux [UB] | |
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | CLAUTIAUX, François | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | SADYKOV, Ruslan | |
dc.date.accessioned | 2024-04-04T03:17:15Z | |
dc.date.available | 2024-04-04T03:17:15Z | |
dc.date.created | 2015 | |
dc.date.issued | 2016 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194290 | |
dc.description.abstractEn | In this paper, we address a multi-activity tour scheduling problem with time varying demand. The objective is to compute a team schedule for a fixed roster of employees in order to minimize the over-coverage and the under- coverage of different parallel activity demands along a planning horizon of one week. Numerous complicating constraints are present in our problem: all employees are different and can perform several different activities during the same day-shift, lunch breaks and pauses are flexible, demand is given for 15 minutes periods. Employees have feasibility and legality rules to be satisfied, but the objective function does not account for any quality measure associated with each individual’s schedule. More precisely, the problem mixes simultaneously days-off scheduling, shift scheduling, shift assignment, activity assignment, pause and lunch break assignment.To solve this problem, we developed four methods: a compact Mixed Integer Linear Programming model, a branch-and-price like approach with a nested dynamic program to solve heuristically the subproblems, a diving heuristic and a greedy heuristic based on our subproblem solver. The computational results, based on both real cases and instances derived from real cases, demonstrate that our methods are able to provide good quality solutions in a short computing time. Our algorithms are now embedded in a commercial software, which is already in use in a mini-mart company. | |
dc.language.iso | en | |
dc.publisher | Elsevier | |
dc.title.en | Column generation based approaches for a tour scheduling problem with multi-skill heterogeneous workforce | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1016/j.ejor.2016.01.036 | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
bordeaux.journal | European Journal of Operational Research | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01214652 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01214652v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2016&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=G%C3%89RARD,%20Matthieu&CLAUTIAUX,%20Fran%C3%A7ois&SADYKOV,%20Ruslan&rft.genre=article |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |