Workforce scheduling problem with collective labour agreement constraints
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Master's thesis
Ask about the availability of the thesis by sending email to the Aalto University Learning Centre oppimiskeskus@aalto.fi
Authors
Date
2017-08-28
Department
Major/Subject
Analytics and Data Science
Mcode
SCI3073
Degree programme
AEE - Master’s Programme in Automation and Electrical Engineering (TS2013)
Language
en
Pages
71+8
Series
Abstract
The purpose of this thesis is to investigate and analyze the present status of solution methods for workforce scheduling problems. Furthermore, the thesis addresses two workforce scheduling problems that appear in organizations operating in Finland and proposes approaches to solving those problems. In the first part, the most interesting results of most up-to-date articles regarding workforce scheduling are presented. These results show that workforce scheduling is extensively studied, but at the moment, no general purpose solution method have been developed. The thesis then introduces and describes mathematical formulations for the two problems in consideration. The thesis provides computational experiments which show that these initial formulations are not sufficiently efficient and not solvable in a reasonable amount of time with a state-of-the-art integer programming solver. In the second part, the thesis concentrates on producing tight lower -and upper-bounds on the optimal cost. Lower bounds are obtained with a column generation approach and the upper bounds with a hybrid heuristic. The computational experiments reveal that the methods developed in this thesis outperform the initial formulation in most cases. This thesis was done for Zenopt Ltd as a part of research and development project.Tässä diplomityössä tarkastellaan ja analysoidaan eri työvuorosuunnitteluongelmien ratkaisumenetelmien nykytilannetta. Tämän ohella, työssä tuodaan esille kaksi Suomessa ilmenevää työvuorosuunnitteluongelmaa sekä tapoja, joilla kyseiset ongelmat voidaan ratkaista. Työn ensimmäisessä osassa käydään läpi ajan tasalla olevien sekä työvuoronsuunnittelua tarkastelevien artikkelien kiinnostavimmat tulokset. Nämä tulokset osoittavat, että työvuorosuunnittelu on kattavasti tutkittu aihealue, mutta tällä hetkellä täysin yleiskäyttöistä ratkaisumenetelmää ei ole kehitetty. Seuraavaksi työssä esitellään ja kuvataan ongelmille matemaattinen formulaatio. Laskennalliset testit osoittavat, että kyseiset formulaatiot eivät ole riittävän tehokkaita ja huippuluokan optimointiohjelmistolla ongelmien ratkaisuaika ylittää kohtuulliset rajat. Seuraavaksi työssä keskitytään löytämään ongelmille kapeat ylä- ja alarajat. Alarajat löydetään sarakkeita generoivan algoritmin avulla ja ylärajat hybridi heuristiikalla. Työn tämän osan laskennalliset tulokset vahvistavat, että uudet menetelmät tuottavat parempia tuloksia suurimmalle osalle instansseista alkuperäiseen formulaatioon verrattuna. Tämä työ on tehty Zenopt Oy:lle osana tutkimus- ja tuotekehitysprojektia.Description
Supervisor
Gionis, AristidesThesis advisor
Alakiikonen, AnttiKeywords
workforce scheduling, integer programming, column generation algorithm, dynamic programming