Optimizing Real-Life Personnel Scheduling Problems through Shift Design and a Parallel Adaptive Large Neighborhood Search

Abstract

Tjenesteytende industrier står overfor den utfordrende oppgaven med å effektivt tilfredsstille en varierende etterspørsel med riktig tilførsel av kvalifisert personell. Å allokere personell til arbeidsskift, slik at et ønskelig tjenestenivå opprettholdes, er en viktig og krevende oppgave for mange selskaper og organisasjoner. Fordelingen av arbeidsskift mellom de ansatte er det vi heretter referer til som arbeidstimelister. I tillegg har nyere studier avdekket viktigheten av ansattes tilfredsshet og opplevd rettferdighet, da disse aspektene kan bidra til å øke arbeidsytelsen. Å ihensynta slike aspekter øker kompleksiteten ved lage tilfredstillende arbeidstimelister ytterligere.

Medvind, en leverandør av systemer for arbeidsledelse, utvikler et planleggingsverktøy som skal kunne generere optimaliserte arbeidstimelister. De har et bredt spekter av ulike kunder, noe som krever at verktøyet for generering av arbeidstimelister er tilstrekkelig generelt, slik at den kan anvendes i de mange industriene som er representert i Medvinds kundebase. I denne masteroppgaven adresserer vi problemet Medvind står overfor, heretter definert som MSP. Vår målsetning er å utvikle en løsningsmetode som genererer arbeidstimelister av høy kvalitet, noe som innebærer at arbeidstimelistene dekker etterspørsel og at rettferdighet maksimeres blant de ansatte.

For å oppnå arbeidstimelister av høy kvalitet, adresserer denne oppgaven to viktige sider ved personalplanlegging; skiftdesign-problemet og allokeringsproblemet. Skiftdesign-problemet omhandler utfordringene med å designe hensiktsmessige arbeidsskift som de ansatte kan tildeles, mens allokeringsproblemet omhandler utfordringene med å allokere de ansatte til de genererte skiftene. I denne masteroppgaven foreslår vi en heuristisk metode for å designe skift (Shift Design Heuristic - SDH), hvor skiftene er tilpasset etterspørselen og samtidig sørger for å fasiliterere fleksibilitet for å bedre imøtekomme rettferdighetsaspektene som betraktes i MSP. For allokeringsproblemet foreslår vi to løsningsmetoder; en blandet heltallsløser (Mixed Integer Programming model - MIP-modell) og et parallelt adaptivt stort nabolagssøk (Parallel Adaptive Large Neighbourhood Search - PALNS). MIP-modellen er en eksakt løser som skal sørge for å generere optimale arbeidslisteplaner. En utfordring med eksakte løsere er imidlertid at ytelsen ofte reduseres vesentlig når kompleksiteten ved allokeringsproblemene øker. Derfor foreslås PALNSen, som har til hensikt å generere løsninger raskere og skalere bedre ved økende komplekistet.

Den foreslåtte SDHen testes på ni reelle probleminstanser gitt av Medvind. Resultatene fre disse testene viser at SDHen genererer skift som klart utkonkurrerer manuelt genererte skift når det kommer til ytelse og effektivitet. Skiftene som genereres av SDHen sammenlignes også med ideelle skift generert av en implisitt arbeidstimelistemodell utviklet i forarbeidet til denne masteroppgaven. Denne implisitte modellen tar ikke i bruk utviklede skift, men allokerer ansatte til starttidspunkter med tilhørende varigheter. Dette innebærer tilnærmet ubegrenset fleksibilitet, noe som legger til rette for ideelle skift. Den betydelige fleksibiliteten medfører imidlertid høy kompleksitet, noe som gjør det krevende for modellen å lage arbeidstimelister. Sammenligningen mellom SDHen og de implisitte skiftene gjøres derfor på forenklede probleminstanser. Selv om de implisitte skiftene muliggjør de beste arbeidstimelistene, er SDHen i stand til å designe skift som ligner de implisitte, og SDHen overgår i tillegg klart den implisitte modellen når det kommer til praktisk anvendbarhet.

Sammenligningen av MIP-modellen og PALNSen viser at MIP-modellen yter bedre på probleminstanser som kan betraktes som mindre komplekse. Når størrelsen og kompleksiteten på problemene øker, reduseres MIP-modellens ytelse. Dette gjør seg gjeldende ved at MIP-modellen ikke evner å generere en mulig løsning for tre av de ni probleminstansene gitt av Medvind, innen tidsbegrensningen på fem timer. PALNSen er derimot i stand til å oppnå tilfredsstillende løsninger for alle de reelle problemene, selv innenfor 15 minutter. Selv om den oppnådde objektivverdien er lavere for PALNSen, sammenlignet med MIP-modellen, er denne forskjellen i praksis neglisjerbar. PALNSen evner også å generere løsninger vesentlig kjappere enn MIP-modellen for mer komplekse problemer, og skalerer i tillegg godt når antall ansatte eller planleggingshorisonten økes for de reelle problemene. Dette gjelder ikke for MIP-modellen. Evnen til å effektivt generere arbeidslisteplaner av høy kvalitet for probleminstanser av varierende kompleksitet, indikerer at PALNSen er den foretrukne løsningsmetoden for MSP.

Kombinasjonen av de utviklede heuristikkene, SDH og PALNS, evner i stor grad å generere arbeidstimelister av høy kvalitet innenfor ønsket tidsbegrensning. Disse arbeidstimelistene tilfredsstiller etterspørselen og legger til rette for en høy grad av rettferdighet. PALNSen er i stand til å generere arbeidstimelister for alle de varierte og reelle problemene gitt av Medvind, som understreker PALNSens evne til å håndtere generelle planleggingsproblemer. I tillegg er den utviklede SDHen i stand til å generere gunstige skift skreddersydd for hvert problem på en veldig effektiv måte. Dette bidraget antas å ha en betydelig praktisk verdi.

Service industries are faced with the challenging task of efficiently satisfying a varying demand with the right supply of qualified personnel. To schedule personnel in order to sustain a desirable service level is, therefore, an important concern. Additionally, recent studies have revealed the importance of employee satisfaction and perceived fairness of schedules, as this tends to increased work performance. This aspect increases the complexity of creating high-quality work schedules.

Medvind, a provider of workforce management systems, are currently developing a scheduling tool that aims to generate optimized work schedules. They have a broad base of customers, which require the scheduling model to be general in order for it to apply to the variety of service industries represented. In this master's thesis, we address the problem faced by Medvind, defined as the Medvind Scheduling Problem (MSP). Our purpose is to generate high-quality schedules, which implies that demand is covered and that the fairness of the employees is maximized.

In order to achieve high-quality schedules, this thesis address two important aspects of personnel scheduling. First, we address the shift design problem, concerned with the generation of favourable shifts for the rostering problem. Secondly, we address the rostering problem, concerned with allocating staff to the generated shifts in an optimal way. In this thesis, we propose a Shift Design Heuristic (SDH), aiming to create shifts tailored to the faced demand, while allowing flexibility to satisfy the fairness aspects considered in the MSP. For the rostering problem, a Mixed Integer Programming (MIP) model has been proposed with the ability to find the optimal schedules. As the performance of exact solvers tends to diminish significantly with higher complexity, a Parallel Adaptive Large Neighborhood Search (PALNS) is also implemented in order to better cope with rostering problems of increased complexity.

When evaluating the SDH on nine real-life problems provided by Medvind, the SDH generates shifts that clearly outperform manually created shifts in terms of performance and efficiency. The generated shifts are also compared to ideal shifts generated by an implicit scheduling model that was developed in the preliminary work of this thesis. This implicit scheduling model generates shifts implicitly, allowing for more or less unlimited flexibility but at the expense of increased complexity in obtaining scheduling solution. The comparison is thus performed on simplified test problems. Even though the implicitly generated shifts facilities the best schedules, the SDH is able to design shifts similar to the implicit shifts and significantly outperform the implicit model when it comes to practical applicability.

Comparing the MIP model to the PALNS shows an advantage for the MIP model on the less complex problem instances. However, as the size and complexity increases, the performance of the MIP model decreases, resulting in no feasible solution for three of the nine provided test instances even with a time limit of five hours. The PALNS, on the other hand, is able to achieve satisfactory solutions for all real-life problems provided by Medvind. Although the obtained objective values are lower for the PALNS compared to the MIP model, these differences are not significant in real-life applications. Furthermore, the PALNS is considerably faster to obtain solutions for more complex problems. Additionally, the PALNS seems to scale well with both the number of employees and the length of the planning horizon. This does not apply to the MIP model. The ability to efficiently create high-quality schedules for problem instances of varying complexity indicates that the PALNS is the preferred solution approach for the MSP.

The combination of the SDH and the PALNS presented in this thesis greatly succeed in generating high-quality schedules within the desired time limit, that both satisfy demand and facilitate a high degree of fairness. The PALNS is able to obtain good schedules for all real problems provided by Medvind, underlining the ability of the PALNS to handle general scheduling problems. Additionally, the developed SDH is able to generate favourable shifts tailored to each problem in a very efficient manner. This contribution is assumed to have a significant practical value.