ARTE: Artificial Intelligence in Employee Scheduling 

This project is supported by the Austrian Science Fund (project: P24814-N23)

FWF

 

 

Project Goals

Work schedules influence the lives of each of us. On the one hand an unsuitable timetable can have a tremendous negative impact on one's health, social life, and motivation at work. On the other hand, organizations in the commercial and public sector must meet their workforce requirements and ensure the quality of their services and operations. Therefore, the task of finding appropriate staff schedules is of great importance for society. However, this is a tremendously complex task due to the huge number of constraints that have to be fulfilled (e.g. labor rules, individual employee preferences, and requirements of companies) and the enormous search space of possible solutions. Such complex problems appear especially in companies where the required number of employees throughout the time periods fluctuates, which operate 24 hours per day, and deal with critical tasks (e.g., air traffic control, personnel working in emergency services, call centers, etc.).

 

Traditionally, the general employee scheduling problems have been solved in separated phases which include several sub-problems, each of which are NP-hard (e.g., shift scheduling, break scheduling, workforce scheduling, etc.). Such an approach reduces the complexity for solving the problem, but requires the use of a human expert. Furthermore, the sub-problems are strongly interleaved between each other, and solutions which are optimal overall can not be guaranteed due to the early decisions made in the sub-problem solutions. One of the main open challenging questions in general employee scheduling is: Can we fully automate the general employee scheduling problem and obtain high quality solutions without the help of human expert?

 

In this project we will tackle exactly this challenge. We aim to make significant progress in solving employee scheduling in general and propose methods that can be used for a broad range of such problems. Our ambitious aims require fundamental research on developing of new intelligent search methods that can deal with such complex tasks.

 

 

 

Team

Project leader

Nysret Musliu

 

Ph.D. and Master Students

Emir Demirovic

Lucas Kletzander

Florian Mischek

Felix Winter

Christoph Erkinger (November 2013)

 

Ph.D. and Master students supervised in this project

Lucas Kletzander. A Heuristic Solver Framework for the General Employee Scheduling Problem. Master Thesis, TU Wien, 2018.

Martin Blöschl. A Graphical Environment for Creating Constraint Programming Models. Master Thesis, TU Wien, 2018.

Bernd-Peter Ivanschitz. Algorithm Selection and Runtime Prediction for the two Dimensional Bin Packing Problem. Master Thesis, TU Wien, 2017.

Emir Demirovic, Hybrid Search Techniques for the High School Timetabling Problem. Ph.D. Thesis, TU Wien, Vienna PhD School of Informatics, March 2017

Michael Abseher, Tailored Tree Decompositions for Efficient Problem Solving. Ph.D. Thesis, TU Wien, April 2017 (co-supervised with Stefan Woltran)

Florian Mischek. Exact and Heuristic Approaches for a Multi-Stage Nurse Rostering. Master Thesis, TU Wien, 2016. (His master thesis was selected as one of the four best master theses finished in Winter Semester 2017 at the Faculty of Informatics, TU Wien)

Felix Winter. MaxSAT Modeling and Metaheuristic Methods for the Employee Scheduling Problem. Master Thesis, TU Wien, 2016. (Winner of the “Distinguished Young Alumnus/Alumna”-Award for the best master thesis finished in Summer Semester 2016 at the Faculty of Informatics, TU Wien)

Maria-Elisabeth Zueger. Large Neighborhood Search for Break Scheduling. Master Thesis, TU Wien, 2016.

Deniz Kocabas. Exact Methods for Shift Design and Break Scheduling. Master Thesis,Vienna University of Technology, 2015.

Kevin Bader. Memetic Algorithms for Tree Decomposition. Master Thesis,Vienna University of Technology, 2014.  

Christoph Erkinger. Rotating Workforce Scheduling As Satisfiability Modulo Theories. Master Thesis, Vienna University of Technology, 2013.

Martin Schwengerer. Algorithm Selection for the Graph Coloring Problem. Master Thesis, TU Wien, 2012. (Winner of “Best Poster-Award”  at the Faculty of Informatics, Vienna University of Technology, Nov. 2012)

Josef Pihera, Machine Learning Techniques Applied to Combinatorial Search Problems, TU Wien, Vienna PhD School of Informatics, 2013 –

 

 

Publications

Nysret Musliu, Andreas Schutt, Peter J. Stuckey. Solver Independent Rotating Workforce Scheduling. CPAIOR 2018: The 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, June 26-29, 2018, Delft, The Netherlands.

Lucas Kletzander, Nysret Musliu. Solving the General Employee Scheduling Problem. The 12th International Conference on the Practice and Theory of Automated Timetabling, August 28-31, 2018, Vienna, Austria. Long version of the paper submitted to a journal.

Lucas Kletzander, Florian Mischek, Nysret Musliu, Gerhard Post and Felix Winter. A General Modeling Format for Employee Scheduling. Technical Report, DBAI-TR-2017-109, TU Wien, 2017.

Florian Mischek, Nysret Musliu. Integer programming model extensions for a multi-stage nurse rostering problem. Annals of Opererations Research (2017). https://doi.org/10.1007/s10479-017-2623-z

Emir Demirovic, Nysret Musliu, Felix Winter. Modeling and solving staff scheduling with partial weighted maxSAT. Annals of Opererations Research (2017). https://doi.org/10.1007/s10479-017-2693-y

Christoph Erkinger, Nysret Musliu. Personnel Scheduling as Satisfiability Modulo Theories. The 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, 2017.

Michael Abseher, Nysret Musliu and Stefan Woltran. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. Journal of Artificial Intelligence Research, Volume 58, pages 1-30, 2017

Alex Bonutti, Sara Ceschia, Fabio De Cesco, Nysret Musliu and Andrea Schaerf. Modeling and Solving a Real-Life Multi-Skill Shift Design Problem. Annals of Operations Research, Volume 252, Issue 2, pp 365–382, 2017, doi:10.1007/s10479-016-2175-7

Nysret Musliu, Felix Winter. A Hybrid Approach for the Sudoku problem: Using Constraint Programming in Iterated Local Search. IEEE Intelligent Systems, Volume 32, Issue 2, pp 52-62, 2017

Emir Demirovic and Nysret Musliu. MaxSAT Based Large Neighborhood Search for High School Timetabling. Computers and Operations Research, Volume 78, February 2017, Pages 172–180.

Emir Demirovic, Nysret Musliu. Modeling High School Timetabling with Bitvectors. Annals of Operations Research, Volume 252, Issue 2, pp 215–238, 2017.

Lucas Kletzander, Nysret Musliu. A Multi-stage Simulated Annealing Algorithm for the Torpedo Scheduling Problem. CPAIOR 2017: The Fourteenth International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, Padova, Italy, June 5 - June 8, 2017. (The original publication is available at www.springerlink.com)

Michael Abseher, Nysret Musliu, Stefan Woltran. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. CPAIOR 2017: The Fourteenth International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, Padova, Italy, June 5 - June 8, 2017. (The original publication is available at www.springerlink.com)

Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub, Stefan Woltran: Shift Design with Answer Set Programming. Fundamenta Informaticae, 147(1): 1-25, 2016, 2016.

Florian Mischek, Nysret Musliu. Integer Programming and Heuristic Approaches for a Multi-Stage Nurse Rostering Problem. Proceedings of PATAT 2016 - The 11th International Conference on the Practice and Theory of Automated Timetabling, Udine, August 23 - 26, 2016

Emir Demirovic, Nysret Musliu, Felix Winter. Modeling and solving staff scheduling with partial weighted maxSAT. Proceedings of PATAT 2016 - The 11th International Conference on the Practice and Theory of Automated Timetabling, Udine, August 23 - 26, 2016

Emir Demirović, Théo Le Calvar, Nysret Musliu, and Katsumi Inoue. An Exact Algorithm for Unicost Set Covering.  Doctoral Program of the 22nd International Conference on the Principles and Practice of Constraint Programming (CP 2016).

Michael Abseher, Frederico Dusberger, Nysret Musliu, Stefan Woltran. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015.

Thomas Hammerl, Nysret Musliu, and Werner Schafhauser. Metaheuristic Algorithms and Tree Decomposition. Handbook of Computational Intelligence, Kacprzyk, Janusz, Pedrycz, Witold (Eds.,), Springer, 2015. (The original publication is available at www.springerlink.com)

Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub and Stefan Woltran. Shift-design with Answer Set Programming. Proceeding of the 13th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2015), Lexington, KY, USA September 27-30, 2015. Lecture Notes in Artificial Intelligence (LNAI), Volume 9345, Springer, 2015. (The original publication is available at www.springerlink.com)

Extended version of paper: Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub and Stefan Woltran. Shift Design with Answer Set Programming.  The Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), Cork, Ireland , August 31, 2015.

Luca Di Gaspero, Johannes Gärtner, Nysret Musliu, Andrea Schaerf, Werner Schafhauser, and Wolfgang Slany. Automated Shift Design and Break Scheduling. Automated Scheduling and Planning, Studies in Computational Intelligence,Volume 505, 2013, pp 109-127. E. Ozcan, N. Urquhart, S. Uyar (Eds.) (The original publication is available at www.springerlink.com)

Alex Bonutti, Fabio De Cesco, Nysret Musliu and Andrea Schaerf. Modeling and Solving a Real-Life Multi-Skill Shift Design Problem. Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, pages 459-461, York, UK, August 26-29, 2014.

Josef Pihera, Nysret Musliu. Application of Machine Learning to Algorithm Selection for TSP. Proceeding of the IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI), Limassol, Cyprus, November 10-12, 2014.

Emir Demirovic, Nysret Musliu. Modeling High School Timetabling as PartialWeighted maxSAT. LaSh 2014: The 4th Workshop on Logic and Search (a SAT / ICLP workshop at FLoC 2014), July 18, 2014, Vienna, Austria.

Emir Demirovic and Nysret Musliu. Solving High School Timetabling with Satisfiability Modulo Theories. Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, pages 142-166, York, UK, August 26-29, 2014.

Jussi Rasku, Nysret Musliu, and Tommi Kärkkäinen. Automating the Parameter Selection in VRP: An Off-line Parameter Tuning Tool Comparison. Modeling, Simulation and Optimization for Science and Technology. Computational Methods in Applied Sciences Volume 34, 2014, pp 191-209.

Magdalena Widl, Nysret Musliu. The Break Scheduling Problem: Complexity Results and Practical Algorithms. Memetic Computing, 6(2): 97-112, 2014. (The final publication is available at http://link.springer.com)

Nysret Musliu, Martin Schwengerer. Algorithm Selection for the Graph Coloring Problem. Learning and Intelligent OptimizatioN Conference (LION 7), Catania - Italy, Jan 7-11, 2013. Lecture Notes in Computer Science, to appear.

Nysret Musliu. Analyzing the Features of Employee Scheduling Problems (abstract). XXVI EURO - INFORMS Joint International Conference, Rome, July 1 - 4, 2013.

Nysret Musliu. Applying Machine Learning for Solver Selection in Scheduling. 10th Metaheuristics International Conference (MIC 2013), Singapore, 5-8 August, 2013.

D. Bucar, S. Bessler, N. Musliu, J. Groenbaek. Scheduling of electric vehicle charging operations. MISTA - Multidisciplinary International Scheduling Conference: Theory and Applications, Ghent, Belgium, 27-30 Aug 2013.

 

   

    General Employee Scheduling Format/Instances/Solver framework

     http://www.dbai.tuwien.ac.at/proj/arte/ges_format/

 

 

Database and Artificial Intelligence Group, Vienna University of Technology, mailto: musliu@dbai.tuwien.ac.at