Resource-constrained project scheduling [[electronic resource] ] : models, algorithms, extensions and applications / / edited by Christian Artigues, Sophie Demassey, Emmanuel Neron

• Record Nr.: UNINA9910139469403321
• Pubbl/distr/stampa: London, : ISTE; Hoboken, NJ, : John Wiley & Sons, 2008
• ISBN: 1-282-16508-9; 9786612165085; 0-470-61122-7; 0-470-39384-X
• Descrizione fisica: 1 online resource (310 p.)
• Collana: ISTE ; ; v.37
• Altri autori (Persone): DemasseySophie; NeronEmmanuel; ArtiguesChristian
• Disciplina: 658.5/3; 658.53
• Soggetti: Production scheduling; Scheduling
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Resource-Constrained Project Scheduling; Table of Contents; Preface; Part 1. Models and Algorithms for the Standard Resource-Constrained Project Scheduling Problem; Chapter 1. The Resource-Constrained Project Scheduling Problem; 1.1. A combinatorial optimization problem; 1.2. A simple resource-constrained project example; 1.3. Computational complexity; 1.4. Dominant and non-dominant schedule subsets; 1.5. Order-based representation of schedules and related dominant schedule sets; 1.6. Forbidden sets and resource flow network formulations of the RCPSP; 1.7. A simple method for enumerating a dominant set of quasi-active schedulesChapter 2. Resource and Precedence Constraint Relaxation; 2.1. Relaxing resource constraints; 2.2. Calculating the disjunctive subproblem; 2.3. Deducing identical parallel machine problems; 2.4. Single cumulative resource problem; 2.5. Conclusion and perspectives; ; Chapter 3. Mathematical Programming Formulations and Lower Bounds; 3.1. Sequence-based models; 3.1.1. Minimal forbidden sets; 3.1.2. Resource flow; 3.2. Time-indexed formulations; 3.2.1. Resource conflicts as linear constraints; 3.2.2. Feasible configurations3.2.2.1. Combinatorial relaxations; 3.2.2.2. Column generation and further improvements; 3.2.2.3. Cutting planes for the preemptive relaxation; 3.3. Linear lower bounds and redundant resources; Chapter 4. Constraint Programming Formulations and Propagation Algorithms; 4.1. Constraint formulations; 4.1.1. Constraint programming; 4.1.2. Constraint-based scheduling; 4.2. Constraint propagation algorithms; 4.2.1. Temporal constraints; 4.2.2. Timetabling; 4.2.3. Disjunctive reasoning; 4.2.4. Edge-finding; 4.2.5. Energy reasoning; 4.2.6. Precedence graph; 4.2.7. Energy precedence4.2.8. Balance constraint; 4.3. Conclusion; Chapter 5. Branching Schemes for Branch-and-Bound; 5.1. Chronological branching scheme; 5.1.1. Adding one activity to a partial solution; 5.1.1.1. Considering all relevant activities; 5.1.1.2. Delaying one activity; 5.1.2. Dominance rule: left shift and global left shift; 5.1.3. Adding a subset of activities to a partial solution; 5.1.3.1. Delaying alternatives; 5.1.3.2. Building a solution using blocks; 5.1.4. Dominance rule: cut-set; 5.2. Specific branching schemes; 5.2.1. Fixing disjunction and parallel relationship; 5.2.2. Reducing time-windows of activities5.2.3. Resolving forbidden sets; 5.3. Conclusion and perspectives; Chapter 6. Heuristics; 6.1. Schedule representation schemes; 6.1.1. Natural date variables; 6.1.2. List schedule generation scheme representations; 6.1.3. Set-based representations; 6.1.4. Resource flow network representation; 6.2. Constructive heuristics; 6.2.1. Standard list schedule generation scheme heuristics; 6.2.2. A generic insertion-based list schedule generation scheme; 6.2.3. Set schedule generation scheme heuristics; 6.2.4. (Double-)justification-based methods; 6.3. Local search neighborhoods
• Sommario/riassunto: This title presents a large variety of models and algorithms dedicated to the resource-constrained project scheduling problem (RCPSP), which aims at scheduling at minimal duration a set of activities subject to precedence constraints and limited resource availabilities.In the first part, the standard variant of RCPSP is presented and analyzed as a combinatorial optimization problem. Constraint programming and integer linear programming formulations are given. Relaxations based on these formulations and also on related scheduling problems are presented. Exact methods and heuristics are surv