Intro; FOREWORD; References; Contents; 1 Introduction; References; 2 Basics; 2.1 Sets and Relations; 2.2 Problems, Algorithms, Complexity; 2.2.1 Problems and Their Encoding; 2.2.2 Algorithms; 2.2.3 Complexity; 2.3 Graphs and Networks; 2.3.1 Basic Notions; 2.3.2 Special Classes of Digraphs; 2.3.3 Networks; 2.4 Enumerative Methods; 2.4.1 Dynamic Programming; 2.4.2 Branch and Bound; 2.5 Heuristic and Approximation Algorithms; 2.5.1 Approximation Algorithms; 2.5.2 Local Search Heuristics; References; 3 Definition, Analysis and Classification of Scheduling Problems

3.1 Definition of Scheduling Problems3.2 Analysis of Scheduling Problems and Algorithms; 3.3 Motivations for Deterministic Scheduling Problems; 3.4 Classification of Deterministic Scheduling Problems; References; 4 Scheduling on One Processor; 4.1 Minimizing Schedule Length; 4.1.1 Scheduling with Release Times and Deadlines; 4.1.2 Scheduling with Release Times and Delivery Times; 4.2 Minimizing Mean Weighted Flow Time; 4.3 Minimizing Due Date Involving Criteria; 4.3.1 Maximum Lateness; 4.3.2 Number of Tardy Tasks; 4.3.3 Mean Tardiness; 4.3.4 Mean Earliness; 4.4 Minimizing Change-Over Cost

4.4.1 Setup Scheduling4.4.2 Lot Size Scheduling; 4.5 Other Criteria; 4.5.1 Maximum Cost; 4.5.2 Total Cost; References; 5 Scheduling on Parallel Processors; 5.1 Minimizing Schedule Length; 5.1.1 Identical Processors; 5.1.2 Uniform and Unrelated Processors; 5.2 Minimizing Mean Flow Time; 5.2.1 Identical Processors; 5.2.2 Uniform and Unrelated Processors; 5.3 Minimizing Due Date Involving Criteria; 5.3.1 Identical Processors; 5.3.2 Uniform and Unrelated Processors; 5.4 Lot Size Scheduling; References; 6 Communication Delays and Multiprocessor Tasks; 6.1 Introductory Remarks

6.2 Scheduling Multiprocessor Tasks6.2.1 Parallel Processors; 6.2.2 Dedicated Processors; 6.2.3 Refinement Scheduling; 6.3 Scheduling Uniprocessor Tasks with Communication Delays; 6.3.1 Scheduling without Task Duplication; 6.3.2 Scheduling with Task Duplication; 6.3.3 Scheduling in Processor Networks; 6.4 Scheduling Divisible Tasks; References; 7 Scheduling in Hard Real-Time Systems; 7.1 Introduction; 7.1.1 What is a Real-Time System?; 7.1.2 Examples of Real-Time Systems; 7.1.3 Characteristics of Real-Time Systems; 7.1.4 Functional Requirements for Real-Time Systems; 7.2 Basic Notions

7.2.1 Structure of a Real-Time System7.2.2 The Task Model; 7.2.3 Schedules; 7.3 Single Processor Scheduling; 7.3.1 Static Priority Scheduling; 7.3.2 Dynamic Priority Scheduling; 7.4 Scheduling Periodic Tasks on Parallel Processors; 7.5 Resources; 7.6 Variations of the Periodic Task Model; References; 8 Flow Shop Scheduling; 8.1 Introduction; 8.1.1 The Flow Shop Scheduling Problem; 8.1.2 Complexity; 8.2 Exact Methods; 8.2.1 The Algorithms of Johnson and Akers; 8.2.2 Dominance and Branching Rules; 8.2.3 Lower Bounds; 8.3 Approximation Algorithms