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.3 Informed Heuristic Search 352.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.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.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.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.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.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