Presents strategies with reachability graph analysis for optimizing resource allocation systems
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 flexible routings.
Table of Contents:
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.3 Informed Heuristic Search 35
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.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.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.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.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.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
About the Author :
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).
