Publication Date:
2014-02-27
Description:
In this thesis we describe a practical problem that we encountered in the on--line optimization of a complex Flexible Manufacturing System. In the considered system a stacker crane has to fulfill all transportation tasks (jobs) in a single aisled automatic storage system. The jobs have to be sequenced in such a way, that the time needed for the unloaded moves is minimized. The modelling of this question leads to the so--called on--line Hamiltonian path problem. We computationally compare several on--line heuristics and derive lower bounds on the value obtained by an optimal on--line strategy by analyzing two off--line Combinatorial Optimization problems: the asymmetric Hamiltonian path problem with precedence constraints, also called sequential ordering problem (SOP), and the asymmetric Hamiltonian path problem with time windows (AHPPTW). We study the SOP and AHPPTW from a polyhedral point of view and derive several new classes of valid inequalities. Based on the polyhedral investigations we develop branch&cut algorithms for both problems and can achieve encouraging results on solving problem instances from real--world examples of the practical application.
Keywords:
ddc:000
Language:
English
Type:
doctoralthesis
,
doc-type:doctoralThesis
Format:
application/postscript
Format:
application/pdf
