Scheduling Algorithm

Contents
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 TheMaximum Flow Problem . . . . . . . . . . . . . . . 13
2.4 BipartiteMatching 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 | fmax . . . . . . . 62
4.1.2 1|prec; pj = 1; rj | fmax and 1 | prec; pmtn; rj | fmax 63
4.2 Maximum Lateness and Related Criteria . . . . . . . . . 67
4.3 TotalWeighted Completion Time . . . . . . . . . . . . . 73
4.3.1 1 | tree | wjCj . . . . . . . . . . . . . . . . . . 73
4.3.2 1 | sp-graph | wjCj . . . . . . . . . . . . . . . . 79
4.4 Weighted Number of Late Jobs . . . . . . . . . . . . . . 84
4.4.1 1 | rj ; pj = 1 | wjUj . . . . . . . . . . . . . . . 84
4.4.2 1 | pj = 1 | wjUj . . . . . . . . . . . . . . . . . 85
4.4.3 1 || Uj . . . . . . . . . . . . . . . . . . . . . . . 86
4.4.4 1 | rj ; pmtn | wjUj . . . . . . . . . . . . . . . . 88
4.5 TotalWeighted Tardiness . . . . . . . . . . . . . . . . . 93
4.6 Problems with Release Times and Identical Processing
Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.6.1 1 | rj ; pj = p | wjUj . . . . . . . . . . . . . . . 98
4.6.2 1 | rj ; pj = p | wjCj and 1 | rj ; pj = p | Tj . . 101
4.7 Complexity of SingleMachine Problems . . . . . . . . . 104
5 Parallel Machines 107
5.1 Independent Jobs . . . . . . . . . . . . . . . . . . . . . . 107
5.1.1 IdenticalMachines . . . . . . . . . . . . . . . . . 107
5.1.2 UniformMachines . . . . . . . . . . . . . . . . . 124
5.1.3 UnrelatedMachines . . . . . . . . . . . . . . . . . 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 GraphModel . . . . . . . . . . . . . . . 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 MinimizingMakespan . . . . . . . . . . . . . . . 174
6.4 Job Shop Problems . . . . . . . . . . . . . . . . . . . . . 178
6.4.1 Problems with TwoMachines . . . . . . . . . . . 179
6.4.2 Problems with Two Jobs. A Geometric Approach 186
6.4.3 Job Shop Problems with TwoMachines . . . . . . 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 TwoMachines . . . . . . . . . . . 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 | wi|Lσ(i)| + w0 · d . . . . . . . . . . . 244
7.2 Problem 1|dopt|wE Ei+wT Ti + w0d . . . . . . . . . 247
7.3 Problem 1 | d | wi|Lσ(i)| . . . . . . . . . . . . . . . . . 249
7.4 Problem 1 | d | wE Ei + wT Ti . . . . . . . . . . . . 255
7.5 Problem 1 | d | |Li|max and 1 | dopt | |Li|max . . . . . . . . 257
7.6 Problem 1 | dopt | wi|Li| . . . . . . . . . . . . . . . . . 259
7.7 Problem 1 | d | wi|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 SingleMachine Problems . . . . . . . . . . . . . . . . . . 282
9.2 Problems with ParallelMachines . . . . . . . . . . . . . 286
9.3 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

Download
Another The Core of CS books