Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-7047
Main Title: Presolving techniques and linear relaxations for cumulative scheduling
Translated Title: Presolving-Techniken und lineare Relaxierungen für kumulatives Scheduling
Author(s): Heinz, Stefan
Advisor(s): Koch, Thorsten
Referee(s): Beck, J. Christopher
Koch, Thorsten
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: In the mathematical optimization community the term scheduling usually describes the computation of a sequential plan for a set of jobs w.r.t. a set of side conditions such as precedence constraints and resource restrictions. Thereby, a certain objective should be fulfilled which can be for example to minimize the latest completion time of all jobs. The sequential plan can be an ordering of the jobs or in case of this dissertation a schedule which assigns a start time to each job. Many scheduling problems can be modeled and solved as a constraint program as well as a mixed-integer (linear) program. Both approaches have their advantages and disadvantages which are often complementary. In this dissertation we use a hybrid approach, called constraint integer programming, to solve scheduling problems. We focus on scheduling problems which contain a cumulative resource structure: the available resources are renewable and can be shared between jobs which have to be scheduled non-preemptively. We define the class of energy-based propagation algorithms which are inference algorithms for the cumulative resource structure using volume arguments to infer bounds on the start time and the completion time of a job. Many of the known propagation algorithms for the cumulative resource structure, such as time-tabling, edge-finding, time-tabling edge-finding, and energetic reasoning, belong to this class. For this class we develop explanations for their inferred bound changes. These explanations are used during the analyzes of infeasible sub-problem to retrieve additional (redundant) constraints which help to solve a particular problem more quickly. This concept generalizes known explanations for propagation algorithms for the cumulative resource structure. In addition we show that each energy-based propagation algorithm implies a linear relaxation for the cumulative resource structure with optional jobs. For current state-of-the-art mixed-integer programming solvers presolving is an important feature. During presolving, the original problem is reformulated into a hopefully easier-to-solve problem. One aim is to remove redundant variables and constraints. For the cumulative resource structure we present several presolving techniques generalizing the concept of dual reductions, which is known for mixed-integer programs to shrink a problem formulation, to constraint programs. This techniques allows us to remove feasible or even optimal solutions from the solution space as long as one optimal solution remains in case that the problem is feasible. Using this idea we develop several dual reduction steps for the cumulative resource structure. These reductions enable the removal of jobs from a cumulative resource with the knowledge that this job can be scheduled independently of the schedule for the remaining jobs. In a computational study, we analyze the impact of the presolving techniques for the cumulative constraint and the linear relaxations for the cumulative constraint with optional jobs. Therefore, we use two problem classes which are resource-constrained project scheduling problems and resource allocation and scheduling problem.
In der mathematischen Optimierung bezeichnet der Begriff Scheduling die Berechnung eines Ablaufplans, die eine gegebenen Menge von Prozessen (Jobs), typischerweise mit Reihenfolgebeziehungen, einer Menge von beschränkten Ressourcen (z.B. Maschinen) zuordnet, meist mit dem Ziel die späteste Fertigstellungszeit aller Jobs zu minimieren. Scheduling-Probleme lassen sich sowohl als Gemischt-Ganzzahlige (Lineare) Programme als auch als Constraint-Programme modellieren und lösen. Beide Ansätze haben ihre Stärken und Schwächen, diese sind aber in vielerlei Hinsicht komplementär. In der vorliegenden Arbeit verwenden wir einen integrierten Ansatz, die sogenannte Constraint-Ganzzahlige Programmierung, um Scheduling-Probleme zu lösen. Wir konzentrieren uns auf Scheduling-Probleme mit Kumulativ-Bedingungen, d.h. es gibt Ressourcen, welche sich mehrere nicht-unterbrechbare Jobs teilen. Wir definieren die Klasse von energiebasierten Propagierungsalgorithmen für Kumulativ-Bedingungen, welche Volumenargumente nutzen, um die Startzeit und Endzeit eines Jobs zu beschränken. Viele aus der Literatur bekannte Propagierungsalgorithmen, wie time-tabling, edge-finding, time-tabling edge-finding und energetic reasoning, gehören zu dieser Klasse. Für die Klasse der energiebasierten Propagierungsalgorithmen entwickeln wir allgemeine Erklärungen für die propagierten Schranken. Diese Erklärungen werden in der Analyse von unzulässigen Teilproblemen genutzt, um zusätzliche gültige Bedingungen zu lernen. Dabei generalisieren wir aus der Literatur bekannte Erklärungen für Propagierungsalgorithmen für Kumulativ-Bedingungen. Zusätzlich zeigen wir, dass jeder energiebasierte Propagierungsalgorithmus eine lineare Relaxierung für Kumulativ-Bedingung mit optionalen Jobs impliziert. Diese Relaxierung kann genutzt werden, um die lineare Relaxierung eines Constraint-Ganzzahligen Programms zu verstärken. Presolving-Verfahren sind ein wichtiger algorithmischer Bestandteil zum Lösen Gemischt-Ganzzahlige Programme. Presolving-Verfahren reformulieren das Original-Problem in ein (hoffentlich) leichter zu lösendes Problem. Oftmals werden dabei redundante Variablen und Bedingungen eliminiert. Wir entwickeln diverse Presolving-Verfahren für Kumulativ-Bedingungen vor. Unter anderem verallgemeinern wir das Konzept der dualen Reduktion, welches in der Gemischt-Ganzzahligen Programmierung für Problemvereinfachungen genutzt wird, auf die Constraint-Programmierung. Solch eine Reduktion kann genutzt werden, um zulässige oder sogar optimale Lösungen aus dem Lösungsraum zu entfernen, solange sicher gestellt wird, dass nicht alle Optimallösung entfernt werden. Wenn es beispielsweise eine Bearbeitungszeit für einen Job gibt, aus der sich keinerlei Einschränkungen für andere Jobs ergeben, kann dieser dort platziert werden und aus der entsprechenden Kumulativ-Bedingung entfernt werden. In einem umfangreichen Rechenexperiment zeigen wir, dass der im Rahmen dieser Arbeit entwickelte Scheduling-Löser kompetitiv zu den besten aus der Literatur bekannten Scheduling-Lösern ist. Dabei ist zu bemerken, dass die entwickelten Techniken allgemein gültig sind für die Constraint-Ganzzahlige Programmierung. Das heißt, diese Techniken können allgemein zum Lösen aller Gemischt-Ganzzahligen Programme, die Kumulativ- Bedingungen enthalten, genutzt werden und sind nicht problemspezifisch.
URI: https://depositonce.tu-berlin.de//handle/11303/7887
http://dx.doi.org/10.14279/depositonce-7047
Exam Date: 7-May-2018
Issue Date: 2018
Date Available: 30-May-2018
DDC Class: 510 Mathematik
Subject(s): cumulative scheduling
dual reductions
mixed-integer programming
logic-based Benders decomposition
energy-based propagation algorithms
kumulative Ablaufplanung
duale Reduktionen
logikbasierte Benders-Dekomposition
gemischt-ganzzahlige Optimierung
energiebasierte Propagierungsalgorithmen
License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
File Description SizeFormat 
heinz_stefan.pdf1.87 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons