A decomposition-based heuristic for large employee scheduling problems with inter-department transfers

We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under study, each department generally covers its demand in employees over the planning horizon of a week by assigning shifts to its own staff. Howe...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Dalia Attia, Reinhard Bürgy, Guy Desaulniers, François Soumis
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	90B35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/cec71d8ac0fa4315b597c5df966cf960
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:cec71d8ac0fa4315b597c5df966cf960
record_format	dspace
spelling	oai:doaj.org-article:cec71d8ac0fa4315b597c5df966cf9602021-12-02T05:01:13ZA decomposition-based heuristic for large employee scheduling problems with inter-department transfers2192-440610.1007/s13675-019-00119-3https://doaj.org/article/cec71d8ac0fa4315b597c5df966cf9602019-12-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001209https://doaj.org/toc/2192-4406We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under study, each department generally covers its demand in employees over the planning horizon of a week by assigning shifts to its own staff. However, the employees can also be transferred to other departments under certain conditions for executing entire shifts or parts of shifts there. The transfer feature enables to improve the overall schedule quality considerably when compared to the nontransfer case. Given the complexity of the problem, we propose a three-phase decomposition-based heuristic. In the first phase, we consider each department separately and solve a simplified version of the mono-department scheduling problems. From the obtained solutions, we deduce inter-department shifts that could potentially reduce the overall cost. This is examined in the second phase by resolving the scheduling problem of the first phase where the deduced inter-department shifts are included. In this phase, however, we decompose the scheduling problem by time, looking at each day separately. From the obtained schedules, we then devise inter-department demand curves, which specify the number of transfers between departments over time. In the third phase, we decompose the initial scheduling problem into mono-department problems using these inter-department demand curves. Consequently, our approach makes it possible to solve mono-department optimization problems to get an overall schedule while still benefiting from the employee transfer feature. In all three phases, the scheduling problems are formulated as mixed-integer linear programs. We show through extensive computational experiments on instances with up to 25 departments and 1000 employees that the method provides high-quality solutions within reasonable computation times.Dalia AttiaReinhard BürgyGuy DesaulniersFrançois SoumisElsevierarticle90B35Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 4, Pp 325-357 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B35 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Dalia Attia Reinhard Bürgy Guy Desaulniers François Soumis A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
description	We consider a personalized employee scheduling problem with characteristics present in retail stores consisting of multiple departments. In the setting under study, each department generally covers its demand in employees over the planning horizon of a week by assigning shifts to its own staff. However, the employees can also be transferred to other departments under certain conditions for executing entire shifts or parts of shifts there. The transfer feature enables to improve the overall schedule quality considerably when compared to the nontransfer case. Given the complexity of the problem, we propose a three-phase decomposition-based heuristic. In the first phase, we consider each department separately and solve a simplified version of the mono-department scheduling problems. From the obtained solutions, we deduce inter-department shifts that could potentially reduce the overall cost. This is examined in the second phase by resolving the scheduling problem of the first phase where the deduced inter-department shifts are included. In this phase, however, we decompose the scheduling problem by time, looking at each day separately. From the obtained schedules, we then devise inter-department demand curves, which specify the number of transfers between departments over time. In the third phase, we decompose the initial scheduling problem into mono-department problems using these inter-department demand curves. Consequently, our approach makes it possible to solve mono-department optimization problems to get an overall schedule while still benefiting from the employee transfer feature. In all three phases, the scheduling problems are formulated as mixed-integer linear programs. We show through extensive computational experiments on instances with up to 25 departments and 1000 employees that the method provides high-quality solutions within reasonable computation times.
format	article
author	Dalia Attia Reinhard Bürgy Guy Desaulniers François Soumis
author_facet	Dalia Attia Reinhard Bürgy Guy Desaulniers François Soumis
author_sort	Dalia Attia
title	A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
title_short	A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
title_full	A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
title_fullStr	A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
title_full_unstemmed	A decomposition-based heuristic for large employee scheduling problems with inter-department transfers
title_sort	decomposition-based heuristic for large employee scheduling problems with inter-department transfers
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/cec71d8ac0fa4315b597c5df966cf960
work_keys_str_mv	AT daliaattia adecompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT reinhardburgy adecompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT guydesaulniers adecompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT francoissoumis adecompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT daliaattia decompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT reinhardburgy decompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT guydesaulniers decompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers AT francoissoumis decompositionbasedheuristicforlargeemployeeschedulingproblemswithinterdepartmenttransfers
_version_	1718400855036657664

A decomposition-based heuristic for large employee scheduling problems with inter-department transfers

Ejemplares similares