Scheduling for deadlock avoidance operation in robotic manufacturing cells

Abstract

This paper addresses a scheduling and control method for deadlock avoidance operation in robotic manufacturing cells with flexible job sequences. The proposed scheduling method generates an optimal or near-optimal schedule avoiding deadlock even when an unexpected event such as machine failure happens. The proposed deadlock-free scheduling approach consists of two components: deadlock manager, and dynamic scheduler. The deadlock manager builds and manages deadlock in a robotic manufacturing cell. The resources or machines in the robotic manufacturing cell are classified into two categories: potential deadlock set and deadlock-safe set. This paper presents an efficient method to obtain a minimal potential deadlock set using a genetic algorithm. Scheduling with deadlock avoidance policy is applied to the potential deadlock set, and scheduling only is applied to the deadlock-safe set. The dynamic scheduler generates a deadlock-free schedule using piecewise shifting operations in a real-time operation phase. The proposed scheduling approach is shown by simulation to be efficient in managing deadlock inherent to the robotic manufacturing cells.

Keywords

scheduling deadlock avoidance robotic manufacturing cell

References

Biché

, ‘Trends in track system architecture’ Solid State Technol. (1995, (May)): 83–86.

Chang

Y. S.

Lee

H. Y.

Fowler

J. W.

, ‘A hybrid approach for modeling and analysis of an integrated machine’ Proc. IMechE., Part B: J. Engineering Manufacture 218 (11) (2004): 1577–1590 DOI: 10.1243/0954405042418437.

Yoon

H. J.

Lee

D. Y.

, ‘Deadlock-free scheduling of photolithography equipment in semiconductor fabrication’ IEEE Trans. Semicond. Mf. 17 (1) (2004): 41–54.

Coffman

E. G.

Elphick

M. J.

Shoshani

, ‘System deadlocks’ Computing Surveys 3 (2) (1971): 67–78.

Silberschatz

Galvin

P. G.

, Operating system concepts (Reading, MA: Addison-Wesley 1994).

Banaszak

Z. A.

Korgh

B. H.

, ‘Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows’ IEEE Trans. Robotics Automn. 6 (6) (1990): 724–734.

Boukerche

Tropper

, ‘A distributed graph algorithm for the detection of local cycles and knots’ IEEE Trans. Distributed Systems 9 (8) (1998): 748–757.

Cidon

, ‘An efficient distributed knot detection algorithm’ IEEE Trans. Software Engng 15 (5) (1989): 644–649.

Lawley

M. A.

, ‘Deadlock avoidance for production systems with flexible routing’ IEEE Trans. Robotics Automn. 15 (3) (1999): 497–509.

10.

Viswanadham

Narahari

Johnson

T. L.

, ‘Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models’ IEEE Trans. Robotics Automn. 6 (6) (1990): 713–723.

11.

Ezpeleta

Colom

J. M.

Martinez

, ‘A Petri net based deadlock prevention policy for flexible manufacturing systems’ IEEE Trans. Robotics Automn. 11 (2) (1995): 173–184.

12.

Ezpeleta

Colom

J. M.

, ‘Automatic synthesis of colored Petri nets for the control of FMS’ IEEE Trans. Robotics Automn. 13 (3) (1997): 327–337.

13.

Fanti

M. P.

Maione

Mascolo

Turchiano

, ‘Event-based feedback control for deadlock avoidance in flexible production systems’ IEEE Trans. Robotics Automn. 13 (3) (1997): 347–363.

14.

Abdallah

I. B.

ElMaraghy

ElMekkawy

, ‘An efficient search algorithm for deadlock-free scheduling in FMS using Petrinets’ In Proceedings of the 1998 IEEE International Conference on Robotics and automation, Leuven, Belgium, 16–20 May, 1998, pp. 1793–1798.

15.

Ramaswamy

S. E.

Joshi

S. B.

, ‘Deadlock-free schedules for automated manufacturing workstations’ IEEE Trans. Robotics Automn. 12 (3) (1996): 391–400.

16.

Gang

, ‘Deadlock-free scheduling strategy for automated production cell’ IEEE Trans. System, Man. Cybernetics. Part A 34 (1) (2004): 113–122.

17.

Yang

H. B.

Yan

H. S.

, ‘A deadlock avoidance strategy for knowledgeable manufacturing systems’ Proc. IMechE, Part B: J. Engineering Manufacture 223 (B2) (2009): 195–205 DOI: 10.1243/09544054JEM1194.

18.

Goldberg

D. E.

, Genetic algorithms in search, optimization, machine learning (Reading, MA: Addison-Wesley 1989).