Heuristics for days-off scheduling of heterogeneous workforce

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.