Models and Algorithms of Time-dependent Scheduling

✍ Scribed by Stanislaw Gawiejnowicz

• Publisher: Springer-Nature New York Inc
• Year: 2019
• Tongue: English
• Leaves: 535
• Series: Monographs in Theoretical Computer Science, Eatcs
• Edition: 2
• Category: Library

✦ Synopsis

This is a comprehensive study of various time-dependent scheduling problems in single-, parallel- and dedicated-machine environments. In addition to complexity issues and exact or heuristic algorithms which are typically presented in scheduling books, the author also includes more advanced topics such as matrix methods in time-dependent scheduling, time-dependent scheduling with two criteria and time-dependent two-agent scheduling.

The reader should be familiar with the basic notions of calculus, discrete mathematics and combinatorial optimization theory, while the book offers introductory material on theory of algorithms, NP-complete problems, and the basics of scheduling theory. The author includes numerous examples, figures and tables, he presents different classes of algorithms using pseudocode, he completes all chapters with extensive bibliographies, and he closes the book with comprehensive symbol and subject indexes.

The previous edition of the book focused on computational complexity of time-dependent scheduling problems. In this edition, the author concentrates on models of time-dependent job processing times and algorithms for solving time-dependent scheduling problems. The book is suitable for researchers working on scheduling, problem complexity, optimization, heuristics and local search algorithms.

✦ Table of Contents

Preface
References
Preface to the first edition
Contents
Part I FUNDAMENTALS
1 Preliminaries
1.1 Mathematical notation and inference rules
1.1.1 Sets and vectors
1.1.2 Sequences
1.1.3 Functions
1.1.4 Logical notation and inference rules
1.1.5 Other notation
1.2 Basic definitions and results
1.2.1 Elementary lemmas
1.2.2 Graph theory definitions
1.2.3 Mean value theorems
1.2.4 Priority-generating functions
1.2.5 Bi-criteria optimization definitions
Bibliographic notes
Mathematical notation and inference rules
Basic definitions and results
References
Mathematical notation and inference rules
Basic definitions and results
2 Problems and algorithms
2.1 Decision and optimization problems
2.1.1 Encoding schemes
2.1.2 Undecidable and decidable problems
2.2 Basic concepts related to algorithms
2.2.1 Time and space complexity of algorithms
2.2.2 Pseudo-code of algorithms
2.2.3 Polynomial-time algorithms
2.2.4 Strongly and weakly polynomial-time algorithms
2.2.6 Pseudo-polynomial algorithms
2.2.7 Offline algorithms vs. online algorithms
2.3 Main types of exact algorithms
2.3.1 Enumeration algorithms
2.3.2 Branch-and-bound algorithms
2.3.3 Dynamic programming algorithms
2.4 Main types of approximation algorithms
2.4.1 Approximation algorithms
2.4.2 Approximation schemes
2.5 Main types of heuristic algorithms
2.5.1 Heuristic algorithms
2.5.2 Greedy algorithms
2.5.3 Local search algorithms
2.5.4 Meta-heuristic algorithms
Bibliographic notes
Decision and optimization problems
Basic concepts related to algorithms
Main types of exact algorithms
Main types of approximation algorithms
Main types of heuristic algorithms
References
Decision and optimization problems
Basic concepts related to algorithms
Main types of exact algorithms
Main types of approximation algorithms
Main types of heuristic algorithms
3 NP-complete problems
3.1 Basic definitions and results
3.1.1 The ordinary NP-completeness
3.1.2 The strong NP-completeness
3.1.3 Coping with NP-completeness
3.2 NP-complete problems
3.2.1 Additive NP-complete problems
3.2.2 Multiplicative
Bibliographic notes
References
Basic definitions and results
Additive NP-complete problems
Multiplicative NP-complete problems
Part II SCHEDULING MODELS
4 The classical scheduling theory
4.1 Models and problems of the scheduling theory
4.1.1 Scheduling models
4.1.2 Scheduling problems
4.2 Basic assumptions of the classical scheduling theory
4.3 Formulation of classical scheduling problems
4.3.1 Parameters of the set of jobs
4.3.2 Parameters of the set of machines
4.3.3 Parameters of the set of resources
4.4 The notion of schedule
4.4.1 The presentation of schedules
4.4.2 Parameters of job in a schedule
4.4.3 Types of schedules
4.5 The criteria of schedule optimality
4.6 Notation of scheduling problems
Bibliographic notes
References
5 The modern scheduling theory
5.1 Main directions in the modern scheduling theory
5.1.1 Scheduling multiprocessor tasks
5.1.2 Scheduling on machines with variable processing speeds
5.1.3 Scheduling jobs with variable processing times
5.2 Main models of variable job processing times
5.2.1 Models of position-dependent job processing times
Notation of position-dependent scheduling problems
Example results on position-dependent job scheduling
5.2.2 Models of controllable job processing times
Notation of controllable scheduling problems
Example results on controllable job scheduling
Bibliographic notes
Scheduling multiprocessor tasks
Resource-dependent scheduling
Scheduling on machines with variable speed
Variable job processing times
Position-dependent job scheduling problems
Controllable job scheduling problems
References
Scheduling multiprocessor tasks
Resource-dependent scheduling
Scheduling on machines with variable speed
Scheduling jobs with variable processing times
Position-dependent job scheduling problems
Controllable job scheduling problems
6 The time-dependent scheduling
6.1 Terminology of time-dependent scheduling
6.2 Pure models of time-dependent processing times
6.2.1 General models of time-dependent processing times
6.2.2 Specific models of deteriorating processing times
6.2.3 Specific models of shortening processing times
6.2.4 Specific models of alterable processing times
6.3 Mixedmodels of time-dependent job processing times
6.4 Notation of time-dependent scheduling problems
6.5 Mathematical background of time-dependent scheduling
6.6 Applications of time-dependent scheduling
6.6.1 Scheduling problems with deteriorating jobs
6.6.2 Scheduling problems with shortening jobs
6.6.3 Scheduling problems with alterable jobs
6.6.4 Scheduling problems with time-dependent parameters
6.6.5 Other problems with time-dependent parameters
Bibliographic notes
Single machine time-dependent scheduling problems
Parallel machine time-dependent scheduling problems
Dedicated machine time-dependent scheduling problems
References
Mathematical background of time-dependent scheduling
Scheduling problems with deteriorating jobs
Scheduling problems with shortening jobs
Scheduling problems with alterable jobs
Time-dependent scheduling problems with a learning effect
Scheduling problems with time-dependent parameters
Other problems with time-dependent parameters
Single machine time-dependent scheduling problems
Parallel machine time-dependent scheduling problems
Dedicated machine time-dependent scheduling problems
Part III POLYNOMIAL PROBLEMS
7 Polynomial single machine problems
7.1 Minimizing the maximum completion time
7.1.1 Proportional deterioration
7.1.2 Proportional-linear deterioration
7.1.3 Linear deterioration
7.1.4 Simple non-linear deterioration
7.1.5 General non-linear deterioration
7.1.6 Proportional-linear shortening
7.1.7 Linear shortening
7.1.8 Non-linear shortening
7.1.9 Simple alteration
7.2 Minimizing the total completion time
7.2.1 Proportional deterioration
7.2.2 Proportional-linear deterioration
7.2.3 Linear deterioration
7.2.4 Simple non-linear deterioration
7.2.5 General non-linear deterioration
7.2.6 Proportional-linear shortening
7.2.7 Linear shortening
7.3 Minimizing the maximum lateness
7.3.1 Proportional deterioration
7.3.2 Proportional-linear deterioration
7.3.3 Linear deterioration
7.3.4 Simple non-linear deterioration
Theorem 7.89.
7.4 Other criteria
7.4.1 Proportional deterioration
Minimizing the total weighted completion time
Minimizing the maximal cost
Minimizing the total lateness and the maximum tardiness
Minimizing the total number of tardy jobs
Minimizing the total deviation of completion times
7.4.2 Proportional-linear deterioration
Minimizing the total weighted completion time
Minimizing the total number of tardy jobs
Minimizing the maximum cost
7.4.3 Linear deterioration
Minimizing the total weighted completion times
Minimizing the maximal processing time
Minimizing the total earliness and tardiness
7.4.4 Simple non-linear deterioration
Minimizing the total weighted completion time
Minimizing the total general completion time
7.4.5 General non-linear deterioration
Minimizing the total weighted completion time
7.4.6 Proportional-linear shortening
Minimizing the total weighted completion time
Minimizing the total number of tardy jobs Theorem 7.145.
Minimizing the maximal cost Theorem 7.146.
7.4.7 Linear shortening
Minimizing the total weighted completion time
Minimizing the total number of tardy jobs
Minimizing the total earliness cost
Minimizing the total earliness and tardiness
References
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the maximum lateness
Other criteria
8 Polynomial parallel machine problems
8.1 Minimizing the total completion time
8.1.1 Linear deterioration
8.1.2 Simple non-linear deterioration
8.1.3 Linear shortening
8.2 Minimizing the total weighted earliness and tardiness
References
Minimizing the total completion time
Minimizing the total weighted earliness and tardiness
9 Polynomial dedicated machine problems
9.1 Minimizing the maximum completion time
9.1.1 Proportional deterioration
Flow shop problems
Open shop problems
9.1.2 Proportional-linear deterioration
Flow shop problems
Open shop problems
9.1.3 Linear deterioration
Flow shop problems
9.1.4 Simple non-linear deterioration
Flow shop problems
9.1.5 Proportional-linear shortening
Flow shop problems
9.2 Minimizing the total completion time
9.2.1 Proportional deterioration
Flow shop problems
9.2.2 Linear deterioration
Flow shop problems
9.2.3 Proportional-linear shortening
Flow shop problems
9.3 Minimizing the maximum lateness
9.3.1 Proportional-linear deterioration
Flow shop problems
9.3.2 Proportional-linear shortening
Flow shop problems
9.4 Other criteria
9.4.1 Proportional deterioration
Flow shop problems
9.4.2 Proportional-linear deterioration
Flow shop problems
9.4.3 Linear deterioration
Flow shop problems
9.4.4 Proportional-linear shortening
Flow shop problems
References
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the maximum lateness
Other criteria
Part IV NP-HARD PROBLEMS
10 NP=hard single machine problems
10.1 Minimizing the maximum completion time
10.1.1 Proportional deterioration
10.1.2 Linear deterioration
10.1.3 General non-linear deterioration
10.1.4 Linear shortening
10.1.5 General non-linear shortening
10.1.6 Simple alteration
10.2 Minimizing the total completion time
10.2.1 Linear shortening
10.3 Minimizing the maximum lateness
10.3.1 Linear deterioration
10.3.2 Linear shortening
10.3.3 General non-linear shortening
10.4 Other criteria
10.4.1 Linear deterioration
10.4.2 Linear shortening
10.4.3 General non-linear shortening
References
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the maximum lateness
Other criteria
11 NP-hard parallel machine problems
11.1 Minimizing the maximum completion time
11.1.1 Proportional deterioration
11.1.2 Linear deterioration
11.1.3 Linear shortening
11.2 Minimizing the total completion time
11.2.1 Proportional deterioration
11.2.2 Linear deterioration
11.3 Other criteria
11.3.1 Proportional deterioration
11.3.2 Linear deterioration
References
Minimizing the maximum completion time
Minimizing the total completion time
Other criteria
12 NP-hard dedicated machine problems
12.1 Minimizing the maximum completion time
12.1.1 Proportional deterioration
Flow shop problems
Open shop problems
Job shop problems
12.1.2 Linear deterioration
Flow shop problems
Open shop problems
Job shop problems
12.2 Minimizing the total completion time
Flow shop problems
12.3 Minimizing the maximum lateness
12.3.1 Proportional deterioration
Flow shop problems
Open shop problems
12.3.2 Linear deterioration
Flow shop problems
References
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the maximum lateness
Part V ALGORITHMS
13 Exact algorithms
13.1 Preliminaries
13.2 Exact algorithms for single machine problems
13.2.1 Minimizing the maximum completion time
Linear deterioration
General non-linear deterioration
Simple alteration
13.2.2 Minimizing the total completion time
General non-linear deterioration
Linear shortening
13.2.3 Minimizing the maximum lateness
Linear deterioration
13.2.4 Other criteria
Linear deterioration
General non-linear deterioration
13.3 Exact algorithms for parallel machine problems
13.3.1 Minimizing the maximum completion time
13.3.2 Minimizing the total completion time
Proportional deterioration
Simple non-linear deterioration
13.4 Exact algorithms for dedicated machine problems
13.4.1 Minimizing the maximum completion time
Proportional deterioration
Linear deterioration
13.4.2 Minimizing the total completion time
Proportional deterioration
Proportional-linear deterioration
Linear deterioration
13.4.3 Other criteria
Proportional deterioration
Proportional-linear shortening
References
Exact algorithms for single machine problems
Exact algorithms for parallel machine problems
Exact algorithms for dedicated machine problems
14 Approximation algorithms and schemes
14.1 Preliminaries
14.2 Minimizing the maximum completion time
14.2.1 Proportional deterioration
Single machine problems
Parallel machine problems
Dedicated machine problems
14.2.2 Linear deterioration
Parallel machine problems
14.2.3 General non-linear deterioration
Single machine problems
14.2.4 Linear shortening
Parallel machine problems
14.2.5 General non-linear shortening
Single machine problems
Parallel machine problems
14.3 Minimizing the total completion time
Single machine problems
Parallel machine problems
14.4 Other criteria
14.4.1 Proportional deterioration
14.4.2 Proportional-linear deterioration
References
Preliminaries
Minimizing the maximum completion time
Minimizing the total completion time
Other criteria
15 Greedy algorithms based on signatures
15.1 Preliminaries
15.1.1 Problem formulation
15.1.2 Definition of signatures
15.2 Basic properties of signatures
15.3 The first greedy algorithm
15.3.1 Formulation
15.3.2 Computational experiments
15.4 Signatures of regular sequences
15.5 The second greedy algorithm
15.5.1 Arithmetic sequences
15.5.2 Geometric sequences
15.5.3 Arbitrary sequences
References
16 Heuristic algorithms
16.1 Preliminaries
16.2 Minimizing the maximum completion time
16.2.1 Linear deterioration
Parallel machine problems
16.2.2 General non-linear deterioration
16.2.3 Linear shortening
Single machine problems
16.3 Minimizing the total completion time
16.3.1 Proportional deterioration
Parallel machine problems
Dedicated machine problems
16.3.2 Linear deterioration
Single machine problems
Dedicated machine problems
16.3.3 Linear shortening
Single machine problems
16.4 Minimizing the maximum lateness
16.4.1 Linear deterioration
Single machine problems
16.4.2 General non-linear deterioration
Single machine problems
16.5 Other criteria
16.5.1 Proportional deterioration
Single machine problems
Parallel machine problems
16.5.2 Linear deterioration
Single machine problems
Parallel machine problems
16.5.3 General non-linear deterioration
Single machine problems
16.5.4 Linear shortening
Single machine problems
References
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the maximum lateness
Other criteria
17 Local search and meta-heuristic algorithms
17.1 Preliminaries
17.1.1 Basic definitions
17.1.2 General concepts in local search
17.1.3 Pros and cons of local search algorithms
17.2 Main types of local search algorithms
17.2.1 Iterative improvement
17.2.2 Steepest descent search
17.3 Main types of meta-heuristic algorithms
17.3.1 Simulated annealing
17.3.2 Tabu search
17.3.3 Genetic algorithms
17.3.4 Evolutionary algorithms
17.3.5 Ant colony optimization
17.3.6 Particle swarm optimization
17.4 Local search time-dependent scheduling algorithms
17.4.1 Iterative improvement algorithms
17.4.2 Steepest descent search algorithms
Experimental evaluation of Algorithms 17.12 and 17.10
17.5 Meta-heuristic time-dependent scheduling algorithms
17.5.1 Simulated annealing algorithms
17.5.2 Tabu search algorithms
17.5.3 Genetic algorithms
17.5.4 Evolutionary algorithms
17.5.5 Ant colony optimization algorithms
17.5.6 Particle swarm optimization algorithms
References
General concepts in local search
General concepts in meta-heuristic algorithms
Local search time-dependent scheduling algorithms
Meta-heuristic time-dependent scheduling algorithms
Part VI ADVANCED TOPICS
18 Time-dependent scheduling under precedence constraints
18.1 Proportional deterioration
18.1.1 Chain precedence constraints
18.1.2 Series-parallel precedence constraints
18.1.3 Arbitrary precedence constraints
18.2 Proportional-linear deterioration
18.3 Linear deterioration
18.3.1 Preliminaries
18.3.2 Chain precedence constraints
18.3.3 Tree and forest precedence constraints
18.3.4 Series-parallel precedence constraints
18.4 Proportional-linear shortening
18.4.1 Chain precedence constraints
18.4.2 Series-parallel precedence constraints
18.5 Linear shortening
18.5.1 Chain precedence constraints
18.5.2 Tree precedence constraints
18.5.3 Series-parallel precedence constraints
References
Proportional deterioration
Proportional-linear deterioration
Linear deterioration
Proportional-linear shortening
Linear shortening
19 Matrix methods in time-dependent scheduling
19.1 Preliminaries
19.2 The matrix approach
19.2.1 The matrix form of single machine problems
19.2.2 The matrix form of parallel machine problems
19.3 Minimizing the lp norm
19.3.1 Problem formulation
19.3.2 Injectivity and convexity
19.3.3 Bounded logarithmic growth
19.3.4 Asymmetricity
19.3.5 V-shapeness
19.4 Equivalent scheduling problems
19.4.1 The initial problem
Single machine initial problems
Parallel machine initial problems
19.4.2 The transformed problem
Single machine transformed problems
Parallel machine transformed problems
19.4.3 Properties of equivalent problems
19.5 Conjugate scheduling problems
19.5.1 The initial problem
19.5.2 The composite problem
19.5.3 The conjugate problem
19.5.4 Properties of conjugate problems
19.6 Isomorphic scheduling problems
19.6.1 Generic problem
19.6.2 The (γ,θ)-reducibility
19.6.3 Algorithms for isomorphic problems
Preliminary definitions
Polynomial algorithms for isomorphic problems
Approximation algorithms for isomorphic problems
Examples of single machine isomorphic scheduling problems
Examples of dedicated machine isomorphic scheduling problems
References
The matrix approach
Minimizing the lp norm
Equivalent scheduling problems
Conjugate scheduling problems
Isomorphic scheduling problems
20 Bi-criteria time-dependent scheduling
20.1 Preliminaries
20.1.1 Problems formulation
20.1.2 Preliminary results
20.2 Pareto optimality
20.2.1 Basic definitions
20.2.2 Main results
20.3 Scalar optimality
20.3.1 Basic definitions
20.3.2 Main results
20.4 Computational experiments
20.5 Other results
References
Pareto optimality
Scalar optimality
21 New topics in time-dependent scheduling
21.1 Time-dependent scheduling on machines with limited availability
21.1.1 Preliminaries
21.1.2 Proportional deterioration
21.1.3 Linear deterioration
21.2 Time-dependent two-agent scheduling
21.2.1 Preliminaries
21.2.2 Proportional deterioration
21.2.3 Proportional-linear deterioration
21.2.4 Linear deterioration
21.2.5 Proportional-linear shortening
21.3 Time-dependent scheduling with job rejection
21.3.1 Preliminaries
21.3.2 Main results
21.4 Time-dependent scheduling with mixed job processing times
21.4.1 Preliminaries
21.4.2 Main results
Minimizing the maximum completion time
Minimizing the total completion time
Minimizing the total weighted completion time
Minimizing the maximum lateness
21.5 Time-dependent scheduling games
21.5.1 Preliminaries
21.5.2 Main results
References
Time-dependent scheduling on machines with limited availability
Two-agent time-dependent scheduling
Time-dependent scheduling with job rejection
Time-dependent scheduling with mixed job processing times
Time-dependent scheduling games
Part A APPENDIX
A Open time-dependent scheduling problems
A.1 Open single machine scheduling problems
A.2 Open parallel machine scheduling problems
A.3 Open dedicated machine scheduling problems
References
Open single machine scheduling problems
Open parallel machine scheduling problems
Open dedicated machine scheduling problems
List of Algorithms
List of Figures
List of Tables
Symbol Index
Subject Index