More Web Proxy on the site http://driver.im/

research-article

A hybrid metaheuristic approach to a real world employee scheduling problem

Authors:

Kenneth N. Reid,

Alexander Brownlee,

Nadarajen Veerapen,

Gilbert OwusuAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1311 - 1318

https://doi.org/10.1145/3321707.3321769

Published: 13 July 2019 Publication History

Abstract

Employee scheduling problems are of critical importance to large businesses. These problems are hard to solve due to large numbers of conflicting constraints. While many approaches address a subset of these constraints, there is no single approach for simultaneously addressing all of them. We hybridise 'Evolutionary Ruin & Stochastic Recreate' and 'Variable Neighbourhood Search' metaheuristics to solve a real world instance of the employee scheduling problem to near optimality. We compare this with Simulated Annealing, exploring the algorithm configuration space using the irace software package to ensure fair comparison. The hybrid algorithm generates schedules that reduce unmet demand by over 28% compared to the baseline. All data used, where possible, is either directly from the real world engineer scheduling operation of around 25,000 employees, or synthesised from a related distribution where data is unavailable.

References

[1]

Baker, K.R.: Workforce allocation in cyclical scheduling problems: A survey. Journal of the Operational Research Society <b>27</b>(1), 155--167 (1976)

[2]

Benlic, U., Burke, E.K., Woodward, J.R.: Breakout local search for the multi-objective gate allocation problem. Computers & Operations Research <b>78</b>, 80--93 (2017)

Digital Library

[3]

Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., De Boeck, L.: Personnel scheduling: A literature review. European Journal of Operational Research <b>226</b>(3), 367--385 (2013)

[4]

Burke, E.K., De Causmaecker, P., De Maere, G., Mulder, J., Paelinck, M., Berghe, G.V.: A multi-objective approach for robust airline scheduling. Computers & Operations Research <b>37</b>(5), 822--832 (2010)

Digital Library

[5]

Burke, E.K., Kendall, G., et al.: Search methodologies. Springer (2005)

[6]

De Bruecker, P., Van den Bergh, J., Beliën, J., Demeulemeester, E.: Workforce planning incorporating skills: State of the art. European Journal of Operational Research <b>243</b>(1), 1--16 (2015)

[7]

El-Yaakoubi, A., El-Fallahi, A., Cherkaoui, M., Hamzaoui, M.R.: Tabu search and memetic algorithms for a real scheduling and routing problem. Logistics Research <b>10</b>(1), 7 (2017)

[8]

Enz, C.: Key issues of concern in the lodging industry: what worries managers. Cornell Hospitality Report <b>9</b>(4), 1--17 (2009)

[9]

Erhard, M., Schoenfelder, J., Fügener, A., Brunner, J.O.: State of the art in physician scheduling. European Journal of Operational Research (2017)

[10]

Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: A review of applications, methods and models. European journal of operational research <b>153</b>(1), 3--27 (2004)

[11]

Fikar, C., Hirsch, P.: Home health care routing and scheduling: A review. Computers & Operations Research <b>77</b>, 86--95 (2017)

Digital Library

[12]

Gendreau, M., Potvin, J.Y.: Handbook of metaheuristics, vol. 2. Springer (2010)

Digital Library

[13]

Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers & operations research <b>13</b>(5), 533--549 (1986)

Digital Library

[14]

Heimerl, C., Kolisch, R.: Scheduling and staffing multiple projects with a multi-skilled workforce. OR spectrum <b>32</b>(2), 343--368 (2010)

[15]

Hoos, H.H.: Programming by optimization. Communications of the ACM <b>55</b>(2), 70--80 (2012)

Digital Library

[16]

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. science <b>220</b>(4598), 671--680 (1983)

[17]

Li, J., Bai, R., Shen, Y., Qu, R.: Search with evolutionary ruin and stochastic rebuild: A theoretic framework and a case study on exam timetabling. European Journal of Operational Research <b>242</b>(3), 798--806 (2015)

[18]

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Birattari, M., Stützle, T.: The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives <b>3</b>, 43--58 (2016)

[19]

Mladenović, N., Hansen, P.: Variable neighborhood search. Computers & operations research <b>24</b>(11), 1097--1100 (1997)

Digital Library

[20]

Pinedo, M., Zacharias, C., Zhu, N.: Scheduling in the service industries: An overview. Journal of Systems Science and Systems Engineering <b>24</b>(1), 1--48 (2015)

[21]

Rahimian, E., Akartunalı, K., Levine, J.: A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems. European Journal of Operational Research <b>258</b>(2), 411--423 (2017)

[22]

Reid, K.N., Li, J., Swan, J., McCormick, A., Owusu, G.: Variable neighbourhood search: A case study for a highly-constrained workforce scheduling problem. In: Computational Intelligence (SSCI), 2016 IEEE Symposium Series on. pp. 1--6. IEEE (2016)

[23]

Reid, K.N., Li, J., Veerapen, N., Swan, J., McCormick, A., Kern, M., Owusu, G.: Shift scheduling and employee rostering: An evolutionary ruin & recreate solution. In: 10th Computer Science and Electronic Engineering Conference (CEEC). pp. 19--23. IEEE (2018)

[24]

Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., Dueck, G.: Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics <b>159</b>(2), 139--171 (2000)

Digital Library

[25]

Simeonova, L., Wassan, N., Salhi, S., Nagy, G.: The heterogeneous fleet vehicle routing problem with light loads and overtime: Formulation and population variable neighbourhood search with adaptive memory. Expert Systems with Applications (2018)

Cited By

Fyvie MMccall JChristie LBrownlee ASilva SPaquete L(2023)Explaining a Staff Rostering Genetic Algorithm using Sensitivity Analysis and Trajectory Analysis.Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596353(1648-1656)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596353
Fyvie MMcCall JChristie LZăvoianu ABrownlee AAinslie R(2023)Explaining a Staff Rostering Problem by Mining Trajectory Variance StructuresArtificial Intelligence XL10.1007/978-3-031-47994-6_27(275-290)Online publication date: 8-Nov-2023
https://doi.org/10.1007/978-3-031-47994-6_27
Khosravi SChalechale A(2022)Chimp Optimization Algorithm to Optimize a Convolutional Neural Network for Recognizing Persian/Arabic Handwritten WordsMathematical Problems in Engineering10.1155/2022/48949222022(1-12)Online publication date: 12-Apr-2022
https://doi.org/10.1155/2022/4894922
Show More Cited By

Index Terms

A hybrid metaheuristic approach to a real world employee scheduling problem
1. Applied computing
  1. Operations research
    1. Industry and manufacturing
2. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Randomized search

Recommendations

Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties

This paper considers an unrelated parallel machine scheduling problem with the objective of minimizing the total earliness and tardiness penalties. Machine and job-sequence dependent setup times and idle times are considered. Since the studied problem ...
Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in permutation flow shop scheduling problems. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation ...
Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach

This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search (TS), simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

July 2019

1545 pages

ISBN:9781450361118

DOI:10.1145/3321707

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Engineering and Physical Sciences Research Council

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fyvie MMccall JChristie LBrownlee ASilva SPaquete L(2023)Explaining a Staff Rostering Genetic Algorithm using Sensitivity Analysis and Trajectory Analysis.Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596353(1648-1656)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596353
Fyvie MMcCall JChristie LZăvoianu ABrownlee AAinslie R(2023)Explaining a Staff Rostering Problem by Mining Trajectory Variance StructuresArtificial Intelligence XL10.1007/978-3-031-47994-6_27(275-290)Online publication date: 8-Nov-2023
https://doi.org/10.1007/978-3-031-47994-6_27
Khosravi SChalechale A(2022)Chimp Optimization Algorithm to Optimize a Convolutional Neural Network for Recognizing Persian/Arabic Handwritten WordsMathematical Problems in Engineering10.1155/2022/48949222022(1-12)Online publication date: 12-Apr-2022
https://doi.org/10.1155/2022/4894922
Baseri Saadi STataei Sarshar NSadeghi SRanjbarzadeh RKooshki Forooshani MBendechache M(2022)Investigation of Effectiveness of Shuffled Frog-Leaping Optimizer in Training a Convolution Neural NetworkJournal of Healthcare Engineering10.1155/2022/47036822022(1-11)Online publication date: 23-Mar-2022
https://doi.org/10.1155/2022/4703682
Nguyen TNguyen GNguyen B(2020)EO-CNN: An Enhanced CNN Model Trained by Equilibrium Optimization for Traffic Transportation PredictionProcedia Computer Science10.1016/j.procs.2020.09.075176(800-809)Online publication date: 2020
https://doi.org/10.1016/j.procs.2020.09.075

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents