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 exible routings.

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

Inhalt

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 PC²R 23

2.2.5.2 S*PR 24

2.2.5.3 S⁵PR 25

2.2.5.4 S⁴PR, S⁴R, S³ PGR² and WS³ PSR 25

2.2.5.5 S³PR 26

2.2.5.6 ES³PR and S³PMR 26

2.2.5.7 LS³PR 27

2.2.5.8 ELS³PR 27

2.2.5.9 GLS³PR 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 Elimina...