Optimal scheduling with nested time intervals and three-dimensional strip packing on comparability graphs of an arborescence order / Thomas Rieger.

Format:

Book

Author/Creator:

Rieger, Thomas, author.

Language:

English

Subjects (All):

Operations research--Periodicals.

Operations research.

Physical Description:

1 online resource (158 pages) : illustrations (some color), tables, graphs

Edition:

1st ed.

Place of Publication:

Göttingen, [Germany] : Cuvillier Verlag, 2015.

Summary:

This thesis is concerned with scheduling and three-dimensional packing problems that arise when restricting to nested intervals - either for allocating jobs to time intervals (at machines) or for positioning boxes within a strip. The scheduling problems considered in the first part of this work are motivated by a real-world application in rail car maintenance, and result in a new type of job characteristic introduced into the methodology of scheduling. Being classified as strip packing problems on comparability graphs of an arborescence order, the packing problems of the second part of this thesis are further structurally characterized based on the concept of packing classes. It turns out that using this characterization, these packing problems can equivalently be solved by interval coloring adequate chordal graphs. For several variants of above-mentioned mathematical optimization problems complexity results are derived and approximation, pure heuristical as well as exact solution approaches presented. The performance of the approaches is finally discussed based on computational results.

Contents:

Intro

Contents

1 Introduction

2 Preliminaries

3 Scheduling with Nested Time Intervals

4 Three-Dimensional Strip Packing on Comparability Graphs of an Arborescence Order

5 Conclusions

Bibliography

List of Symbols

List of Tables

List of Figures

List of Algorithms

Zusammenfassung.

Notes:

Includes bibliographical references.

Description based on online resource; title from PDF title page (ebrary, viewed September 27, 2017).

ISBN:

9783736980358

3736980353