Graph Coloring based Heuristic for Crew Rostering
- 19 August 2020
- journal article
- research article
- Published by University of Szeged in Acta Cybernetica
- Vol. 24 (4) , 643-661
Abstract
In the last years personnel cost became a huge factor in the financial management of many companies and institutions.The firms are obligated to employ their workers in accordance with the law prescribing labour rules. The companies can save costs with minimizing the differences between the real and the expected worktimes. Crew rostering is assigning the workers to the previously determined shifts, which has been widely studied in the literature. In this paper, a mathematical model of the problem is presented and a two-phase graph coloring method for the crew rostering problem is introduced. Our method has been tested on artificially generated and real life input data. The results of the new algorithm have been compared to the solutions of the integer programming model for moderate-sized problems instances.Keywords
This publication has 22 references indexed in Scilit:
- Personnel scheduling: A literature reviewEuropean Journal of Operational Research, 2013
- Solving large scale crew scheduling problems in practicePublic Transport, 2011
- A dynamic programming algorithm for days-off scheduling with sequence dependent labor costsJournal of Scheduling, 2007
- A graph coloring model for a feasibility problem in monthly crew scheduling with preferential biddingComputers & Operations Research, 2007
- Interval scheduling: A surveyNaval Research Logistics (NRL), 2007
- Survey, Categorization, and Comparison of Recent Tour Scheduling LiteratureAnnals of Operations Research, 2004
- Staff scheduling and rostering: A review of applications, methods and modelsEuropean Journal of Operational Research, 2004
- On the complexity of manpower shift schedulingComputers & Operations Research, 1996
- Michael R. ΠGarey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco1979, x + 338 pp.The Journal of Symbolic Logic, 1983
- New methods to color the vertices of a graphCommunications of the ACM, 1979