A Book of Open Shop Scheduling: Algorithms, Complexity and Applications

Description

This book provides an in-depth presentation of algorithms for and complexity of open shop scheduling. Open shops allow operations of a job to be executed in any order, contrary to flow and job shops where the order is pre-specified. The author brings the field up to date with more emphasis on new and recent results, and connections with graph edge coloring and mathematical programming. The book explores applications to production and operations management, wireless network scheduling, and timetabling.  The book is addressed to researchers, graduate students, and practitioners in Operations Research, Operations Management, computer science and mathematics, who are developing and using mathematical approaches to applications in manufacturing, services and distributed wireless network scheduling. Preface References Contents 1 Preliminaries 1.1 Open Shop 1.2 Open Shop Scheduling and Multigraph Edge Coloring 1.2.1 Job-Machine Bipartite Multigraph 1.2.2 Edge Coloring 1.2.3 General Multigraph 1.2.4 Open Shop Scheduling and Doubly Stochastic Matrices 1.2.5 Vector Rearrangement Theorem References 2 Makespan Minimization for Two-Machine Open Shops 2.1 Introduction 2.2 A Linear-Time Algorithm for Two-Machine Open Shop 2.3 Open Shop with Additional Renewable Resources 2.4 A Network Flow Algorithm for O2| res …, pmtn|Cmax 2.5 An Algorithm for O2| res 1 . .|Cmax 2.6 Open Problems Problems References 3 General Open Shop Scheduling 3.1 Complexity of Makespan Minimization 3.2 Approximate Solutions 3.2.1 A Greedy 2-Approximation Algorithm 3.2.2 No (54-ε)-Approximation Algorithm Exists Unless P=NP 3.2.3 Approximation for Fixed Number of Machines Om| | Cmax and m=3, 4, … 3.3 A Scheme for Polynomially Solvable Cases 3.4 Other Objective Functions 3.5 Open Shop Scheduling with All Unit-Time Operations 3.5.1 Open Shop Scheduling and Scheduling on Identical Parallel Processors 3.5.2 Horn's Algorithm for P|pmtn, pi=m, ri|Lmax Turned into an Algorithm for O|pij=1, ri| Lmax 3.5.3 Algorithm for P|pmtn, pi=m, ri|Ci Turned into an Algorithm for O|pij=1, ri| Ci 3.5.4 Algorithm for P|pmtn, pi=m|Ci Turned into an Algorithm O|pij=1|wiCi 3.5.5 Other Open Shop Scheduling Problems with All Unit-Time Operations 3.6 Open Shops with 0–1 Operations 3.6.1 Makespan Minimization: Problem O|pij= 0, 1| Cmax 3.6.2 Total Completion Time: Problem O|pij= 0, 1|Ci 3.6.3 Maximum Lateness: Problem O|pij=0,1, ri|Lmax; and Number of Tardy Jobs: Problem O|pij=0,1|Ui 3.7 Preemptive Open Shop Scheduling 3.7.1 An Algorithm for O|pmtn |Cmax 3.7.2 An Algorithm for O|pmtn, rj| Lmax 3.7.3 Complexity of Total Completion Time Minimization 3.8 Exact Algorithms Problems References 4 Multiprocessor Operations 4.1 Introduction 4.2 Complexity of Short Schedules with Preemptions at Integer Points 4.3 University Timetabling. A Polynomial-Time Algorithm and Conjecture for Two Groups 4.3.1 LP Relaxation with Minimum r 4.3.2 Preliminaries 4.3.3 Outline of the Proof 4.3.4 Columns Absent from d (y ,w) in s 4.4 Pairs of Columns Absent from d (y ,w) in s 4.4.1 The a-, c-, and d-Tightness in s 4.4.2 The Absence of Crossing Jobs in s 4.5 Characterization of d (y ,w) in s 4.5.1 The Overlap 4.6 Integral Optimal Solution to p for jB1 j=ε or jB2 j=ε 4.7 The Projection 4.8 Integral Optimal Solution to p for jBij>ε, i=1,2 4.9 The Proof of the Conjecture 4.10 Complexity of Open Shop Scheduling with Preemptions Allowed at Any Points 4.11 Integer Preemptions: Approximations 4.12 Other Models of Multiprocessor Operations Problems References 5 Concurrent Open Shops 5.1 Introduction 5.2 Complexity of Concurrent Open Shop Scheduling 5.3 Permutation Schedules and Minimization of Maximum Lateness 5.4 2-Approximation Algorithm for O|cncnt|wiCi 5.4.1 The Algorithm 5.4.2 The Proof 5.4.3 An Example 5.5 Hardness of Approximation 5.5.1 O|cncnt|Ci 5.5.2 O|cncnt|Ti, and O|cncnt|Ui 5.6 Fixed Number of Machines and Special Cases 5.7 Conflict Graphs and the Classification of Open Shops Problems References 6 Open Shop Scheduling with Simultaneity Constraints 6.1 Open Shop with Simultaneity Constraints 6.2 Wireless Networking with Primary Interference 6.3 Scheduling Links to Satisfy Link Demand and Related Problems 6.4 Relationship with Edge Coloring 6.5 Complexity of Match and K-Match for General Graphs 6.6 GOLoP Graphs 6.6.1 Characterization of OLoP Graphs; GOLoP Graphs 6.6.2 K-Match for GOLoP Graphs 6.6.3 Match for GOLoP Graphs 6.6.4 Find-K-Match for GOLoP Graphs 6.7 An Upper Bound on the Schedule Length 6.7.1 OLoP Graphs 6.7.2 GOLoP Graphs 6.7.3 Minimizing the Schedule Length 6.8 Conclusions References 7 Proportionate and Ordered Open Shops 7.1 Introduction 7.2 Job-Proportionate Open Shops 7.2.1 Three-Machine Job-Proportionate Open Shop: Complexity and Approximation 7.3 Machine-Proportionate Open Shops 7.3.1 The Job-Proportionate and Machine-Proportionate Open Shops Are Equivalent for Makespan 7.3.2 The n≥m Case Is Easy 7.3.3 The n