Time-Dependent Scheduling (eBook)

Preface 6
Contents 9
Part I FUNDAMENTALS 15
1 Preliminaries 16
1.1 Mathematical notation 16
1.2 Basic definitions and results 19
1.3 Bibliographic notes 26
2 Problems and algorithms 27
2.1 Decision and optimization problems 27
2.2 Basic concepts related to algorithms 29
2.3 Bibliographic notes 38
3 NP- complete problems 39
3.1 Basic definitions and results 39
3.2 Examples of NP- complete problems 43
3.3 Bibliographic notes 45
4 Basics of the scheduling theory 46
4.1 Parameters of the scheduling problem 46
4.2 The notion of schedule 50
4.3 The criteria of schedule optimality 54
4.4 Notation of scheduling problems 56
4.5 Bibliographic notes 57
5 Basics of time-dependent scheduling 58
5.1 The scheduling theory vs. time-dependent scheduling 58
5.2 Formulation of time-dependent scheduling problems 60
5.3 Terminology and notation 62
5.4 Applications of time-dependent scheduling 64
5.5 Bibliographic notes 67
Part II COMPLEXITY 68
6 Single-machine time-dependent scheduling 69
6.1 Minimizing the maximum completion time 69
6.2 Minimizing the total completion time 113
6.3 Minimizing the maximum lateness 128
6.4 Other criteria 133
6.5 Summary and tables 157
7 Parallel-machine time-dependent scheduling 164
7.1 Minimizing the maximum completion time 164
7.2 Minimizing the total completion time 169
7.3 Other criteria 173
7.4 Summary and tables 176
8 Dedicated-machine time-dependent scheduling 179
8.1 Minimizing the maximum completion time 179
8.2 Minimizing the total completion time 194
8.3 Minimizing the maximum lateness 200
8.4 Other criteria 202
8.5 Summary and tables 204
Part III ALGORITHMS 209
9 Approximation and heuristic algorithms 210
9.1 Minimizing the maximum completion time 210
9.2 Minimizing the total completion time 233
9.3 Minimizing the maximum lateness 241
9.4 Other criteria 243
9.5 Concluding remarks 247
10 Greedy algorithms based on signatures 252
10.1 Preliminaries 252
10.2 Basic properties of signatures 254
10.3 A greedy algorithm 258
10.4 Signatures of regular sequences 261
10.5 Concluding remarks 272
11 Local search algorithms 273
11.1 Preliminaries 273
11.2 Selected types of local search algorithms 275
11.3 Local search time-dependent scheduling algorithms 279
11.4 Concluding remarks 288
Part IV ADVANCED TOPICS 289
12 Matrix methods in time-dependent scheduling 290
12.1 Preliminaries 290
12.2 A matrix approach 291
12.3 The lp norm criterion 294
12.4 Equivalent problems 297
12.5 Concluding remarks and open problems 303
13 Scheduling dependent deteriorating jobs 304
13.1 Preliminaries 304
13.2 Chain precedence constraints 309
13.3 Tree and forest precedence constraints 312
13.4 Series-parallel constraints 317
13.5 General precedence constraints 320
13.6 Concluding remarks and open problems 323
14 Time-dependent scheduling with two criteria 325
14.1 Preliminaries 325
14.2 Pareto optimality 328
14.3 Scalar optimality 332
14.4 Computational experiments 339
14.5 Concluding remarks and open problems 341
Afterword 342
References 344
List of Figures 360
List of Tables 361
Author Index 364
Subject Index 368
Symbol Index 375