|
|
Fixed interval scheduling problems with endogenous uncertainty
Hamerníková, Iva ; Branda, Martin (advisor) ; Lachout, Petr (referee)
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...
|
|
|
Minimax in scheduling problems under uncertainty
Jeliga, Jan ; Branda, Martin (advisor) ; Lachout, Petr (referee)
In this work, we deal with fixed interval scheduling problems with the possibility of random delay of the end of the tasks (FIS). First, we pre- sent the basic deterministic FIS problems and ways to solve them. Next, we introduce the concept of minimax and present two well-known and one new FIS problem under uncertainty, when random task delays are conside- red to belong to a certain uncertainty set. Next, we deal with the solution of previously presented FIS problems for five chosen uncertainty sets. We present both previously achieved and original results. The work concludes with a summary of a numerical study of two problems. First, we explore the possibility of Lagrange relaxation application to the first presented problem. Next we explore the quality of approximation allowing to solve the later of problems as LP. 1
|
|
|
Vertex coloring algorithms in scheduling problems under uncertainty
Hájek, Štěpán ; Branda, Martin (advisor) ; Lavička, Karel (referee)
This thesis concerns solutions to problems that arise in optimizing fixed interval scheduling under situations of uncertainty such as when there are random delays in job process times. These problems can be solved by using a vertex coloring with random edges and problems can be formulated using integer linear, quadratic and stochastic programming. In this thesis is propo- sed a new integer linear formulation. Under certain conditions there is proved its equivalence with stochastic formulation, where is maximized the schedule reliability. Moreover, we modified the proposed formulation to obtain bet- ter corresponding to real life situations. In a numerical study we compared computational time of individual formulations. It turns out that the propo- sed formulation is able to solve scheduling problems considerably faster than other formulations. 1
|
guest ::
