TY - BOOK
T1 - Optimization Methods for Real Life Scheduling Problems
AU - Larsen, Rune
A2 - Bang-Jensen, Jørgen
PY - 2012
Y1 - 2012
N2 - In this thesis the challenges that arise when applying optimization methods to real
life scheduling problems are considered. The work is divided into four main parts:
i) Real life problems posed by two companies have been investigated first hand.
The primary focus of this work in the context of the thesis is identifying and handling
the constraints exogenous to the core optimization problem. Each of the problems
can be formulated as a variable size bin packing problem, and contains a "subset
sum" sub problem, that is solved by dynamic programming. Complications include
strict real time requirements and uncertain information resulting in a stochastic
problem. These are handled by regular reoptimizations by heuristics with the "anytime"
property. The optimization methods proposed have been adopted, and are
currently being employed in a production environment in both companies.
ii) The subject of the ROADEF/EURO Challenge 2010 is considered. The problem
is based on the French electricity production which is primarily done by nuclear
power plants. The problem is stochastic due to uncertainty in estimated demand
and varying amounts of electricity from other sources such as hydro power plants.
This inherent stochasticity is represented as scenarios for demands. The goal is to
produce a maintenance schedule and a production plan. The problem contains a
large set of constraints, that makes even finding feasible solutions challenging. The
proposed solution consists of a multi phased approach, applying constraint programming
to obtain an initial solution, which is subsequently improved by local search
heuristics applied to a surrogate problem. Finally the solution to the surrogate
problem is generalised to a solution to the actual problem. After correcting a programming
error, the obtained results of the solution method comes out ahead of all
competitors.
iii) A highly modular framework for dynamic rescheduling for problems with
solutions representable as temporal networks is proposed. The framework provides a
method for using a deterministic solver to generate an initial solution to a stochastic
instance, implementing and executing strategies for rescheduling based on Monte
Carlo sampling, and visualise stochastic solutions. The framework is demonstrated
on stochastic versions of two different scheduling problems from the literature: The
job shop instance FT10 and a "single machine weighted completion time" problem.
For each problem, different rescheduling policies are tested and evaluated. The
most significant predictor of solution quality of the problems under consideration, is
shown to be the policies for generating the deterministic instances for rescheduling.
iv) The framework from part iii) is used to generate initial solutions to a train
scheduling problem from the Utrecht area in the Dutch railway system. Three algorithms
from the literature are considered and the sensitivity of solutions produced by
these algorithms to delays (of trains) is analysed. Delays are taken from a uniform
distribution for travel times and Weibull distributions for dwell times. The policy
for generating deterministic instances to solve, is shown to be a better predictor for
quality of the stochastic solution, than any other parameter including the type of
solver used. Finally a set of directions for future work with the framework is proposed, including
two planned papers on applications of the developed framework: Applying
a closed loop rescheduling strategy to the train scheduling problem, and applying
the framework on a real life anodizing plant problem.
AB - In this thesis the challenges that arise when applying optimization methods to real
life scheduling problems are considered. The work is divided into four main parts:
i) Real life problems posed by two companies have been investigated first hand.
The primary focus of this work in the context of the thesis is identifying and handling
the constraints exogenous to the core optimization problem. Each of the problems
can be formulated as a variable size bin packing problem, and contains a "subset
sum" sub problem, that is solved by dynamic programming. Complications include
strict real time requirements and uncertain information resulting in a stochastic
problem. These are handled by regular reoptimizations by heuristics with the "anytime"
property. The optimization methods proposed have been adopted, and are
currently being employed in a production environment in both companies.
ii) The subject of the ROADEF/EURO Challenge 2010 is considered. The problem
is based on the French electricity production which is primarily done by nuclear
power plants. The problem is stochastic due to uncertainty in estimated demand
and varying amounts of electricity from other sources such as hydro power plants.
This inherent stochasticity is represented as scenarios for demands. The goal is to
produce a maintenance schedule and a production plan. The problem contains a
large set of constraints, that makes even finding feasible solutions challenging. The
proposed solution consists of a multi phased approach, applying constraint programming
to obtain an initial solution, which is subsequently improved by local search
heuristics applied to a surrogate problem. Finally the solution to the surrogate
problem is generalised to a solution to the actual problem. After correcting a programming
error, the obtained results of the solution method comes out ahead of all
competitors.
iii) A highly modular framework for dynamic rescheduling for problems with
solutions representable as temporal networks is proposed. The framework provides a
method for using a deterministic solver to generate an initial solution to a stochastic
instance, implementing and executing strategies for rescheduling based on Monte
Carlo sampling, and visualise stochastic solutions. The framework is demonstrated
on stochastic versions of two different scheduling problems from the literature: The
job shop instance FT10 and a "single machine weighted completion time" problem.
For each problem, different rescheduling policies are tested and evaluated. The
most significant predictor of solution quality of the problems under consideration, is
shown to be the policies for generating the deterministic instances for rescheduling.
iv) The framework from part iii) is used to generate initial solutions to a train
scheduling problem from the Utrecht area in the Dutch railway system. Three algorithms
from the literature are considered and the sensitivity of solutions produced by
these algorithms to delays (of trains) is analysed. Delays are taken from a uniform
distribution for travel times and Weibull distributions for dwell times. The policy
for generating deterministic instances to solve, is shown to be a better predictor for
quality of the stochastic solution, than any other parameter including the type of
solver used. Finally a set of directions for future work with the framework is proposed, including
two planned papers on applications of the developed framework: Applying
a closed loop rescheduling strategy to the train scheduling problem, and applying
the framework on a real life anodizing plant problem.
M3 - Ph.D. thesis
BT - Optimization Methods for Real Life Scheduling Problems
PB - University of Southern Denmark
ER -