Supervisory Control and Scheduling of Resource Allocation Systems
Description
Supervisory Control and Scheduling of Resource Allocation Systems offers an important guide to Petri net (PN) models and methods for supervisory control and system scheduling of resource allocation systems (RASs). Resource allocation systems are common in automated manufacturing systems, project management systems, cloud data centers, and software engineering systems. The authors--two experts on the topic--present a definition, techniques, models, and state-of-the art applications of supervisory control and scheduling problems.
The book introduces the basic concepts and research background on resource allocation systems and Petri nets. The authors then focus on the deadlock-free supervisor synthesis for RASs using Petri nets. The book also investigates the heuristic scheduling of RASs based on timed Petri nets. Conclusions and open problems are provided in the last section of the book.
This important book:
* Includes multiple methods for supervisory control and scheduling with reachability graphs, and provides illustrative examples
* Reveals how to accelerate the supervisory controller design and system scheduling of RASs based on PN reachability graphs, with optimal or near-optimal results
* Highlights both solution quality and computational speed in RAS deadlock handling and system scheduling
Written for researchers, engineers, scientists, and professionals in system planning and control, engineering, operation, and management, Supervisory Control and Scheduling of Resource Allocation Systems provides an essential guide to the supervisory control and scheduling of resource allocation systems (RASs) using Petri net reachability graphs, which allow for multiple resource acquisitions and exible routings.
More details
Other editions
Additional editions
Persons
BO HUANG, PHD, is a Full Professor with the School of Computer Science and Engineering at Nanjing University of Science and Technology (NUST).
MENGCHU ZHOU, PHD, is a Distinguished Professor of Electrical and Computer Engineering and the Director of Discrete-Event Systems Laboratory at the New Jersey Institute of Technology (NJIT).
Content
Preface xi
Acknowledgments xvii
Glossary xix
Acronyms xxiii
About the Authors xxv
Part I Resource Allocation Systems and Petri Nets 1
1 Introduction 3
1.1 Resource Allocation Systems 3
1.2 Supervisory Control and Scheduling with Petri Nets 7
1.3 Summary 9
1.4 Bibliographical Notes 9
2 Preliminaries 11
2.1 Introduction 11
2.2 Petri Nets 12
2.2.1 Basic Concepts 12
2.2.2 Modeling Power of Petri Nets 16
2.2.2.1 Sequential Execution 16
2.2.2.2 Concurrency (Parallelism) 17
2.2.2.3 Synchronization 17
2.2.2.4 Conflict (choice) 17
2.2.2.5 Merging 17
2.2.2.6 Mutual Exclusion 18
2.2.3 Behavioral Properties of Petri Nets 18
2.2.3.1 Boundedness and Safeness 18
2.2.3.2 Liveness and Deadlock 19
2.2.3.3 Reversibility 19
2.2.3.4 Conservativeness 19
2.2.4 Subclasses of Petri Nets 20
2.2.4.1 Ordinary Nets and Generalized Nets 20
2.2.4.2 Pure Petri Nets 20
2.2.4.3 State Machines 21
2.2.4.4 Marked Graphs 22
2.2.4.5 Free-choice Nets 22
2.2.4.6 Extended Free-choice Nets 22
2.2.4.7 Asymmetric Choice Nets 22
2.2.5 Petri Nets for Resource Allocation Systems 22
2.2.5.1 PC2R 23
2.2.5.2 S*PR 24
2.2.5.3 S5PR 25
2.2.5.4 S4PR, S4R, S3 PGR2 and WS3 PSR 25
2.2.5.5 S3PR 26
2.2.5.6 ES3PR and S3PMR 26
2.2.5.7 LS3PR 27
2.2.5.8 ELS3PR 27
2.2.5.9 GLS3PR 28
2.2.6 Structural Analysis 28
2.2.7 Reachability Graph Analysis 30
2.2.7.1 Supervisory Control 30
2.2.7.2 System Scheduling 31
2.2.8 Petri Net Analysis Tools 32
2.3 Informed Heuristic Search 35
2.3.1 Basic Concepts of Heuristic A* Search 35
2.3.2 Properties of the A* Search 36
2.3.2.1 Completeness 36
2.3.2.2 Admissible Heuristics 36
2.3.2.3 Monotone (Consistent) Heuristics 36
2.3.2.4 More Informed Heuristics 36
2.4 Bibliographical Notes 37
Part II Supervisory Control 39
3 Behaviorally Maximal and Structurally Minimal Supervisor 41
3.1 Introduction 41
3.2 Petri Nets for Supervisory Synthesis 43
3.3 Optimal and Minimal Supervisory Synthesis 45
3.3.1 Reachability Graph Analysis 45
3.3.2 Supervisor Computation with Place Invariants 47
3.3.3 Optimal Supervisor Synthesis and Vector Covering Method 47
3.3.4 Optimal Supervisor with Fewest Monitors 49
3.3.5 Deadlock Prevention Policy 50
3.4 An Illustrative Example 52
3.5 Concluding Remarks 54
3.6 Bibliographical Notes 55
4 Supervisor Design with Fewer Places 57
4.1 Introduction 57
4.2 Critical and Free Activity Places 59
4.3 Properties of DP-Nets 62
4.4 Supervisor Design with Critical Activity Places 66
4.5 An Illustrative Example 70
4.6 Concluding Remarks 72
4.7 Bibliographical Notes 73
5 Redundant Constraint Elimination 75
5.1 Introduction 75
5.2 Minimal-Number-of-Monitors Problem 77
5.3 Elimination of Redundant Constraints 78
5.3.1 Redundant Reachability Constraints 78
5.3.2 Linear Program Method 79
5.3.3 Non-Linear Program Method 82
5.3.4 Supervisor Synthesis with Redundancy Elimination 84
5.4 Illustrative Examples 85
5.5 Concluding Remarks 91
5.6 Bibliographical Notes 91
6 Fast Iterative Supervisor Design 93
6.1 Introduction 93
6.2 Optimal Supervisor of a DP-net 94
6.3 Fast Synthesis of Optimal and Simple Supervisors 95
6.3.1 Multiobjective Supervisory Control 96
6.3.2 Design of an Optimal Control Place 97
6.3.3 Identification of Redundant Constraints 99
6.3.4 Iterative Deadlock Prevention 102
6.4 Illustrative Examples 107
6.5 Concluding Remarks 115
6.6 Bibliographical Notes 115
7 Supervisor Synthesis with Uncontrollable and Unobservable Transitions 117
7.1 Introduction 117
7.2 Supervisor Synthesis with Uncontrollability and Unobservability 119
7.2.1 DP-Nets with Uncontrollable and/or Unobservable Transitions 119
7.2.2 Admissible Markings and First-Met Inadmissible Markings 120
7.2.3 Design of an Admissible Monitor 123
7.2.4 Admissible and Structure-Minimal Supervisor Synthesis 125
7.3 Deadlock Prevention Policy 127
7.4 Illustrative Experiments 132
7.5 Concluding Remarks 136
7.6 Bibliographical Notes 136
Part III Heuristic Scheduling 137
8 Informed Heuristic Search in Reachability Graph 139
8.1 Introduction 139
8.2 System Scheduling with Place-Timed Petri Nets 140
8.2.1 Place-Timed Petri Nets 140
8.2.2 Conversion from an Untimed Petri Net 141
8.2.3 Synthesis of a Place-Timed Petri Net 143
8.2.3.1 Top-down Method 144
8.2.3.2 Bottom-up Method 145
8.3 State Evolution of Place-Timed Nets 145
8.4 A* Search on a Reachability Graph 152
8.5 A* Search with State Check 153
8.6 An Illustrative Example 155
8.7 Concluding Remarks 156
8.8 Bibliographical Notes 156
9 Controllable Heuristic Search 157
9.1 Introduction 157
9.2 Alternative Routes with Different Lengths 159
9.3 An Admissible Heuristic for SC-nets 160
9.4 A Controllable Heuristic Search 163
9.5 Randomly Generated Examples 166
9.6 Another Controllable Heuristic Search 168
9.6.1 A* Search and Depth-First Search 168
9.6.2 Controllable Hybrid Heuristic Search 171
9.7 Illustrative Results 176
9.8 Concluding Remarks 178
9.9 Bibliographical Notes 179
10 Hybrid Heuristic Search 181
10.1 Introduction 181
10.2 A*-BT Combinations 182
10.3 Illustrative Examples 187
10.4 Concluding Remarks 190
10.5 Bibliographical Notes 191
11 A* Search with More Informed Heuristics Functions 193
11.1 Introduction 193
11.2 More Informed Heuristics in A* Search 194
11.3 Combination of Admissible and Inadmissible Heuristics 195
11.4 Illustrative Examples 197
11.5 Concluding Remarks 203
11.6 Bibliographical Notes 204
12 Symbolic Heuristic Search 205
12.1 Introduction 205
12.2 Boolean Algebra and Binary Decision Diagram 206
12.3 Symbolic Evolution of Place-Timed Petri Nets 207
12.4 Symbolic Heuristic Search 213
12.5 Illustrative Examples 218
12.6 Concluding Remarks 224
12.7 Bibliographical Notes 226
13 Open Problems 227
13.1 Structural Analysis of Generalized Nets 227
13.2 Robust Supervisor Synthesis with Unreliable Resources 227
13.3 Alleviation of the State Explosion Problem 228
13.4 Optimization of Symbolic Variable Ordering 229
13.5 Multiobjective Scheduling 230
13.6 Anytime Heuristic Scheduling 230
13.7 Parallel Heuristic Search 231
13.8 Bidirectional Heuristic Search 232
13.9 Computing and Scheduling with GPUs 232
References 235
Index 253
Preface
This book covers the supervisory control and scheduling of resource allocation systems (RASs) based on the reachability graphs of Petri nets that allow for multiple resource acquisitions and flexible routings. In such systems, resources (such as machines, robots, drives, and data) are shared among concurrently running processes (such as parts, vehicles, and programs). A successful system should correctly allocate these resources without deadlocks and at the same time achieve some desired objectives such as maximizing makespan and minimizing tardiness.
First, deadlocks in such systems can lead to an unnecessary economic cost and even catastrophic results in practical systems. In the literature, Petri nets (PNs) are widely used to describe and control RASs since PNs can naturally and compactly model the structural and behavioral properties of RASs and then analyze the performances of the models. To obtain deadlock-free supervisors for PN models of RASs, a reachability graph analysis method, which synthesizes a PN supervisor by using an invariant-based control approach, is commonly used. This method can be applied to many kinds of PN models and allows designers to obtain a deadlock-free supervisor with maximally or highly permissive behavior, but its computational burden is always heavy and of exponential complexity. In the first half of this book, the reachability graph analysis method for deadlock prevention of RASs are accelerated by using different strategies.
Second, although RASs allow high productivity, a great number of choices for resources and processing routes make it difficult to correctly allocate different resources to different processes and to efficiently schedule the sequence of operations with the highest efficiency. In order to address these problems, an A* search with an admissible heuristic function that only needs to explore a partial reachability graph to obtain an optimal schedule can be used. Although the generation of the whole reachability graph is avoided, the number of the explored markings by the algorithm still grows exponentially with problem size and/or initial markings, which makes the method only applicable to small systems. However, result quality and computational efficiency are two important factors in the scheduling of RASs. In the second half of this book, different acceleration strategies for the A* search within reachability graphs, such as hybrid searches, more informed heuristics, and symbolic representations and manipulations, are presented in order to speed up the search process for optimal or suboptimal schedules.
A lot of work has been done by researchers and engineers in both the deadlock handling and system scheduling of RASs. This book focuses on the solutions' quality and computational speed in RAS deadlock handling and system scheduling based on Petri nets and their reachability graphs. If optimal or suboptimal solutions can be obtained with fewer computational burdens, more systems can be handled by the deadlock prevention and system scheduling methods. Therefore, this book aims to present the state-of-the-art developments in the acceleration of the supervisory control and scheduling of RASs based on PNs' reachability graphs. The outline of this book is as described below:
The book is divided into three parts. Part I includes Chapters 1 and 2 that introduce the basic concepts and research background of RASs and Petri nets. Part II consists of Chapters 3-7 focusing on the deadlock-free supervisor synthesis for RASs by using Petri nets. Part III contains Chapters 8-12 and investigates the heuristic scheduling of RASs based on timed Petri nets.
Chapter 1 introduces the features of RASs and briefly reviews different approaches on the supervisory control and system scheduling of such systems. Then, the advantages and disadvantages of these approaches are analyzed.
Chapter 2 first recalls the fundamentals of Petri nets, including their basic concepts, modeling power, behavioral properties, and analysis tools. Next, some typical subclasses of Petri nets for RASs and their relationships are introduced. After that, structural analysis methods and reachability graph analysis methods based on PNs for RASs are discussed. Finally, the procedures and properties of the heuristic A* search within the PNs' reachability graphs are presented. The basic concepts given in this chapter are used throughout the book.
Chapter 3 focuses on the applications of the theory of regions in the synthesis of optimal and deadlock-free supervisors with the fewest monitors for RASs based on PN's reachability graphs. The performance of such a deadlock prevention policy can be evaluated by three criteria: behavioral permissiveness, structural complexity, and computational complexity. This chapter presents a supervisor synthesis method that has the following advantages: its controlled nets are behaviorally maximal and the added supervisors are structurally minimal in terms of added monitors. However, its computational burden is usually heavy.
The existing reachability graph analysis methods for deadlock prevention consider all activity places in the design of place invariants that prevent the system from entering the deadlock zone in the graph. However, some activity places may be useless for such a method and they may result in many redundant constraints in the supervisor synthesis process. To handle it, Chapter 4 presents a method to obtain liveness-enforcing and optimal or suboptimal supervisors for RASs based on critical activity places that are a proper subset of activity places. The proof that critical activity places are enough to be considered in the design of place invariants to obtain such supervisors is given. Since the number of places considered in the supervisor synthesis is reduced, the supervisor synthesis process thus becomes simpler.
To reduce the computational burden of the method in Chapter 3, researchers have mainly focused on the revision of the underlying integer linear program (ILP). Instead, Chapter 5 presents another strategy to accelerate the computation by eliminating redundant reachability constraints given in the method. First, a sufficient and necessary condition for a reachability constraint to be redundant is given in the form of an ILP, based on the concept of the feasible region of supervisors. Then, two kinds of redundancy elimination methods are presented: an ILP method and a non-ILP method. Most of the redundant reachability constraints can be eliminated by the presented methods in a short time. Thus, the computational time of the deadlock prevention method is greatly reduced after the elimination, especially for large-scale systems. In addition, the obtained supervisors are still optimal and structurally minimal.
Chapter 6 investigates an acceleration method for solving a multiobjective ILP to obtain an optimal and deadlock-free supervisor with a compressed structure in terms of both control places and added arcs for RASs. Instead of a single big ILP, several smaller ILPs are formulated in an iterative manner and the problem can thus be solved much faster. To further reduce the ILP solution time, the redundancy elimination method is also adopted in the iterative method. The advantages of the presented method are that the supervisor synthesis process is well accelerated without compromising the result's optimality and the obtained supervisor is structurally compressed in terms of both control places and added arcs.
Chapter 7 presents a deadlock prevention method for RASs based on Petri nets with uncontrollable and unobservable transitions. First, the concepts of admissible markings and first-met inadmissible markings are introduced. Next, place invariants are designed to survive all admissible markings and prohibit all first-met inadmissible markings, which keeps the system from reaching deadlock markings, livelock markings, bad markings, and those that can evolve into deadlocks, livelocks, or bad markings via the firings of uncontrollable transitions. Then, an ILP is developed to ensure that the obtained supervisor does not violate the unobservability and the supervisor is structurally minimal in terms of control places and added arcs. The presented method can deal with the PNs in which some crucial transitions are uncontrollable and/or unobservable. The supervisors obtained by the method are admissible. In addition, the condition under which the obtained supervisors are optimal is also given.
Chapter 8 first presents two methods to build place-timed Petri net models for the RAS scheduling, i.e. converting existing Petri nets of RASs in the literature and synthesizing a new one via a top-down or a bottom-up method. Then, the state evolution of such place-timed Petri nets is introduced in detail. Finally, an algorithm that combines the evolution of a place-timed Petri net, an intelligent A* search, and state check rules is presented to schedule RASs.
Chapter 9 provides a good trade-off between the quality of the obtained schedule and the computational burden of the RAS scheduling based on PN's reachability graphs. This chapter presents an admissible heuristic function for the place-timed Petri nets of RASs and two controllable search methods with the heuristic function. The first method does not need to predict the depth of a solution in advance and the quality of the obtained schedule is controllable. The second method combines an A* search with a...
