Supervisory Control and Scheduling of Resource Allocation Systems

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).

• Preface xiAcknowledgments xviiGlossary xixAcronyms xxiiiAbout the Authors xxvPart I Resource Allocation Systems and Petri Nets 11 Introduction 31.1 Resource Allocation Systems 31.2 Supervisory Control and Scheduling with Petri Nets 71.3 Summary 91.4 Bibliographical Notes 92 Preliminaries 112.1 Introduction 112.2 Petri Nets 122.2.1 Basic Concepts 122.2.2 Modeling Power of Petri Nets 162.2.2.1 Sequential Execution 162.2.2.2 Concurrency (Parallelism) 172.2.2.3 Synchronization 172.2.2.4 Conflict (choice) 172.2.2.5 Merging 172.2.2.6 Mutual Exclusion 182.2.3 Behavioral Properties of Petri Nets 182.2.3.1 Boundedness and Safeness 182.2.3.2 Liveness and Deadlock 192.2.3.3 Reversibility 192.2.3.4 Conservativeness 192.2.4 Subclasses of Petri Nets 202.2.4.1 Ordinary Nets and Generalized Nets 202.2.4.2 Pure Petri Nets 202.2.4.3 State Machines 212.2.4.4 Marked Graphs 222.2.4.5 Free-choice Nets 222.2.4.6 Extended Free-choice Nets 222.2.4.7 Asymmetric Choice Nets 222.2.5 Petri Nets for Resource Allocation Systems 222.2.5.1 PC2R 232.2.5.2 S*PR 242.2.5.3 S5PR 252.2.5.4 S4PR, S4R, S3 PGR2 and WS3 PSR 252.2.5.5 S3PR 262.2.5.6 ES3PR and S3PMR 262.2.5.7 LS3PR 272.2.5.8 ELS3PR 272.2.5.9 GLS3PR 282.2.6 Structural Analysis 282.2.7 Reachability Graph Analysis 302.2.7.1 Supervisory Control 302.2.7.2 System Scheduling 312.2.8 Petri Net Analysis Tools 322.3 Informed Heuristic Search 352.3.1 Basic Concepts of Heuristic A* Search 352.3.2 Properties of the A* Search 362.3.2.1 Completeness 362.3.2.2 Admissible Heuristics 362.3.2.3 Monotone (Consistent) Heuristics 362.3.2.4 More Informed Heuristics 362.4 Bibliographical Notes 37Part II Supervisory Control 393 Behaviorally Maximal and Structurally Minimal Supervisor 413.1 Introduction 413.2 Petri Nets for Supervisory Synthesis 433.3 Optimal and Minimal Supervisory Synthesis 453.3.1 Reachability Graph Analysis 453.3.2 Supervisor Computation with Place Invariants 473.3.3 Optimal Supervisor Synthesis and Vector Covering Method 473.3.4 Optimal Supervisor with Fewest Monitors 493.3.5 Deadlock Prevention Policy 503.4 An Illustrative Example 523.5 Concluding Remarks 543.6 Bibliographical Notes 554 Supervisor Design with Fewer Places 574.1 Introduction 574.2 Critical and Free Activity Places 594.3 Properties of DP-Nets 624.4 Supervisor Design with Critical Activity Places 664.5 An Illustrative Example 704.6 Concluding Remarks 724.7 Bibliographical Notes 735 Redundant Constraint Elimination 755.1 Introduction 755.2 Minimal-Number-of-Monitors Problem 775.3 Elimination of Redundant Constraints 785.3.1 Redundant Reachability Constraints 785.3.2 Linear Program Method 795.3.3 Non-Linear Program Method 825.3.4 Supervisor Synthesis with Redundancy Elimination 845.4 Illustrative Examples 855.5 Concluding Remarks 915.6 Bibliographical Notes 916 Fast Iterative Supervisor Design 936.1 Introduction 936.2 Optimal Supervisor of a DP-net 946.3 Fast Synthesis of Optimal and Simple Supervisors 956.3.1 Multiobjective Supervisory Control 966.3.2 Design of an Optimal Control Place 976.3.3 Identification of Redundant Constraints 996.3.4 Iterative Deadlock Prevention 1026.4 Illustrative Examples 1076.5 Concluding Remarks 1156.6 Bibliographical Notes 1157 Supervisor Synthesis with Uncontrollable and Unobservable Transitions 1177.1 Introduction 1177.2 Supervisor Synthesis with Uncontrollability and Unobservability 1197.2.1 DP-Nets with Uncontrollable and/or Unobservable Transitions 1197.2.2 Admissible Markings and First-Met Inadmissible Markings 1207.2.3 Design of an Admissible Monitor 1237.2.4 Admissible and Structure-Minimal Supervisor Synthesis 1257.3 Deadlock Prevention Policy 1277.4 Illustrative Experiments 1327.5 Concluding Remarks 1367.6 Bibliographical Notes 136Part III Heuristic Scheduling 1378 Informed Heuristic Search in Reachability Graph 1398.1 Introduction 1398.2 System Scheduling with Place-Timed Petri Nets 1408.2.1 Place-Timed Petri Nets 1408.2.2 Conversion from an Untimed Petri Net 1418.2.3 Synthesis of a Place-Timed Petri Net 1438.2.3.1 Top-down Method 1448.2.3.2 Bottom-up Method 1458.3 State Evolution of Place-Timed Nets 1458.4 A* Search on a Reachability Graph 1528.5 A* Search with State Check 1538.6 An Illustrative Example 1558.7 Concluding Remarks 1568.8 Bibliographical Notes 1569 Controllable Heuristic Search 1579.1 Introduction 1579.2 Alternative Routes with Different Lengths 1599.3 An Admissible Heuristic for SC-nets 1609.4 A Controllable Heuristic Search 1639.5 Randomly Generated Examples 1669.6 Another Controllable Heuristic Search 1689.6.1 A* Search and Depth-First Search 1689.6.2 Controllable Hybrid Heuristic Search 1719.7 Illustrative Results 1769.8 Concluding Remarks 1789.9 Bibliographical Notes 17910 Hybrid Heuristic Search 18110.1 Introduction 18110.2 A*-BT Combinations 18210.3 Illustrative Examples 18710.4 Concluding Remarks 19010.5 Bibliographical Notes 19111 A* Search with More Informed Heuristics Functions 19311.1 Introduction 19311.2 More Informed Heuristics in A* Search 19411.3 Combination of Admissible and Inadmissible Heuristics 19511.4 Illustrative Examples 19711.5 Concluding Remarks 20311.6 Bibliographical Notes 20412 Symbolic Heuristic Search 20512.1 Introduction 20512.2 Boolean Algebra and Binary Decision Diagram 20612.3 Symbolic Evolution of Place-Timed Petri Nets 20712.4 Symbolic Heuristic Search 21312.5 Illustrative Examples 21812.6 Concluding Remarks 22412.7 Bibliographical Notes 22613 Open Problems 22713.1 Structural Analysis of Generalized Nets 22713.2 Robust Supervisor Synthesis with Unreliable Resources 22713.3 Alleviation of the State Explosion Problem 22813.4 Optimization of Symbolic Variable Ordering 22913.5 Multiobjective Scheduling 23013.6 Anytime Heuristic Scheduling 23013.7 Parallel Heuristic Search 23113.8 Bidirectional Heuristic Search 23213.9 Computing and Scheduling with GPUs 232References 235Index 253