ARTE:
Artificial Intelligence in Employee Scheduling This
project is supported by the Austrian Science Fund
(project: P24814-N23) |
|
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 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
|