Fixed interval scheduling problems with endogenous uncertainty

Abstract

V této práci se zaměřujeme na úlohy s pevnými intervaly prací (dále FIS problémy). V první kapitole zadefinujeme FIS problémy a endogenní a exogenní náhodu, následně v další kapitole shrneme výsledky zabývající se FIS problémy a jejich vztahem k robust- nímu obarvování grafů. Na ty navážeme představením nového modelu FIS s údržbou. Jde o specifický případ problému s náhodou ovlivněnou rozhodnutím. Představíme nový typ práce - údržbu, která nám umožňuje pozitivně ovlivnit pravděpodobnostní rozdělení zpoždění prací. Zadeifnujeme nejprve problém, kdy údržbu lze použít pouze na začátku, poté představíme obecný problém, kdy se údržba může vyskytnout kdykoliv i později rozvrhu prací. Ukážeme, že tento přístup vede na optimální řešení, zároveń přidáme ilustrativní příklad a budeme diskutovat některá možná rozšířemí problému. Na závěr uvedem výsledky numerické studie, kdy řešíme představený FIS problém s údržbou pomocí solveru Cplex. Ukážeme, že údržba se projevuje pouze při určtých nastaveních, jako velký nepoměr mezi cenou outsourcingu a údržby nebo v případě prací s velkou pravděpodobností zpoždění. Bohužel se ukáže, že už pro středně velké rozměry úloh je problém výpočetně příliš náročný. 1

This thesis is focused on the fixed interval scheduling (FIS) problems with random delays. Firstly, we introduce the concept of FIS problems and the exogenous and endogenous uncertainty. In the next chapter we will summarize the FIS problems under decision dependent randomness and their relation to the robust coloring. We will extend previous results with proposing a new FIS problem with maintenance. This problem is a specific case of a decision-dependent probabilities as it allows to use a specific type of a job - the maintenance, which positively impacts the probability distributions of job delays. We start with defining a problem, where maintenance must be assigned only before regular jobs and then we propose the general case, when maintenances appears during the whole processing period. We show why this approach leads to an optimal solution and provide a detailed example of a small problem.We also discuss some extensions of our problem. Finally, we conduct a numerical study. We solve the FIS maintenance problem with the Cplex solver for a few different settings of inputs. It seems that the maintenance is useful only for certain settings, such as jobs with high probability of having a delay or the price of outsourcing being much higher than the cost of maintenance. It is also shown that the problem...