Time-Dependent Scheduling (eBook)

Stanislaw Gawiejnowicz (Autor)

eBook Download: PDF

2008 | 2008
XVI, 380 Seiten
Springer Berlin (Verlag)
978-3-540-69446-5 (ISBN)

Infos

hebookpresentedtothereaderisdevotedtotime-dependentscheduling. TScheduling problems, in general, consist in the allocation of resources over time in order to perform a set of jobs. Any allocation that meets all requirements concerning the jobs and resources is called a feasible schedule. The quality of a schedule is measured by a criterion function. The aim of scheduling is to ?nd, among all feasible schedules, a schedule that optimizes the criterion function. A solution to an arbitrary scheduling problem consists in giving a polynomial-time algorithm generating either an optimal schedule or a schedule that is close to the optimal one, if the given scheduling problem has been proved to be computationally intractable. The scheduling problems are subject of interest of the scheduling theory, originated in mid-?fties of the twentieth century. The theory has been developing dynamically and new research areas constantly come into existence. The subject of this book, ti- dependent scheduling, is one of such areas. In time-dependent scheduling, the processing time of a job is variable and depends on the starting time of the job. This crucial assumption allows us to apply the scheduling theory to a broader spectrum of problems. For example, in the framework of the time-dependent scheduling theory we may consider the problems of repayment of multiple loans, ?re ?ghting and maintenance assignments. In this book, we will discuss algorithms and complexity issues concerning various time-dependent scheduling problems.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 26.9.2008
• Reihe/Serie: Monographs in Theoretical Computer Science. An EATCS Series
• Reihe/Serie: Monographs in Theoretical Computer Science. An EATCS Series
• Zusatzinfo: XVI, 380 p. 26 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Schlagworte: algorithm • Algorithm analysis and problem complexity • algorithms • approximation algorithms • combinatorial optimization • Complexity • Greedy algorithms • Heuristics • Local-search algorithms • Optimization • optimization theory • problem complexity • Scheduling • Search • tar
• ISBN-10: 3-540-69446-3 / 3540694463
• ISBN-13: 978-3-540-69446-5 / 9783540694465