TU Berlin

FG Software und Algorithmen für die diskrete OptimierungPh.D. theses

Page Content

to Navigation

Ph.D. theses

Presolving techniques and linear relaxations for cumulative scheduling
Citation key Heinz2018
Author Stefan Heinz
Year 2018
DOI 10.14279/depositonce-7047
Month May
Note Dissertationspreis 2019 der Gesellschaft für Operations Research
School TU Berlin
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.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe