Dorndorf Project Scheduling with Time Windows

From Theory to Applications
2002
ISBN: 978-3-642-57506-8
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 166 Seiten, eBook

Reihe: Contributions to Management Science

Project Scheduling is concerned with the allocation of scarce resources over time. The rich optimisation models with time windows that are treated in this book cover a multitude of practical decision problems arising in diverse application areas such as construction engineering or make-to-order production planning.
The book shows how Constraint Propagation techniques from Artificial Intelligence can be successfully combined with Operations Research methods for developing powerful exact and heuristic solution algorithms for a very general class of scheduling problems. Example applications demonstrate the effectiveness of the approach.

Zielgruppe

Research

Autoren/Hrsg.

Dorndorf, Ulrich

Inhaltsverzeichnis

1 Introduction.- 1.1 Motivation and Objectives.- 1.2 Outline.- 2. Optimisation Model.- 2.1 The General Single-Mode Model.- 2.1.1 Activities and Resources.- 2.1.2 Temporal Constraints.- 2.1.3 The Model.- 2.1.4 Schedules and Performance Measures.- 2.1.5 Domains of Decision Variables.- 2.1.6 Special Cases.- 2.2 Extension to Multiple Execution Modes.- 2.2.1 Modes.- 2.2.2 Resources.- 2.2.3 The Model.- 3 Constraint Propagation.- 3.1 Constraint Satisfaction and Optimisation.- 3.1.1 The Constraint Satisfaction Problem.- 3.1.2 The Constraint Optimisation Problem.- 3.1.3 Constraint Graphs.- 3.2 Concepts of Consistency.- 3.2.1 k-Consistency.- 3.2.2 Domain-Consistency.- 3.2.3 Bound Consistency.- 3.3 Consistency Checking.- 3.3.1 Consistency Tests.- 3.3.2 Consistency Checking Algorithms.- 3.3.3 Uniqueness of the Fixed Point.- 3.4 Constraint Programming.- 4 Consistency Tests.- 4.1 Basic Concepts.- 4.2 Consistency Tests for Temporal Constraints.- 4.3 Interval Consistency.- 4.4 Disjunctive Sub-Problems.- 4.4.1 Disjunctive Activity Pairs.- 4.4.2 Selection of Disjunctive Sub-Problems.- 4.5 Disjunctive Interval Consistency Tests.- 4.5.1 Input/Output Test.- 4.5.2 Input-or-Output Test.- 4.5.3 Input/Output Negation Test.- 4.5.4 Summary and Generalisation.- 4.5.5 Relation to Interval Consistency.- 4.5.6 Lower Level Consistency.- 4.5.7 Sequence Consistency Does Not Imply k-b-Consistency.- 4.5.8 Shaving.- 4.6 Cumulative Interval Consistency Tests.- 4.6.1 Unit-Interval Consistency.- 4.6.2 Activity Interval Consistency.- 4.6.3 Minimum Slack Intervals.- 4.6.4 Fully and Partially Elastic Relaxations.- 4.7 Multi-Mode Consistency Tests.- 4.8 Summary.- 5 A Branch-and-Bound Algorithm.- 5.1 Previous Solution Approaches.- 5.2 Constraint Propagation.- 5.2.1 Consistency Tests.- 5.2.2 Some Properties of the Earliest Start Times.- 5.3 The Branch-and-Bound Algorithm.- 5.3.1 The Branching Scheme.- 5.3.2 Upper and Lower Bounds.- 5.3.3 Some Properties of Active Schedules.- 5.4 Computational Experiments.- 5.4.1 Implementation of the Algorithm.- 5.4.2 Bidirectional Planning.- 5.4.3 Characteristics of the Test Sets.- 5.4.4 Experiments for the Problem PSItemplCmax.- 5.4.5 Experiments for the Problem PS1precIC,,,ax.- 5.5 Summary.- 6 Multi-Mode Extension of the Branch-and-Bound Algorithm.- 6.1 Previous Work.- 6.2 Constraint Propagation.- 6.3 Extended Branching Scheme.- 7 Applications in Airport Operations Management.- 7.1 Scheduling of Ground Handling Operations.- 7.2 Gate Scheduling.- 7.2.1 Introduction.- 7.2.2 Literature Review.- 7.2.3 Problem Description.- 7.2.4 Constraint Propagation.- 7.2.5 A Branch-and-Bound Algorithm.- 7.2.6 Lower Bounds.- 7.2.7 Problem Partitioning.- 7.2.8 Layered Branch-and-Bound.- 7.2.9 Large Neighbourhood Search.- 7.2.10 Computational Experiments.- 8 Summary and Conclusions.- List of Figures.- List of Tables.- List of Symbols.- References.