Heuristics for days-off scheduling of heterogeneous workforce

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2022-01-25
Department
Major/Subject
Systems and Operations Research
Mcode
SCI3055
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
6+38
Series
Abstract
Flexible working life and competition between companies characterize modern working environments. To address this, employers use automatic workforce scheduling to reduce manual planning work and optimize schedules on some aspects, such as costs or employee satisfaction. In this thesis, the problem of allocating rest and workdays of employees is modelled as a mixed-integer nonlinear optimization problem that features a workload forecast consisting of multiple task types, varying employee skills on different task types, and employee-specific contracts. The goal of the thesis is to find a performant method for producing high-quality solutions for the model. The studied method is solving a relaxed problem instance and constructing an integer solution from the real number solution with two heuristics. Solution times, solution quality, and feasibility of the solution obtained were analyzed using a data set of 60 realistic scenarios. The heuristics provided high-quality solutions in terms of feasibility and objective function values. Regarding solution times, obtaining the real number solution was recognized as a performance bottleneck.

Nykyaikaisille työympäristöille on ominaista joustavuus ja yritysten välinen kilpailu. Työnantajat käyttävät automaattista aikatauluttamista vähentääkseen manuaalista suunnittelutyötä ja optimoidakseen aikatauluja mm. kustannusten ja työntekijätyytyväisyyden osalta. Tässä diplomityössä työntekijöiden lepo- ja työpäivien allokoimisongelmaa mallinnetaan epälineaarisena kokonaislukuoptimointiongelmana, jossa työntekijöiden taidot vaihtelevat eri tehtävissä ja työntekijöillä on yksilölliset työsopimukset. Tutkielman tavoitteena on löytää suorituskykyinen menetelmä laadukkaan ratkaisun tuottamiseksi malliin. Malli ratkaistaan laskemalla ongelmainstanssille reaalilukuratkaisu, jossa kokonaislukurajoitukset jätetään huomiotta. Reaalilukuratkaisusta muodostetaan kokonaislukuratkaisu kahdella heuristiikalla. Algoritmien testaamiseen käytettiin 60 realistista testidatainstanssia. Ratkaisuajat, ratkaisun laatu ja saadun ratkaisun rajoitustenmukaisuus analysoitiin. Heuristiikat tuottivat rajoitusten noudattamisen ja tavoitefunktion arvojen kannalta laadukkaita ratkaisuja. Ratkaisuaikojen osalta reaalilukuratkaisun saaminen todettiin suorituskyvyn pullonkaulaksi.
Description
Supervisor
Oliveira, Fabricio
Thesis advisor
Pulliainen, Laur
Saikko, Paul
Keywords
workforce optimization, days-off scheduling, heuristic, heterogeneous workforce
Other note
Citation