Formal Methods in Manufacturing

8	Deadlock Avoidance Policies in Production Systems by a Digraph Approach Maria Pia Fanti, Bruno Maione and Biagio Turchiano

CONTENTS

8.1 Introduction

8.1.1 Deadlock Problem

8.1.2 Digraph Theory and Deadlock Avoidance

8.2 Digraph Representation of The Resource Allocation System

8.2.1 The Manufacturing System Model

8.2.2 Digraph Definitions

8.2.3 Revisiting Some Digraph Properties

8.3 Necessary And Sufficient Conditions for Deadlock

8.4 Second-Level Deadlock

8.5 Deadlock Avoidance Techniques

8.6 Restriction Policy Properties

8.6.1 Computational Complexity

8.6.2 Some Remarks about the Restriction Policies

8.7 Relation Between Graph Theoretic And Petri Net Approaches To Deadlock Avoidance

8.8 Conclusions

8.A Appendix A

8.B Appendix B

8.C Appendix ...