Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2001 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Constraint-Based Scheduling

Applying Constraint Programming to Scheduling Problems

verfasst von: Philippe Baptiste, Claude Le Pape, Wim Nuijten

Verlag: Springer US

Buchreihe : International Series in Operations Research & Management Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Constraint Programming is a problem-solving paradigm that establishes a clear distinction between two pivotal aspects of a problem: (1) a precise definition of the constraints that define the problem to be solved and (2) the algorithms and heuristics enabling the selection of decisions to solve the problem.
It is because of these capabilities that Constraint Programming is increasingly being employed as a problem-solving tool to solve scheduling problems. Hence the development of Constraint-Based Scheduling as a field of study.
The aim of this book is to provide an overview of the most widely used Constraint-Based Scheduling techniques. Following the principles of Constraint Programming, the book consists of three distinct parts: The first chapter introduces the basic principles of Constraint Programming and provides a model of the constraints that are the most often encountered in scheduling problems. Chapters 2, 3, 4, and 5 are focused on the propagation of resource constraints, which usually are responsible for the "hardness" of the scheduling problem. Chapters 6, 7, and 8 are dedicated to the resolution of several scheduling problems. These examples illustrate the use and the practical efficiency of the constraint propagation methods of the previous chapters. They also show that besides constraint propagation, the exploration of the search space must be carefully designed, taking into account specific properties of the considered problem (e.g., dominance relations, symmetries, possible use of decomposition rules). Chapter 9 mentions various extensions of the model and presents promising research directions.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
Constraint-Based Scheduling can be defined as the discipline that studies how to solve scheduling problems by using Constraint Programming (CP). In this introduction we first pay attention to the basics of CP, after which we introduce the scheduling problems that are considered in this book.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 2. Propagation of the One-Machine Resource Constraint
Abstract
In this chapter we study several methods to propagate a One-Machine resource constraint: A set of n activities A1,…, A n require the same resource of capacity 1. The propagation of resource constraints is a purely deductive process that allows to deduce inconsistencies and to tighten the temporal characteristics of activities and resources. In the non-preemptive case (Section 2.1), the earliest start times and the latest end times of activities are updated. When preemption is allowed (Section 2.2), modifications of earliest end times and latest start times also apply.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 3. Propagation of Cumulative Constraints
Abstract
Cumulative resource constraints represent the fact that activities A i use some amount cap(A i ) of resource throughout their execution. For a fully elastic activity A i , the cap(A i ) variable is not meaningful and we use a variable E(A i ) that represents the global “energy” required by the activity on the resource. Of course, for a non-elastic activity, we have E(A i ) = cap(A i )proc(A i ). In all case, enough resource must be allocated to activities, i.e., E(A i ) = Σ t E(A i , t), where E(A i , t) is the amount of resource used at t by A i . Recall that if A i is not an elastic activity, there are some strong relations between E(A i , t) and X(A i , t): E(A i , t) = X(A i , t)cap(A i ) For elastic activities, we have a weaker relation between the variables: [E(A i , t) # 0] ⇔ [X(A i i,t) # 0]. Generally speaking, the cumulative resource constraint can be stated as follows:
$$ \forall t\sum\limits_i {E(A_i ,t)} \le cap $$
In the non-preemptive case, it can be rewritten as,
$$ \forall t\sum\limits_{start(A_i ) \le t < end(A_i )} {cap(A_i )} \le cap $$
and in the preemptive case as,
$$ \forall t\sum\limits_{start(A_i ) \le t < end(A_i )} {X(A_i ,t)cap(A_i )} \le cap $$
In the following, we note c i and e i the minimal amount of the capacity (resp. of the energy) of the resource required by A i . Finally we note C the maximum value in the domain of the resource capacity. In this chapter, we recall the most well-known techniques used to propagate the cumulative resource constraint. We focus on the fully elastic case in Section 3.1, on the preemptive case in Section 3.2 and, finally, on the non-preemptive case in Section 3.3.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 4. Comparison of Propagation Techniques
Abstract
Many deductive rules and algorithms have been presented. The aim of this chapter is to compare the deductive power of these rules and algorithms, thereby providing a much clearer overview of the state of the art in the field.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 5. Propagation of Objective Functions
Abstract
In our model, a variable criterion represents the value taken by the objective function.
$$ criterion = F(end({A_1}),...,\;end({A_n})) $$
(5.1)
Considering the objective constraint and the resource constraints independently is not a problem when F is a “maximum” such as Cmax or Tmax. Indeed, the upper bound on criterion is directly propagated on the completion time of each activity, i.e., deadlines are efficiently tightened. The situation is much more complex for sum functions such as Σw i C i , Σw i T i or Σw i U i. For these functions, the constraint (5.1) has to be taken into account at each step of the search tree. An efficient constraint propagation technique must consider the resource constraints and the objective constraint simultaneously. In the following sections, we propose two efficient constraint-propagation techniques for the Σw i U i criterion and for the minimization of setup times.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 6. Resolution of Disjunctive Problems
Abstract
Disjunctive problems are scheduling problems where all resources are machines (hence activities on the same machine cannot overlap in time, i.e., they are in disjunction). These problems have been widely studied in the literature. In this chapter we address three problems: (1) the Job-Shop Problem where operations of jobs have to be processed in a given order by some specified machines, (2) the Open-Shop Problem where operations of the same job cannot overlap in time but can be executed in any order and (3) the Preemptive Job-Shop Problem.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 7. Cumulative Scheduling Problems
Abstract
Many industrial scheduling problems are variants, extensions or restrictions of the “Resource-Constrained Project Scheduling Problem”. Given (i) a set of resources with given capacities, (ii) a set of non-interruptible activities of given processing times, (iii) a network of precedence constraints between the activities, and (iv) for each activity and each resource the amount of the resource required by the activity over its execution, the goal of the RCPSP is to find a schedule meeting all the constraints whose makespan (i.e., the time at which all activities are finished) is minimal. The decision variant of the RCPSP, i.e., the problem of determining whether there exists a schedule of makespan smaller than a given deadline, is NP-hard in the strong sense [77].
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 8. Min-Sum Scheduling Problems
Abstract
We illustrate and compare the efficiency of the constraint propagation algorithms described in previous chapters on two well-known scheduling problems. In Section 8.1 we study the problem of minimizing the weighted number of late jobs on m parallel identical machines and in Section 8.2 we consider a general-shop scheduling problem with sequence-dependent setup times and alternative machines where the optimization criteria are both makespan and sum of setup times.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 9. Conclusion
Abstract
The various examples provided in Chapters 6, 7, and 8 have shown how a general Constraint-Based Scheduling model and the associated constraint propagation algorithms can be used to enable the resolution of complex scheduling problems.
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Chapter 10. Summary of Notation
Philippe Baptiste, Claude Le Pape, Wim Nuijten
Backmatter
Metadaten
Titel
Constraint-Based Scheduling
verfasst von
Philippe Baptiste
Claude Le Pape
Wim Nuijten
Copyright-Jahr
2001
Verlag
Springer US
Electronic ISBN
978-1-4615-1479-4
Print ISBN
978-1-4613-5574-8
DOI
https://doi.org/10.1007/978-1-4615-1479-4