Convex optimization for shift scheduling in retail
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2022-12-12
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
51+13
Series
Abstract
Retail is a turbulent sector characterized by long opening hours, a multitude of products and services, varying employee availabilities and various contractual constraints. In retail workforce optimization we want to match the available workload to employees while minimizing task switches. In our problem formulation we have tasks that are interruptible and have different priorities and skill requirements. The scope of this thesis is the subproblem of evaluating the value of a set of daily shifts by assigning tasks to them. We show that this task assignment subproblem is NP-hard as it contains the interval scheduling problem with non-identical machines as a special case, which 3-SAT can be reduced to. We have a pre-defined utility function for scoring the solutions and an existing baseline solution which we compare our results against. We also have 33 real problem instances and 100 artificially generated ones to run benchmarks on. We formulate and solve an integer program which optimizes the nonconvex quadratic utility function directly using the commercial solver GUROBI. This revealed that the baseline could be improved for the real world, problem instances up to 4.2% (mean 0.7%) and for artificial instances up to 785.5% (mean 19.7%), with average runtimes being 451s and 5493s respectively. Next, we formulated a convex quadratic program which approximated the utility function. By optimizing this convex objective, the results were still up to 4.2% (mean 0.6%) better than baseline on real instances and up to 401% (mean 7.1%) better on artificial instances. For this convex objective the average runtimes were 9.3s and 385s respectively. To reduce runtime variance, we removed the integer constraints and solved the model with the open source OSQP solver to get fractional solutions. For these fractional solutions we implemented an iterative rounding scheme, which improved the real instances up to 4.2% (mean 0.3%) and artificial instances up to 376% (mean 1%), with an average runtime of 2.4s and 16.3s respectively. The convex relaxation could also be directly used as the utility function, as it also rewards consecutive task assignments. This would likely make the approach in this thesis perform even better.Detaljhandel karaktäriseras av långa och varierande öppettider, flexibla arbetstider, flera produkter och olika tjänster. Då vi optimerar bemanningen i detaljhandeln vill vi para ihop tillgängligt arbete med personal och undvika överflödiga byten mellan arbetsuppgifter. I vårt problem är det möjligt att avbryta arbetsuppgifter och dessa uppgifter har olika prioritet och kompetenskrav. Detta arbete begränsar omfattningen till delproblemet, där vi vill värdera en samling av givna arbetspass genom att ange dem arbetsuppgifter. Vi visar att detta delproblem är NP-svårt, eftersom det innefattar ”intervall optimerings problemet” (interval scheduling problem) med icke-identiska maskiner som ett specialfall, vilket 3-SAT kan reduceras till. Vi har en given nyttofunktion för att värdera lösningarna och det finns en bas lösning vilken vi jämför med våra resultat. Vi har 33 riktiga problemfall och 100 artificiellt genererade som vi använder till jämförelsen. Vi formulerar och löser ett heltalsprogram som optimerar den icke-konvexa kvadratiska nyttofunktionen direkt med hjälp av den kommersiella lösaren GUROBI. Detta visade att baslösningen kan förbättras i de riktiga fallen med upp till 4,2% (medeltal 0,7%) och i de artificiella fallen upp till 785,5% (medeltal 19,7%), med körtiderna i medeltal 451s respektive 5493s. Sedan formulerade vi en konvex approximering för modellen. Optimering av denna modell ledde till resultat som var fortfarande upp till 4,2% bättre (medeltal 0,6%) för de riktiga fallen och 401% bättre (medeltal 7,1%) för de artificiella fallen. För denna modell tog optimeringen i medeltal 9,3s respektive 385s. För att minska variansen i körtiderna tog vi bort heltalsrestriktionen och löste modellen med OSQP lösaren. För dessa bråktalslösningar gjorde vi olika iterativa avrundningsmetoder, varav den bästa förbättrade de riktiga fallen upp till 4,2% (medeltal 0,3%) och de artificiella fallen upp till 376% (medeltal 1%), med körtiderna 2,4s respektive 16,3s. Denna konvexa omformulering kunde möjligtvis användas direkt som nyttofunktion, eftersom den också belönar på varandra följande arbetsuppgifter. I detta fall skulle metoden i detta arbete troligtvis prestera även bättre.Description
Supervisor
Suomela, JukkaThesis advisor
Saikko, PaulNorjama, Laur
Keywords
convex optimization, employee scheduling, multi-activity assignment problem, mixed integer programming, combinatorial optimization