ISBN 9783843928359

978-3-8439-2835-9, Reihe Mathematik

Jens Leoff
Hierarchical Scheduling and Cutting Stock with Bounded Open Orders

193 Seiten, Dissertation Technische Universität Kaiserslautern (2016), Softcover, A4

Zusammenfassung / Abstract

The thesis consists of two parts.

The first part treats a hierarchical scheduling and planning approach, where time is divided into intervals of increasing size. As time progresses the larger intervals are split into smaller ones, such that the near future is always planned to a sufficient level of detail. An infeasibility problem is encountered when trying to split an interval. This infeasibility problem and different relaxations of the same are analysed in depth. We prove that a multi-level bin packing approach is an approximation algorithm for a simplified offline model. Under weak assumptions, we show that the approximation quality is independent of the depth of the hierarchy defined by the time-intervals. The results are generalized to an online version of the problem.

In the second part of the thesis we consider an integrated cutting stock and sequencing problem. The aim is to cover the demand quantities with a minimal amount cutting patterns and sequencing the same, such that only a certain number of orders are produced simultaneously. We prove an equivalent description of one constraint via a polyhedron. For this polyhedron we derive minimal inner and outer descriptions. A separation procedure to find violated facet defining inequalities is presented. Our results allow to formulate the problem as an IP which we solve exactly with a branch, price and cut procedure.

We compare our model numerically to a generalized model from the Literature and evaluate the impact of using an integrated solution approach compared to a sequential one.