TES-rajoitteet sisältävä työvuorosuunnitteluongelma

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