Optimization Methods for Real Life Scheduling Problems

Rune Larsen, Jørgen Bang-Jensen (Supervisor)

Research output: Book/ReportPh.D. thesis

2177 Downloads (Pure)


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.
Original languageEnglish
PublisherUniversity of Southern Denmark
Number of pages181
Publication statusPublished - 2012
Externally publishedYes


Dive into the research topics of 'Optimization Methods for Real Life Scheduling Problems'. Together they form a unique fingerprint.

Cite this