We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixed-integer program with a pseudo-polynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.

Scheduling cleaning activities on trains by minimizing idle times / Bartolini, Enrico; Dell'Amico, Mauro; Iori, Manuel. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - 20:(2017), pp. 493-506. [10.1007/s10951-017-0517-1]

Scheduling cleaning activities on trains by minimizing idle times

BARTOLINI, ENRICO;DELL'AMICO, Mauro;IORI, MANUEL
2017

Abstract

We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixed-integer program with a pseudo-polynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.
2017
13-apr-2017
20
493
506
Scheduling cleaning activities on trains by minimizing idle times / Bartolini, Enrico; Dell'Amico, Mauro; Iori, Manuel. - In: JOURNAL OF SCHEDULING. - ISSN 1094-6136. - 20:(2017), pp. 493-506. [10.1007/s10951-017-0517-1]
Bartolini, Enrico; Dell'Amico, Mauro; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
s10951-017-0517-1.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 533.78 kB
Formato Adobe PDF
533.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1131365
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact