Complex Scheduling

Cover......Page 1
Complex Scheduling......Page 4
Preface of the Second Edition......Page 6
Preface......Page 7
Contents......Page 8
1.1 The RCPSP and some Generalizations......Page 12
Generalized precedence constraints......Page 15
Time-dependent resource profiles......Page 16
Multiple modes......Page 17
Non-renewable resources......Page 18
Partially renewable resources......Page 20
Storage resources......Page 21
Setup or transfer times......Page 22
Other objective functions......Page 23
1.2.2 Parallel machine scheduling......Page 25
1.2.3 Shop scheduling......Page 26
Open-shop problems......Page 27
1.2.4 Multi-processor task scheduling......Page 28
Application 1.2 : Aircraft maintenance......Page 29
Application 1.4 : Gate scheduling......Page 30
Application 1.5 : Batch scheduling in process industries......Page 32
Application 1.6 : High-school timetabling......Page 33
Application 1.7 : An audit-staff scheduling problem......Page 34
Application 1.8 : Sports league scheduling......Page 35
1.4 Reference Notes......Page 39
2.1 Easy and Hard Problems......Page 40
2.1.2 NP-hard problems......Page 41
2.2.1 Dijkstra’s algorithm......Page 46
2.2.2 Label-correcting algorithms......Page 50
2.2.4 Floyd-Warshall algorithm......Page 53
2.3.1 Linear programs and the simplex algorithm......Page 55
2.3.2 Duality......Page 63
2.3.3 The revised simplex method......Page 67
2.3.4 Delayed column generation techniques......Page 69
2.4 Lagrangian Relaxation......Page 73
2.5.1 The minimum cost flow problem......Page 76
2.5.2 The residual network and decomposition of flows......Page 78
Application 2.2 : Scheduling on identical parallel machines......Page 83
2.5.4 Flows and cuts......Page 84
Application 2.3 : Distributed computing on a two-processor computer......Page 85
2.5.5 Algorithms for the maximum flow problem......Page 87
2.5.6 Algorithms for the minimum cost flow problem......Page 91
2.6.1 Basic concepts......Page 93
2.6.2 The knapsack problem......Page 95
2.6.3 Integer linear programs......Page 99
2.7 Constraint Programming......Page 102
2.8 The Satisfiability Problem (SAT)......Page 108
2.9 Dynamic Programming......Page 111
2.10.1 Local search algorithms......Page 114
2.10.2 Genetic algorithms......Page 121
2.10.3 Ant colony optimization......Page 124
2.11 Reference Notes......Page 126
3.1.1 Temporal analysis......Page 127
3.1.2 A classification of schedules......Page 129
3.1.3 Reference notes......Page 131
3.2.1 Schedule generation schemes......Page 132
3.2.2 Priority-based heuristics......Page 138
Swap-neighborhood......Page 140
Shift-neighborhood......Page 141
3.2.4 Genetic algorithms......Page 142
One-point crossover......Page 143
Two-point crossover......Page 144
Uniform crossover......Page 145
3.2.5 Ant colony optimization......Page 146
3.2.7 Reference notes......Page 147
3.3.1 Discrete time formulations......Page 148
3.3.2 Continuous time formulations......Page 150
3.3.3 Event-based formulations......Page 152
Start/End Event-based formulation......Page 153
On/Off Event-based formulation......Page 155
3.3.4 Project scheduling with labor constraints......Page 158
3.4 A SAT Formulation of the RCPSP......Page 160
3.5 General Objective Functions for Problems without Resource Constraints......Page 161
3.5.2 Linear functions......Page 162
3.5.3 Convex piecewise linear functions......Page 164
3.5.4 General sum functions......Page 167
Constructing a feasible schedule from a minimum a, b-cut......Page 170
3.5.5 Reference notes......Page 171
3.6.1 Basic relations......Page 172
3.6.2 Start-start distance matrix......Page 173
3.6.3 Symmetric triples and extensions......Page 175
3.6.4 Disjunctive sets......Page 178
Input/Output tests......Page 181
Input/Output negation tests......Page 186
Input-or-Output test......Page 190
3.6.6 Constraint propagation for the multi-mode case......Page 196
3.6.7 Reference notes......Page 202
3.7 Lower Bounds......Page 203
3.7.1 Combinatorial constructive lower bounds......Page 204
3.7.2 Lower bounds based on Lagrangian relaxation......Page 206
3.7.3 An LP-based constructive lower bound......Page 207
3.7.4 An LP-based destructive method......Page 213
Non-preemptive cuts......Page 216
Precedence cuts......Page 218
3.7.5 A destructive method for the multi-mode case......Page 221
3.7.6 Reference notes......Page 226
3.8.1 An algorithm based on precedence trees......Page 227
3.8.2 An algorithm based on extension alternatives......Page 231
3.8.3 An algorithm based on delaying alternatives......Page 235
3.8.4 An algorithm based on schedule schemes......Page 241
3.8.5 Algorithms for the multi-mode case......Page 247
3.8.6 Reference notes......Page 248
4.1.1 Problem formulation......Page 249
4.1.2 The disjunctive graph model......Page 250
4.2 Heuristic Methods......Page 254
4.3 Branch-and-Bound Algorithms......Page 262
Time-lags......Page 263
Blocking......Page 264
4.5.1 Problem formulation......Page 269
4.5.2 Heuristic methods......Page 270
4.6.1 Problem formulation......Page 277
4.6.2 Problems without transportation conflicts......Page 278
4.6.3 Problems with transportation conflicts......Page 281
4.6.4 Constraint propagation......Page 289
4.6.5 Lower bounds......Page 295
4.6.6 Heuristic methods......Page 306
An one-stage approach......Page 307
A two-stage approach......Page 309
4.7.1 Problem formulation......Page 310
4.7.2 Representation of solutions......Page 311
4.7.3 Flow-shop problems with intermediate buffers......Page 316
4.7.5 Job-shop problems with output buffers......Page 318
4.7.6 Job-shop problems with input buffers......Page 324
4.7.7 Job-shop problems with job-dependent buffers......Page 325
4.8 Reference Notes......Page 326
Bibliography......Page 328
Index......Page 343