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

✍ Scribed by Wieslaw Kubiak

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 290
• Series: International Series in Operations Research & Management Science
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

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<m Case
7.4 Ordered Open Shops
7.5 Maximal Machine
7.6 Dominated Machine
7.7 Bottleneck Machine
7.8 Total Completion Time for Machine-Proportionate Open Shops
7.9 Algorithm for Two Machines
7.9.1 Characterization of Optimal Schedules
7.9.2 The Algorithm
Problems
References
8 Multiprocessor Open Shops
8.1 Preemptive Open Shops with Multiprocessors
8.1.1 Single-Operation Machines: McNaughton Meets König
8.1.2 Multiple-Operation Machines
8.2 Non-Preemptive Open Shops with Parallel Machines
8.3 Applications
References
9 Compact Scheduling of Open Shops
9.1 Compact Schedules
9.1.1 Interval Edge Coloring
9.2 Complexity of Short Compact Schedules
9.2.1 Test for =3
9.2.2 Makespan Minimization for Compact Open Shops with ≤3
9.2.3 Test for =4
9.2.4 Makespan Minimization for Compact Open Shops with ≤4
9.2.5 Test for ≥5
9.3 Biregular Open Shops
9.3.1 (2, )-Biregular Open Shops
9.3.2 (3, 4)-Biregular Open Shops
9.3.3 (a,b)-Biregular Open Shops
9.4 Simple Graphs or Multigraphs
9.5 Deficiency and Spans
9.5.1 Spans
9.5.2 Computation of Deficiency
9.6 Cyclic Compact Open Shop Scheduling
9.6.1 Makespan Minimization for Cyclic Compact Open Shops with =3
9.6.2 Makespan Minimization for Cyclic Compact Open Shops with =4
9.6.3 Makespan Minimization for Other Cyclic Compact Open Shops
Problems
References
10 No-Wait Open Shop Scheduling
10.1 No-Wait Open Shop Schedules Can Be Preemptive
10.1.1 Strong NP-Hardness for Two Machines
10.2 Short No-Wait Schedules: Test for Cmax≤3
10.3 Short No-Wait Schedules: Test for Cmax≤4
10.4 Short No-Wait Schedules: Cmax≤5
10.5 Short No-Wait Schedules: Cmax≤6
10.6 No-Wait and Cyclic Compact Open Shop Scheduling
10.7 Exact Algorithms and Approximations
Problems
References
11 Applications of Preemptive Open Shop Scheduling
11.1 Introduction
11.2 Satellite Communication
11.3 Reconfigurable Data Centers
11.4 Crossbar Switches
11.5 Multimessage Unicasting and Multicasting
11.6 Scheduling and Wavelength Assignment problem
11.7 Scheduling Theory
11.8 Data Migration and File Transfer Scheduling
Problems
References
12 Two-Machine Open Shop Scheduling with Time Lags
12.1 Makespan Minimization
12.2 Total Completion Time Minimization
References
Index