Preface ......................................................... v
1. Classification of Scheduling Problems ........................ 1
1.1. Scheduling Problems ..................................... 1
1.2. Job Data ................................................ 2
1.3. Job Characteristics ..................................... 3
1.4. Machine Environment ..................................... 5
1.5. Optimality Criteria ..................................... 6
1.6. Examples ................................................ 7
2. Some Problems in Combinatorial Optimization ................. 11
2.1. Linear and Integer Programming ......................... 11
2.2. Transshipment Problems ................................. 12
2.3. The Maximum Flow Problem ............................... 13
2.4. Bipartite Matching Problems ............................ 14
2.5. The Assignment Problem ................................. 18
2.6. Arc Coloring of Bipartite Graphs ....................... 22
2.7. Shortest Path Problems and Dynamic Programming ......... 26
3. Computational Complexity .................................... 37
3.1. The Classes P and NP ................................... 37
3.2. NP-complete and NP-hard Problems ....................... 41
3.3. Simple Reductions Between Scheduling Problems .......... 48
3.4. Living with NP-hard Problems ........................... 51
3.4.1. Local Search Techniques ......................... 51
3.4.2. Branch-and-Bound Algorithms ..................... 56
4. Single Machine Scheduling Problems .......................... 61
4.1. Minimax Criteria ....................................... 62
4.1.1. Lawler's Algorithm for 1 | prec |  max ........... 62
4.1.2. l | prec;pj = l; rj | max and 1 | prec;pmtn;rj |
max ............................................. 63
4.2. Maximum Lateness and Related Criteria .................. 67
4.3. Total Weighted Completion Time ......................... 73
4.3.1. 1 |tree| ∑ωjCj .................................. 73
4.3.2. 1 |sp-graph| ∑ωjCj .............................. 79
4.4. Weighted Number of Late Jobs ........................... 84
4.4.1. 1 |rj;pj = 1| ∑ωjUj .............................. 84
4.4.2. l |Pj = l| ∑ωjUj ................................. 85
4.4.3. 1 || ∑ Uj ....................................... 86
4.4.4. 1 | rj;pmtn | ∑ωjUj .............................. 88
4.5. Total Weighted Tardiness ............................... 93
4.6. Problems with Release Times and Identical Processing
Times .................................................. 98
4.6.1. 1 | rj;pj = p | ∑ωjUj ............................ 98
4.6.2. 1 | rj;pj = p | ∑ωjCj and 1 | rj;pj = p | ∑Tj .... 101
4.7. Complexity of Single Machine Problems ................. 104
5. Parallel Machines .......................................... 107
5.1. Independent Jobs ...................................... 107
5.1.1. Identical Machines ............................. 107
5.1.2. Uniform Machines ............................... 124
5.1.3. Unrelated Machines ............................. 136
5.2. Jobs with Precedence Constraints ...................... 139
5.2.1. P | tree;pi = 1 | Lmax-Problems ................. 140
5.2.2. Problem P2 | prec pi = 1 | Lmax ................. 145
5.3. Complexity Results .................................... 150
6. Shop Scheduling Problems ................................... 155
6.1. The Disjunctive Graph Model ........................... 156
6.2. Open Shop Problems .................................... 158
6.2.1. Arbitrary Processing Times ..................... 158
6.2.2. Unit Processing Times .......................... 161
6.3. Flow Shop Problems .................................... 174
6.3.1. Minimizing Makespan ............................ 174
6.4. Job Shop Problems ..................................... 178
6.4.1. Problems with Two Machines ..................... 179
6.4.2. Problems with Two Jobs. A Geometric Approach ... 186
6.4.3. Job Shop Problems with Two Machines ............ 196
6.4.4. A Branch-and-Bound Algorithm ................... 202
6.4.5. Applying Tabu-Search to the Job Shop Problem ... 221
6.5. Mixed Shop Problems ................................... 226
6.5.1. Problems with Two Machines ..................... 226
6.5.2. Problems with Two Jobs ......................... 227
6.6. Complexity of Shop Scheduling Problems ................ 232
7. Due-Date Scheduling ........................................ 243
7.1. Problem 1 | dopt | ∑ωi | Lσ(i) | + ω0 · d ............... 244
7.2. Problem l | dopt | ωE ∑ Ei + ωT ∑ Ti + ω0d .............. 247
7.3. Problem 1 | d | ∑ωi | Lσ(i) | .......................... 249
7.4. Problem 1 | d | ωE ∑ Ei + ωT ∑ Ti ..................... 255
7.5. Problem 1 | d | | Li |max and 1 | dopt || Li |max ....... 257
7.6. Problem 1 | dopt |∑ωi | Li | ........................... 259
7.7. Problem 1 | d | ∑ωi | Li | ............................ 262
8. Batching Problems .......................................... 267
8.1. Single Machine .s-Batching Problems ................... 267
8.2. Single Machine p-Batching Problems .................... 271
8.2.1. The Unbounded Model ............................ 272
8.2.2. The Bounded Model .............................. 276
8.3. Complexity Results for Single Machine Batching
Problems .............................................. 277
9. Changeover Times and Transportation Times .................. 281
9.1. Single Machine Problems ............................... 282
9.2. Problems with Parallel Machines ....................... 286
9.З. General Shop Problems ................................. 290
10.Multi-Purpose Machines ..................................... 293
10.1. MPM Problems with Identical and Uniform Machines ..... 294
10.2. MPM Problems with Shop Characteristics ............... 300
10.2.1. Arbitrary Processing Times .................... 300
10.2.2. Unit Processing Times ......................... 311
10.3. Complexity Results ................................... 315
11.Multiprocessor Tasks ....................................... 317
11.1. Multiprocessor Task Systems .......................... 318
11.2. Shop Problems with MPT: Arbitrary Processing Times ... 323
11.3. Shop Problems with MPT: Unit Processing Times ........ 329
11.4. Multi-Mode Multiprocessor-Task Scheduling Problems ... 335
11.5. Complexity Results ................................... 342
Bibliography .................................................. 347
Index ......................................................... 367
| 
