Supervisory Control and Scheduling of Resource Allocation Systems E-Book

Bo Huang

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: IEEE Series on Systems Science and Engineering
• Sprache: Englisch

Seitenzahl: 403

Veröffentlichungsjahr: 2020

Beschreibung

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.

Leseprobe

Table of Contents

Cover

Preface

Acknowledgments

Glossary

Acronyms

About the Authors

Part I: Resource Allocation Systems and Petri Nets

1 Introduction

1.1 Resource Allocation Systems

1.2 Supervisory Control and Scheduling with Petri Nets

1.3 Summary

1.4 Bibliographical Notes

2 Preliminaries

2.1 Introduction

2.2 Petri Nets

2.3 Informed Heuristic Search

2.4 Bibliographical Notes

Part II: Supervisory Control

3 Behaviorally Maximal and Structurally Minimal Supervisor

3.1 Introduction

3.2 Petri Nets for Supervisory Synthesis

3.3 Optimal and Minimal Supervisory Synthesis

3.4 An Illustrative Example

3.5 Concluding Remarks

3.6 Bibliographical Notes

4 Supervisor Design with Fewer Places

4.1 Introduction

4.2 Critical and Free Activity Places

4.3 Properties of DP‐Nets

4.4 Supervisor Design with Critical Activity Places

4.5 An Illustrative Example

4.6 Concluding Remarks

4.7 Bibliographical Notes

5 Redundant Constraint Elimination

5.1 Introduction

5.2 Minimal‐Number‐of‐Monitors Problem

5.3 Elimination of Redundant Constraints

5.4 Illustrative Examples

5.5 Concluding Remarks

5.6 Bibliographical Notes

6 Fast Iterative Supervisor Design

6.1 Introduction

6.2 Optimal Supervisor of a DP‐net

6.3 Fast Synthesis of Optimal and Simple Supervisors

6.4 Illustrative Examples

6.5 Concluding Remarks

6.6 Bibliographical Notes

7 Supervisor Synthesis with Uncontrollable and Unobservable Transitions

7.1 Introduction

7.2 Supervisor Synthesis with Uncontrollability and Unobservability

7.3 Deadlock Prevention Policy

7.4 Illustrative Experiments

7.5 Concluding Remarks

7.6 Bibliographical Notes

Part III: Heuristic Scheduling

8 Informed Heuristic Search in Reachability Graph

8.1 Introduction

8.2 System Scheduling with Place‐Timed Petri Nets

8.3 State Evolution of Place‐Timed Nets

8.4 A* Search on a Reachability Graph

8.5 A* Search with State Check

8.6 An Illustrative Example

8.7 Concluding Remarks

8.8 Bibliographical Notes

9 Controllable Heuristic Search

9.1 Introduction

9.2 Alternative Routes with Different Lengths

9.3 An Admissible Heuristic for SC‐nets

9.4 A Controllable Heuristic Search

9.5 Randomly Generated Examples

9.6 Another Controllable Heuristic Search

9.7 Illustrative Results

9.8 Concluding Remarks

9.9 Bibliographical Notes

10 Hybrid Heuristic Search

10.1 Introduction

10.2 A*‐BT Combinations

10.3 Illustrative Examples

10.4 Concluding Remarks

10.5 Bibliographical Notes

11 A* Search with More Informed Heuristics Functions

11.1 Introduction

11.2 More Informed Heuristics in A* Search

11.3 Combination of Admissible and Inadmissible Heuristics

11.4 Illustrative Examples

11.5 Concluding Remarks

11.6 Bibliographical Notes

12 Symbolic Heuristic Search

12.1 Introduction

12.2 Boolean Algebra and Binary Decision Diagram

12.3 Symbolic Evolution of Place‐Timed Petri Nets

12.4 Symbolic Heuristic Search

12.5 Illustrative Examples

12.6 Concluding Remarks

12.7 Bibliographical Notes

13 Open Problems

13.1 Structural Analysis of Generalized Nets

13.2 Robust Supervisor Synthesis with Unreliable Resources

13.3 Alleviation of the State Explosion Problem

13.4 Optimization of Symbolic Variable Ordering

13.5 Multiobjective Scheduling

13.6 Anytime Heuristic Scheduling

13.7 Parallel Heuristic Search

13.8 Bidirectional Heuristic Search

13.9 Computing and Scheduling with GPUs

References

Index

IEEE PRESS SERIES ON SYSTEMS SCIENCE AND ENGINEERING

End User License Agreement

List of Tables

Chapter 3

Table 3.1 Supervisor obtained for the DP‐net in Figure 3.2.

Chapter 4

Table 4.1 Descriptions of a system model.

Chapter 5

Table 5.1 Numbers of constraints and variables in different ILPs.

Table 5.2 Results for the model in Figure 5.1.

Table 5.3 Results for the model in Figure 5.2.

Table 5.4 Performance comparisons for the model in Figure 5.1.

Table 5.5 Performance comparisons for the model in Figure 5.2.

Table 5.6 Solutions of parameterized problem instances.

Chapter 6

Table 6.1 The obtained supervisor for the net shown in Figure 6.1 (

)

Table 6.2 Added places and arcs for the net shown in Figure 6.4. (

,

)

Table 6.3 Performance comparisons for the net shown in Figure 6.4.

Table 6.4 Added places and arcs for the net shown in Figure 6.5. (

,

)

Table 6.5 Performance comparisons for the net shown in Figure 6.5.

Chapter 7

Table 7.1 Supervisor for the net in Figure 7.4 with

and

.

Table 7.2 Supervisor for the net in Figure 7.5 with

and

.

Table 7.3 Supervisor for the net in Figure 7.5 with

and

.

Chapter 8

Table 8.1 The obtained schedule for the SC‐net on the right of Figure 8.2 wit...

Chapter 9

Table 9.1 Job requirements of the example system.

Table 9.2 Scheduling results of the example system.

Table 9.3 Job requirements of the example system.

Table 9.4 Scheduling results of the example system.

Table 9.5 Scheduling results for the lot size (3, 3, 3, 3) by using A*‐DF.

Table 9.6 Scheduling results for the lot size (5, 5, 5, 5) by using A*‐DF.

Table 9.7 Scheduling results for the lot size (10, 10, 10, 10) by using A*‐DF...

Table 9.8 Operation times of activity places.

Table 9.9 Scheduling results of the SC‐net in Figure 9.4 (A*:

,

,

; DF:

,

Chapter 10

Table 10.1 Scheduling results of the SC‐net in Figure 9.3 with the lot size (5, ...

Table 10.2 Scheduling results of the SC‐net in Figure 9.3 with the lot size (8, ...

Table 10.3 Scheduling results of the SC‐net in Figure 9.3 with the lot size (...

Chapter 11

Table 11.1 Performance comparisons for the system of Xiong and Zhou (1998) wi...

Table 11.2 Performance comparisons for the system of Xiong and Zhou (1998) with ...

Table 11.3 Performance comparisons for the system of Xiong and Zhou (1998) with ...

Table 11.4 Performance comparisons for the system of Xiong and Zhou (1998) with ...

Table 11.5 Performance comparisons for the system of Xiong and Zhou (1998) wi...

Table 11.6 Performance comparisons for small‐scale problems (

=

=

=

=

Table 11.7 Performance comparisons for middle‐scale problems

(

=

= 4,

=...

Table 11.8 Performance comparisons for middle‐scale problems

(

=

= 6,

=...

Chapter 12

Table 12.1 Operation times of Example 1.

Table 12.2 Scheduling results for Example 1.

Table 12.3 Operation times of Example 2.

Table 12.4 Scheduling results for Example 2.

Table 12.5 Operation times of Example 3.

Table 12.6 The obtained optimal schedule for Example 3 (makespan = 36).

List of Illustrations

Chapter 2

Figure 2.1 A Petri net example.

Figure 2.2 The reachability graph of the Petri net in Figure 2.1.

Figure 2.3 Elementary structures of Petri nets: (a) sequential execution; (b...

Figure 2.4 Venn diagram of different subclasses of Petri nets.

Figure 2.5 Subclasses of Petri nets. (a) State machine (b) marked graph (c) ...

Figure 2.6 Relations among different classes of PNs for RASs.

Figure 2.7 A PC

2

R net for a postmodern dining philosophers problem.

Figure 2.8 An S

3

PR net for an FMS.

Figure 2.9 Some processing subnets. (a) and (b) are subnets of LS

3

PR; (c) is...

Figure 2.10 Petri net model of a resource allocation system.

Figure 2.11 Reachability graph of the Petri net in Figure 2.10.

Chapter 3

Figure 3.1 (a) A flexible manufacturing system; (b) its processing sequences...

Figure 3.2 DP‐net of the example RAS.

Figure 3.3 Reachability graph of the DP‐net in Figure 3.2.

Figure 3.4 Controlled net of the DP‐net in Figure 3.2.

Chapter 4

Figure 4.1 Set relations between

,

, and

.

Figure 4.2 DP‐net of an RAS.

Figure 4.3 Supervisor for the DP‐net shown in Figure 4.2.

Chapter 5

Figure 5.1 Petri net model of a flexible manufacturing system.

Figure 5.2 Petri net model of another manufacturing system.

Chapter 6

Figure 6.1 DP‐net of an RAS.

Figure 6.2 Reachability graph of the DP‐net in Figure 6.1.

Figure 6.3 Controlled net with a supervisor for the model in Figure 6.1.

Figure 6.4 Petri net model of an AMS (Uzam, 2002; Li

et al

., 2008

a

).

Figure 6.5 Petri net model of another AMS (Ezpeleta

et al

., 1995; Chen

et al

Chapter 7

Figure 7.1 A DP‐net with

and

.

Figure 7.2 Reachability graph of the DP‐net in Figure 7.1 with

and

.

Figure 7.3 Controlled net for the model in Figure 7.1.

Figure 7.4 DP‐net of a flexible manufacturing system (Chen & Li, 2011; Ghaff...

Figure 7.5 DP‐net of another manufacturing system (Li

et al

., 2008

a

; Uzam, 2...

Chapter 8

Figure 8.1 (a) A flexible manufacturing system; (b) its process sequences.

Figure 8.2 Conversion of an S

3

PR net into an SC‐net.

Figure 8.3 (a) Processing of P

1

(initial merges); (b) processing of P

2

(init...

Figure 8.4 Three states with the same marking but different tokens' remainin...

Chapter 9

Figure 9.1 An SC‐net of an automated manufacturing system.

Figure 9.2 Performances of IDWA and DWA, averaged over 50 random SC‐nets....

Figure 9.3 The SC‐net of the example system.

Figure 9.4 SC‐net of a more complex system.

Chapter 10

Figure 10.1 (a) The BF‐BT algorithm; (b) The BT‐BF algorithm.

Figure 10.2 The algorithm performing A* locally and BT globally.

Figure 10.3

versus

for the SC‐net with the lot size

.

Figure 10.4

versus

for the SC‐net with the lot size

.

Figure 10.5

versus

for the SC‐net with the lot size

.

Figure 10.6 (a) A buffer with a finite size; (b) an operation with an altern...

Figure 10.7 Performances of Algorithm 10.1 for random problems.

Chapter 12

Figure 12.1 An ordered BDD representing a set of markings.

Figure 12.2 A reduced and ordered BDD representing the same set of markings....

Figure 12.3 SC‐net of Example 1.

Figure 12.4 SC‐net of Example 2.

Figure 12.5 SC‐net of Example 3.

Guide

Cover

Table of Contents

Begin Reading

Pages

ii

iii

iv

xi

xii

xiii

xiv

xv

xvi

xvii

xviii

xix

xx

xxi

xxii

xxiii

xxiv

xxv

1

3

4

5

6

7

8

9

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

39

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

181

182

183

184

185

186

187

188

189

190

191

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

b1

b2

257

IEEE Press

445 Hoes Lane

Piscataway, NJ 08854

IEEE Press Editorial Board

Ekram Hossain, Editor in Chief

Jón Atli Benediktsson  David Alan Grier Elya  B. Joffe

Xiaoou Li        Peter Lian       Andreas Molisch

Saeid Nahavandi     Jeffrey Reed      Diomidis Spinellis

Sarah Spurgeon      Ahmet Murat Tekalp

Supervisory Control and Scheduling of Resource Allocation Systems

Reachability Graph Perspective

Bo Huang

Nanjing University of Science and Technology, Nanjing, China

MengChu Zhou

New Jersey Institute of Technology, Newark, NJ, USA

Copyright © 2020 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone].

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herin may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department with the U.S. at 877-762-2974, outside the U.S. at 317-572-3993 or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic format.

Library of Congress Cataloging-in-Publication Data

Names: Huang, Bo, 1980- editor. | Zhou, MengChu, editor.Title: Supervisory control and scheduling of resource allocation systems: reachability graph perspective / [edited by] Bo Huang, Nanjing University of Science and Technology, Nanjing, China, Mengchu Zhou New Jersey Institute of Technology, Newark, NJ, USA.Description: First edition. | Hoboken, New Jersey: John Wiley & Sons, Inc., [2020] | Series: IEEE Press series on systems science and engineering | Includes bibliographical references and index.Identifiers: LCCN 2020016184 (print) | LCCN 2020016185 (ebook) | ISBN 9781119619680 (cloth) | ISBN 9781119619697 (adobe pdf) | ISBN 9781119619703 (epub)Subjects: LCSH: Resource allocation–Decision making. | Management information systems.Classification: LCC T57.77 .S87 2020 (print) | LCC T57.77 (ebook) | DDC 658.4/034–dc23LC record available at https://lccn.loc.gov/2020016184LC ebook record available at https://lccn.loc.gov/2020016185

Cover Design: WileyCover Image: © Mark Agnor/Shutterstock

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 depth‐first strategy within the PN’s reachability graphs to schedule RASs. The search scheme can invoke quicker termination conditions and the quality of the obtained result is controllable.

Chapter 10 presents a hybrid scheduling method that combines two search schemes for RASs based on place‐timed PNs. The method performs an A* algorithm locally and a backtracking strategy globally within the PNs’ reachability graphs. It is proven to be more efficient than other existing methods that also combine the A* algorithm and the backtracking strategy.

Chapter 11 deals with the method that can simultaneously use admissible and inadmissible heuristic functions in an A* search within the reachability graphs of PNs for RASs. It also proves that the combinational heuristic function is still admissible and more informed than any of its constituents.

Chapter 12 investigates a symbolic A* search to compactly represent and efficiently schedule RASs based on reachability graphs. First, the methods to functionally represent, evolve, and schedule the place‐timed PNs by using both binary decision diagrams and an A* algorithm are presented. To accelerate the search process, an admissible heuristic function suitable for the symbolic method and its efficient functional implementation are given. When compared with explicit‐state A* methods, the presented symbolic A* approach can compactly represent large sets of states and efficiently compute on such sets to fast find an optimal schedule.

Chapter 13 provides several interesting open problems and future research topics in the development of deadlock prevention and system scheduling methods for RASs based on Petri nets.

Attached to the end of the book is a reference bibliography. A glossary and a list of acronyms can be found at the beginning of the book and a complete index is provided at the end of the book. The implementation codes and experimental files of the methods presented in this book are also given for the reader’s examination and reference. For the codes and input data of the methods presented in Part II, please refer to http://github.com/huang-njust/supervisor. The programs and experimental data of the methods in Part III except Chapter 12 can be seen in http://github.com/huang-njust/schedule. The codes and input data of the method presented in Chapter 12 are given in http://github.com/huang-njust/bdd.

This book can be used as a reference for university classes aimed at modeling, analysis, control, and scheduling systems based on discrete event models. The book can provide useful information for control engineers and industrial engineers who are interested in developing deadlock prevention and schedule optimization methods for RASs. It may also be of interest to the discrete event systems community, providing a bridge for supervisory control and system scheduling applications. The book serves researchers, engineers, scientists, and professionals who work in system modeling, planning, control, engineering, and management fields as well as faculty, staff, and graduate students who are interested in Petri net, scheduling, and control of discrete event dynamic systems.

Bo Huang and MengChu Zhou

Nanjing, China

Acknowledgments

We cannot acknowledge all the people who have made suggestions and given help, but we would like to sincerely note the help from Professors Yufeng Chen, Macau University of Science and Technology (Macau, China), Yan Qiao, Macau University of Science and Technology (Macau, China), Yisheng Huang, Taiwan ILan University (Taiwan, China), Zhiwu Li, Macau University of Science and Technology (Macau, China), Naiqi Wu, Macau University of Science and Technology (Macau, China), Maria Pia Fanti, Polytechnic University of Bari (Italy), Shouguang Wang, Zhejiang Gongshang University (China), Dmitry Zaitsev, International Humanitarian University (Ukraine), Jiliang Luo, Huaqiao University (China), Jun Li, Southeast University (China), Qinghua Zhu, Guandong University of Technology (China), Chunrong Pan, Jiangxi University of Science and Technology (China), Peiyun Zhang, Anhui Normal University (China), Yisheng An, Changan University (China), and Juan‐Pablo López‐Grao, University of Zaragoza (Spain), Dr. Huanxin Henry Xiong, Nokia (USA), and the esteemed anonymous reviewers of this book. We would like to appreciate the assistance provided by some of the first author's graduate students from Nanjing University of Science and Technology (NUST), who helped to prepare some diagrams of this book.

The first author would like to thank his doctoral thesis advisor Professor Yamin Sun, NUST, who introduced him to this exciting research field. He is also very thankful to his NUST colleagues for their great professional help and friendship. Finally, he appreciates his wife, Liwei Luo, and his lovely daughter, Kexin Huang, for their support during the long period of writing this book.

The second author would like to thank many of his mentors including Professors Frank DiCesare, James Tien, Peter Luh, Frank Lewis, Keith Hipel, Tsu‐Tian Lee, and Ljiljana Trajkovic, Dr. Dimitar Filev, and Dr. Edward Tunstel. He would also thank many colleagues at New Jersey Institute of Technology. Finally, he would thank his family members and many friends.

This monograph was in part supported by the National Natural Science Foundation of China under Grants 61773206 and 61203173, the Natural Science Foundation of Jiangsu Province of China under Grant BK20170131, the Foundation of Fujian Engineering Research Center of Motor Control and System Optimal Schedule under Grant FERC002, and the Jiangsu Overseas Visiting Scholar Program for University Prominent Young & Middle‐aged Teachers and Presidents.

Bo Huang and MengChu Zhou

Glossary

∅

The empty set

∩, ∪, ∖

Set intersection, union, and difference

⊕

The logical operation of exclusive OR

α

A symbolic function to add one

β

A coefficient of a place invariant

Γ

A positive integer that is big enough

A transformation function of the (

j

+ 1)th Boolean variable of

M

(

p

) when

t

fires

η

A symbolic function to subtract one

κ

The tight upper bound of capacities of activity places

λ

The empty string

σ

A sequence of transitions

The Parikh vector of

σ

The sum of operation times spent on

H

l

(

p

max

) in a state transfer

Φ

The set of marking/transition separation instances

Ω

A feasible region

A

K

The set of critical activity places

A

F

The set of free activity places

The set of forward free activity places

The set of backward free activity places

c

The cost or makespan of a path

c

*

The cost of an optimal path

c

(

S

,

S

′

)

The cost of a transfer from

S

to

S

′

in

c

*(

S

,

S

′

)

The optimal cost of a transfer from

S

to

S

′

in

C

A control vector indicating which transition is to fire

C

(

t

j

)

The element of

C

with respect to transition

t

j

d

The depth of a state

D

The vector of time delays in places

D

(

p

i

)

The time delay of a place

p

i

e

The relative error of a heuristic function

e

+

The positive relative error of a heuristic function

e

−

The negative relative error of a heuristic function

ℰ

t

The enable function of a transition

t

f

An estimate of the lowest cost from

M

0

(or

S

0

) to

M

G

(or

S

G

) along a path through

M

(or

S

)

f

*

The lowest cost from

M

0

(or

S

0

) to

M

G

(or

S

G

) among all paths through

M

(or

S

)

f

j

,

k

An integer variable in {0, 1} denoting whether or not a place invariant designed to forbid

M

j

forbids

M

k

F

The set of arcs in a Petri net

g

The lowest cost currently found from

M

0

(or

S

0

) to

M

(or

S

)

g

*

The lowest cost among all paths from

M

0

(or

S

0

) to

M

(or

S

)

G

(

N

,

M

0

)

The reachability graph of a net system (

N

,

M

0

)

The reachability graph of a place‐timed net system

h

A heuristic estimate of the cost from

M

(or

S

) to

M

G

(or

S

G

) along an optimal path

h

*

The cheapest cost from

M

(or

S

) to

M

G

(or

S

G

)

H

(

r

)

The set of holders of

r

H

l

(

r

)

The set of loyal holders of

r

I

A loading buffer

I

A place invariant

||

I

||

The support of

I

ℐ

n

The

n

×

n

identity matrix

l

j

,

i

The

i

th coefficient of a place invariant

I

j

M

A marking

M

0

An initial marking

M

G

A goal marking

M

(

p

i

)

The number of tokens in a place

p

i

at a marking

M

ℳ

A set of markings

ℳ

A

The set of admissible markings

The set of inadmissible markings

The set of uncontrollable dangerous markings

ℳ

D

The set of markings in the deadlock zone

ℳ

L

The set of legal markings

A minimal covering set of ℳ

L

A minimal covering set of ℳ

L

with respect to

K

‐cover

ℳ

F

The set of first‐met bad markings

A minimal covered set of ℳ

F

A minimal covered set of ℳ

F

with respect to

K

‐cover

ℳ

FIM

The set of first‐met inadmissible markings

N

A Petri net

N

= (

P

,

T

,

F

,

W

)

N

x

The

x

th processing subnet of

N

N

BDD

The number of used BDD nodes

N

E

The number of expanded states

(

N

,

M

0

)

A Petri net system

[

N

]

The incidence matrix of

N

[

N

]

−

The pre‐incidence matrix of

N

[

N

]

+

The post‐incidence matrix of

N

A place‐timed Petri net

A place‐timed Petri net system

ℕ

The set of natural numbers, i.e. {0, 1, 2, …}

ℕ

κ

Denotes {1, …,

κ

}

ℕ

A

Denotes

Denotes

Denotes

ℕ

J

Denotes {

x

∈ ℤ

+

∣

N

x

is the

x

th processing subnet of

N

}

ℕ

T

Denotes

O

An unloading buffer

O

An objective

p

A place in a Petri net

p

•

The set of post‐transitions of a place

p

•

p

The set of pre‐transitions of a place

p

p

c

A control place

p

max

A resource place whose sum of the processing times of its loyal holders is the maximal among all places in

P

A part type

P

A set of places

P

0

The set of idle places

P

A

The set of activity (operation) places

P

c

The set of control places

P

pre

(

t

j

)

A set of

t

j

's pre‐places whose processing times are not zero

P

post

(

t

j

)

A set of

t

j

's post‐places whose processing times are not zero

P

E

The set of end places

P

R

The set of resource places

The set of 1‐bounded resource places

P

S

The set of start places

q

j

An integer variable in {0, 1} denoting whether or not a place invariant

I

j

is selected to design a control place

r

A resource place

R

A resource type

R

The tokens' remaining time matrix of a place‐timed Petri net

R

i

,

u

The remaining time of the

u

th token in

p

i

R

u

The column vector of

R

with respect to the

u

th token

R

S

The set of shared resource places

The set of unshared resource places

R

(

N

,

M

0

)

The set of reachable markings of (

N

,

M

0

)

The set of reachable states of

ℛ

c

The percentage of lost optimality

ℛ

E

The percentage of the change in search effort

S

A state of

S

0

An initial state

S

G

A goal state

A BDD representing a set of states

t

A transition in a Petri net

t

•

The set of post‐places of

t

•

t

The set of pre‐places of

t

T

A set of transitions

T

C

The set of controllable transitions

The set of uncontrollable transitions

The set of all finite strings of elements in

T

cru

The set of crucial transitions

T

F

The set of free transitions

The set of forward free transitions

The set of backward free transitions

T

K

The set of critical transitions

T

O

The set of observable transitions

The set of unobservable transitions

The set of observable but uncontrollable transitions

The computational time

The loyal time of a resource place

p

i

U

p

The resource requirements of an activity place

p

∈

P

A

w

j

The (

j

+ 1)th Boolean variable for the weight of an arc

W

The set of weights of arcs

Z

The set of zones separation instances

ℤ

The set of integers

ℤ

+

The set of positive integers

Acronyms

AI

Artificial intelligence

AMS

Automated manufacturing system

BDD

Binary decision diagram

BF

Best first

BT

Backtracking

DEDS

Discrete event dynamic system

DF

Depth first

DP‐net

Deadlock prevention net

DWA

Dynamic weighted A*

DZ

Deadlock zone

ELS

3

PR

Extended system of linear sequential processes with resources

ES

3

PR

Extended system of simple sequential processes with resources

ESSP

Event/state separation problem

FBM

First‐met bad marking

FIM

First‐met admissible marking

FMS

Flexible manufacturing system

GLS

3

PR

System of generalized linear simple sequential processes with resources

GMEC

Generalized mutual exclusion problem

GPU

Graphics processing unit

IDWA

Improved dynamic weighted A*

ILP

Integer linear program

LMILP

Lexicographic multiobjective integer linear program

LS

3

PR

System of linear sequential processes with resources

LZ

Live zone

MFFP

Maximal number of forbidden FBMs problem

MMP

Minimal number of monitors problem

MPP

Minimal number of P‐semiflows problem

MTSI

Marking/transition separation instance

NS‐RAP

Non‐sequential resource allocation process

PC

2

R

Process competing for conservative resources

PI

Place invariant

PN

Petri net

PPN

Production Petri net

RAS

Resource allocation system

ROBDD

Reduced ordered binary decision diagram

S

2

LSPR

System of simple linear sequential processes with resources

S

2

U

2

T

Supervisor synthesis with uncontrollable and unobservable transitions

S

3

PGR

2

System of simple sequential processes with general resource requirements

S

3

PMR

System of simple sequential processes with multiple resources

S

3

PR

System of simple sequential processes with resources

S

4

R

System of sequential systems with shared resources

SC‐net

System scheduling net

SCC

Strongly connected component

SCT

Supervisory control theory

SSP

States separation problem

TPN

Timed Petri net

WOT

Weighted operation time

WRT

Weighted resource time

WS

3

PR

Weighted system of simple sequential processes with resources

WS

3

PSR

Weighted system of simple sequential processes with several resources

About the Authors

Bo Huang received a PhD degree from Nanjing University of Science and Technology, Nanjing, China, in 2006. He was a Visiting Professor at the University of Missouri‐Kansas City, MO, USA, in 2013, and a Visiting Scholar at New Jersey Institute of Technology, Newark, NJ, USA, in 2014–2015 and 2019–2020. He is now a professor at Nanjing University of Science and Technology. His research fields include discrete event systems, Petri nets, intelligent automation, intelligent transportation, and multi‐robot systems. He has published 60+ papers and presided 10+ projects in these areas.

MengChu Zhou is a Distinguished Professor of Electrical and Computer Engineering at New Jersey Institute of Technology. He made many contributions to the areas of Petri nets, intelligent automation, Internet of things, big data, web services, and intelligent transportation. He has over 800 publications including 12 books, over 500 journal papers, 23 patents, and 29 book chapters. He is the Editor‐in‐Chief of IEEE/CAA Journal of Automatica Sinica and a recipient of Humboldt Research Award for US Senior Scientists from Alexander von Humboldt Foundation, and Franklin V. Taylor Memorial Award and Norbert Wiener Award from IEEE Systems, Man and Cybernetics Society. He is a Fellow of IEEE, IFAC, AAAS, and CAA.

Part IResource Allocation Systems and Petri Nets

1Introduction

This chapter introduces the definitions of resource allocation systems (RASs) and their deadlock resolution and system scheduling. Different approaches to control and schedule RASs based on Petri nets are briefly reviewed. In addition, both the pros and cons of these approaches are introduced to show the development of deadlock resolution and system scheduling methods for RASs based on Petri nets.

1.1 Resource Allocation Systems

Resource scarcity is a common scenario in many discrete event dynamic systems (DEDSs). In such systems, available resources (such as machines, robots, drives, and programs) have to be shared among concurrently running processes (such as parts, vehicles, and data) and they must compete in order to be granted their allocation and achieve some system objectives such as maximizing makespan and minimizing tardiness. These systems are named resource allocation systems (RASs). This chapter briefly introduces different deadlock resolution and scheduling methodologies based on Petri nets, which are in the view of resource allocation and have successfully been applied to many RASs, such as flexible manufacturing systems (FMSs) (Li et al., 2008b), project management systems (Kumar & Ganesh, 1998), and multithread software engineering systems (López‐Grao & Colom, 2012).

According to Reveliotis et al. (1997), an RAS usually contains a set of resource types , and a set of jobs . Each resource type is further characterized by its capacity that is a finite positive integer indicating at most how many units of are in the system. A job often contains a set of tasks or job stages , representing the operations to be processed to finish the job. The operational assumptions on job routing structures and resource requirements give rise to complex behavioral patterns, leading to different control and scheduling approaches. In terms of the resource requirements for jobs, RASs can be categorized into the following four classes: (i) single‐unit RASs in which each operation only requires one resource from a single resource type; (ii) single‐type RASs in which each operation requires an arbitrary number of resources from the same resource type; (iii) conjunctive (AND) RASs in which each operation requires an arbitrary number of resources from different resource types; and (iv) disjunctive/conjunctive (AND/OR) RASs in which an operation may be associated with a set of conjunctive requests for different resource types. Among them, the AND/OR RASs are the most generalized ones.

In an RAS, there are often a limited number of shared resources to be allocated. The competition for such shared resources by different operations may cause deadlocks where two or more operations are each indefinitely waiting for the other to release their acquired resources. Deadlocks can lead to unnecessary economic cost and even catastrophic results in practical systems. Hence, they are a highly undesirable situation.

For a deadlock in RASs to occur, four conditions must be satisfied (Coffman et al., 1971):

Mutual exclusion: when operations claim exclusive control of the resources they need;

Hold and wait: when operations hold resources already allocated to them while waiting for additional resources.

No preemption: when a resource can only be voluntarily released by the operation holding it.

Circular wait: when a circular chain of operations exists, where each operation holds one or more resources that are being requested by the next operation in the chain.

If a deadlock occurs, the above four conditions are met. To handle deadlocks in RASs, most approaches work by preventing one of the four conditions from being satisfied. In general, there are four deadlock handling approaches: deadlock ignoring, deadlock detection and recovery, deadlock avoidance, and deadlock prevention.

Deadlock ignoring, which is also known as an ostrich algorithm, assumes that deadlocks are exceedingly rare in the system and the influence incurred by a deadlock is tolerable. In this case, deadlock ignoring is acceptable from a technical and economical point of view. For example, in UNIX, if the process table is full and processes still try to fork some subprocesses, a deadlock can occur. However, it happens rarely and the procedures to prevent it are cumbersome. Thus, it is often ignored.

Deadlock detection and recovery (Reveliotis, 2000; Wysk et al., 1994) uses a monitor to detect and recover from deadlocks. When a deadlock occurs, the monitor detects it and then actions are taken to either terminate operations in the deadlock or release some resources held by operations to recover the system from the deadlock. This approach requires the periodic detection of deadlocks, which uses a large amount of data and may become complex if several kinds of shared resources are considered. Its efficiency depends on the response time of the implemented algorithms for deadlock detection and recovery. Thus, it is only applied to systems where detection and recovery strategies are not expensive.

Deadlock avoidance (Ezpeleta & Recalde, 2004; Fanti et al., 2006; Hsieh, 2004; Lawley, 2000; Luo et al., 2019; Reveliotis, 2007; Wu & Zhou, 2005; Xing et al., 2009) is a dynamic and online approach that works in a real‐time manner and bases the decision on information about the resource allocation status. In deadlock avoidance, both deadlocks and bad states (which are the states that inevitably lead to deadlocks) are avoided by using look‐ahead procedures. The approach usually has high resource utilization and throughput since it tries to permit more states in a system, but sometimes does not eliminate all deadlocks. If it cannot avoid all deadlocks, some recovery strategies are required (Wysk et al., 1994).

Deadlock prevention (Abdallah et al., 2002; Chen et al., 2016; Ezpeleta et al., 1995; Fanti & Zhou, 2004; Feng et al., 2020; Li & Zhao, 2008; Luo et al., 2009; Tricas et al., 2000; Zhou & DiCesare, 1991) works by preventing at least one of the four conditions necessary for the occurrence of a deadlock at any point of the RAS dynamic. It is an off‐line computational approach which controls the requirements for resources to ensure that deadlocks never occur. When compared with deadlock avoidance, this approach tends to be more conservative and reduces resource utilization and system productivity. However, it has the advantages of safety and stability. In addition, its controller implementation does not need the knowledge of system states, which leads to a simple control law.