Models and Algorithms of Time-Dependent Scheduling

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