International Journal of Engineering Materials and Manufacture (2017) 2(1) 11-15 https://doi.org/10.26776/ijemm.02.01.2017.02 A. H. Taha, M. H. F. Al-Hazza and E. Y. T. Adesta Department of Manufacturing and Materials Engineering International Islamic University Malaysia PO Box 10, 50728 Kuala Lumpur, Malaysia E-mail: muataz@iium.edu.my Reference: Taha, A. H.., Al-Hazza, M. H. F. and Adesta, E. Y. T. (2017). Modelling and Analysing Deadlock in Flexible Manufacturing System using Timed Petri Net. International Journal of Engineering Materials and Manufacture, 1(2), 11-6. Modelling and Analysing Deadlock in Flexible Manufacturing System using Timed Petri Net Assem Hatem Taha, Muataz Hazza Faizi Al Hazza, Erry Y. T. Adesta Received: 21 February 2017 Accepted: 15 March 2017 Published: 31 March 2017 Publisher: Deer Hill Publications © 2017 The Author(s) Creative Commons: CC BY 4.0 ABSTRACT Flexible manufacturing system (FMS) has several advantages compared to conventional systems such as higher machine utilization, higher efficiency, less inventory, and less production time. On the other hand, FMS is expensive and complicated. One of the main problems that may happen is the deadlock. Deadlock is a case that happens when one operation or more are unable to complete their tasks because of waiting of resources that are used by other processes. This may occur due to inappropriate sharing of the resources or improper resource allocation logic which may lead to deadlock occurrence due to the complexity of assigning shared resources to different tasks in an efficient way. One of the most effective tools to model and detect the deadlocks is the petri net. In this research the MATLAB software was used to detect the deadlock in two parallel lines with one shared machines. The analysis showed that the highest utilization is in transition t4 with 71% and the longest waiting time is in place p4 at 72 seconds. Hence, deadlock was located there as parts wait to be processed by machine 1 which is busy to perform processes on parts in both lines. Keywords: FMS, deadlock, shared resources, petri net 1 INTRODUCTION The competition of companies in marketplace requires high degree of efficiency and low production time. These companies try to have suitable manufacturing systems that can be flexible to any circumstance as product life cycles are reduced in the continuously changing market. To respond to these demands, the use of a Flexible Manufacturing System (FMS) has been widely applied to attain high productivity and production flexibility [1]. Manufacturing process has been improved recently to meet the increasing requirements of the market. One of the very demanding requirements that impacts the development of the Manufacturing process is the variability aspect in the market. Market needs are changing rapidly, which require more flexibility in the manufacturing process to respond to such changes quickly. One of the main criteria that indicate to the flexibility in the manufacturing process is the degree of resources sharing. FMS is a system that has capability to react to any changed condition happen in process. It includes numerically controlled machines with the aid of value-added, automatic and material handling facilities. Industrial companies use FMS to fulfil the demands for making different kinds of products from small to medium quantity in production [2]. FMS includes both material handling devices and machines which are controlled by computer programs to make the processes flow flexibly. It gives operators the chance to load new programs simply when it is necessary to manufacture different kinds of products. FMS helps managers to provide customized products, improve equipment utilization to reduce costs and process time [3]. In FMS, shared resources with many parts being used in the system may cause a major issue that industries face which is deadlock. Deadlock is a common phenomenon in computer integrated systems (CIM) such as automated production system. It is an event where the manufacturing system wholly or partially stop and unable to finish a specific task. It occurs when some parts in waiting status as the machines needed to complete their operation are held by other parts in the production line [4]. Deadlock issue was ignored in the past by eliminating all parts or some of them that have a role for the deadlock to happen and using their resource with other parts in the operation. Yet, flexible manufacturing system forced Modelling and Analysing Deadlock in Flexible Manufacturing System using Timed Petri Net 12 manufacturers to look for ways to allocate resources without deadlock exist to run the operations efficiently, flexibly and at low cost [5]. Consequently, there is a need to study deadlock and find a method to avoid it and prevent it if it’s possible. High degree of resources sharing leads to more flexibility in the production. However, higher degree of resources sharing is also a source of conflicts in accessing the resources by many production processes. One of the main problems of synchronization between multi-processes in accessing shared resources is deadlock. The problem of deadlock causes halt or failure in part or evens the whole manufacturing system unless a human being intervention is performed in order to break the deadlock. The general taxonomy of the approaches of modelling FMS consists of three classes of approaches. Petri nets have been used widely besides directed graph [6], and finite state automata [7]. Petri net modelling techniques is a mathematical tool for modelling different aspects of FMS, and for handling all its attributes such as concurrency, causal dependency, and dynamics. 2 TYPES OF FMS FMS has five types and they are sequential, random, dedicated, engineered and Modular FMSs [8]. In sequential FMS, one piece part is manufactured in batch line followed by another product prepared to be processed after the first one and so on for other parts. Random FMS can make any mix of product types without sequence. Dedicated FMS can produce regular limited mix of product types. For engineered FMS, same mix of part types can be manufactured in the system. Modular FMS is an advanced system which allows the operator to use any of the four kinds previously mentioned. FMS can be classified based on level of flexibility [9]. There are three levels of flexibility: basic flexibility, system flexibility and aggregate flexibility. Basic flexibility contains three kinds which are machine flexibility, material handling flexibility and operation flexibility. Machine flexibility is the level of easiness that a machine can do several tasks. Material handling flexibility is a measure of ability to transfer different part kinds and place them at several machine tools in the manufacturing system. Operation flexibility is the ease to make a part type using different process sequences. System flexibility includes volume, expansion, routing, process and product flexibility. Volume flexibility is the ability to manufacture efficiently a part type with different volumes. Expansion flexibility is to establish a system and do changes for the aim of expanding it. Routing flexibility is a measure of available routes that a part can be processed through them in the system. Process flexibility is the ability to make amount of parts without need to conduct big changes in setup. Product flexibility is the number of parts that system can produce without doing a small change in setup. Aggregate flexibility has three types which are program, production and market flexibility. Program flexibility is the system capability to perform operations for long duration without any interruption. Production flexibility is to make little investment to manufacture specific number of parts and market flexibility is the capacity of system to adjust its process and plan in accordance of market requirements. FMS has several advantages such as higher machine utilization than conventional manufacturing system, fewer machines to be used in the process, less space used in the factor, less used inventory, less lead time and higher response to part, tool and production schedule changes. On the other hand, FMS is expensive, complicated when compared to transfer lines and requires skilled worker to control the system and fix any problem [10]. 3 DEADLOCK Deadlock is a case that happens when processes in the system can’t do their tasks because of waiting of resources held by other processes. It occurs in flexible manufacturing system due to resource sharing, buffer capacity and availability in material handling system. It leads to affect on manufacturing system performance by reducing machine utilization, efficiency in production process, and delay in finishing the operation [11]. There are four cases where deadlock can occur. These conditions are mutual exclusion, hold and wait, no pre- emption and circular wait [12]. Mutual condition means resource can be utilized by one process and no other process can use at a time. Hold and wait condition occurs when one is held by a process which at the same time use another resource. This causes a problem in resource utilization as a process might request a resource but use it at end of its task only. This condition also leads to starvation for some processes that wait for resources with no specific time. No pre-emption condition is when it is not possible to interrupt process while it is functioning to give the access of the resources to another process and to resume its work again in later time. Circular wait condition exists when a there is a resource requested by a process and this resource is held by the next process in the chain. The deadlock and blocking phenomena may lead to tragic results and intervention from human beings. Detecting deadlocks in the manufacturing systems through developing simulating model will help to improve and increase the efficiency of the flexible manufacturing systems. In this paper, timed petri net was used to simulate the manufacturing system and analyse it to determine the deadlocks. 4 PETRI NET Petri Net (PN) is a tool for modelling and studying systems with parallel, synchronized processes and shared resources. A PN consists of places (P) which denote to conditions, transitions (T) that indicate events and arcs (F) that link places to transitions. This can be represented by N = (P, T, F), where P and T are limited but not equal zero and F ⊆ (P × Taha et al., (2017): International Journal of Engineering Materials and Manufacture, 1(1), 1-15 13 T) ∪ (T × P) which means that firing tokens (k) can be from place to transition or vice versa. Token in a place carries the condition that tells that the resource or item is available in this place. P is circle shape in petri net and T can be bar or box shape. Given a node x ∈ P ∪ T, an event has input place (pre-condition x) which is defined as •x = {y ∈ P ∪ T|(y, x) ∈ F}, and output place (post-condition x) that is defined as x• = {y ∈ P ∪ T|(x, y) ∈ F}. A marking is the state of system that is M: P → Z+, where Z+ = {0, 1, 2,….., n} which is number of integers. Given a place p ∈ P and a marking M, M (p) denotes the number of tokens in p at M. Let S ⊆ P be a set of places; the sum of tokens in all places of S at M is denoted by M (S), i.e., M(S) = Σ p ∈ S p∈ S M (p). A marked PN is the one with an initial marking (M0) is, denoted as (N, M0). A transition t ∈ T is enabled at a marking M, denoted by M [t >, if ∀p ∈ •t, M (p) > 0. An enabled transition t at M can be fired, resulting in a new reachable marking M‵, denoted by M (t > M‵), where M‵ (p) = M (p) − 1, ∀p ∈ •t \ t•, M‵ (p) = M (p) + 1, ∀p ∈ t• \ •t, and, otherwise, M‵ (p) = M (p) [13,14]. 5 SCENARIO A manufacturing system consists of two parallel jobs to make final product from parts A and B. Machine 1 is shared between the two lines for parts coming from buffer 1 and 2. This leads to deadlock as the machine will be busy with doing process on one part while the other part waits for its turn. Machine 2 and 3 perform a process for part A and B respectively, after being done from machine 1. The last machine assembles part A and part B to make the final product. The process was designed using timed petri net. MATLAB software has been used to simulate the system as shown in the figures 2 and 3. It was assumed that 15 available parts (represented by tokens) are in each source (represented by part A and part B places). The following elements in the net are: - t1, t2: immediate transitions to show movement of parts A & B to buffers 1 and 2. - p3, p4: buffers 1 and 2. - p5, t3, t4: shared machine 1 with a 10 seconds process. - p6, t5: machine 2 performing a process within 12 seconds. - p7, t6: machine 3 accomplishing a process at 14 seconds. - p8, p9, t7: assembly process for part A and B performed at duration of 6 seconds using machine 4. There is one token in place 5 as a signal for machine 1 to perform process once one token comes from place 3 or place 4. Then, it will be available again once token that represents part goes to the next machine in line to be processed. Figure 1: Scenario of manufacturing system Modelling and Analysing Deadlock in Flexible Manufacturing System using Timed Petri Net 14 Analysis of places was obtained and collected in Tables 1. Arrival sum is the number of parts that arrives to places or leave them to another one. Arrival distance is the mean time between parts to reach to a place or to depart from it. Waiting time is the average time that part stays in a place and queue length is average number of parts in a place. Place p4 has the longest waiting time at 72 seconds and a queue length of 1.3 part as shared machine (p6) is busy in processing other parts from both lines which leads to delay and more wait for parts in this place. Table 2 illustrates the analysis of transitions in the petri net. Service sum is the number of executed part in each transition. Service distance is the mean time between firing one token and another. Utilization is the probability of transition to be busy. Transition t4 has the highest utilization at 71% while the lowest utilization is in t7 at 32.3%. Deadlock exists where there is a high utilization and a long waiting time. So, it exists in p4 and t4. Figure 2: Petri net design of the system Figure 3: Simulation of the system Table 1: Places analysis Place Name Arrival Sum (part) Arrival Distance (seconds) Waiting Time (seconds) Queue Length (part) p3 5 24.8 41 1.2 p4 3 41.3333 72 1.3 p5 5 24.8 10 0.5 p6 4 31 12 0.3 p7 2 62 14 0.2 p8 3 41.3333 23 0.4 p9 2 62 17 0.3 Product 2 62 - - Taha et al., (2017): International Journal of Engineering Materials and Manufacture, 1(1), 1-15 15 Table 2: Transitions analysis Transition Name Service Sum (part) Service Distance (seconds) Utilization (%) t3 4 31 32.3 t4 2 62 71 t5 3 41.3 37.1 t6 2 62 66.1 t7 2 62 30.6 6 CONCLUSIONS Based on the results, it can be concluded that use of petri net method was an effective tool in detecting the deadlock for parallel machines with shared resources. Timed petri net was used to simulate and analyse the manufacturing system. The simulation analysis denoted that the deadlock is in p4 and t4 that have the highest value of utilization and waiting time respectively. A proper planning for the production system is needed to eliminate the deadlock and ensure the flexible flow of the parts in the system. REFERENCES 1. Kaschel C., H., & Bernal, L. M. (2006). Importance of Flexibility in Manufacturing Systems. International Journal of Computers, Communications & Control, Vol. I, No. 2, 53-60. 2. Qiao, G., Lu, R. F., & McLean, C. (2006). Flexible Manufacturing Systems for Mass Customisation Manufacturing. International Journal of Mass Customisation, Vol.1, No. 2/3, 374 – 393. 3. Heizer, J., & Render, B. (2005). Operations Management, 8th edition. New Jersey: Pearson Prentice Hall. 4. Xing, K., Lin, F., & Hu, B. (2001). An Optimal Deadlock Avoidance Policy for Manufacturing Systems with Flexible Operation Sequence and Flexible Routing. Proceedings of the IEEE International Conference on Robotics 8 Automation, Vol. 4, 3565 – 3570. 5. Fanti, M. P., & Zhou, M. (2004). Deadlock Control Methods in Automated Manufacturing Systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 34, No. 1, 5-22. 6. Leibfried, T. F. (1989). A Deadlock Detection and Recovery Algorithm Using the Formalism of a Directed Graph Matrix. SIGOPS Operating Systems Review, Vol. 23, Issue 2, 45 – 55. 7. Yalcin, A., & Boucher, T. O. (2000). Deadlock Avoidance in Flexible Manufacturing Systems Using Finite Automata. IEEE Transactions on Robotics and Automation, Vol. 16, No. 4, 424 – 429. 8. Shivanand, H., Benal, M., & Koti, V. (2006). Flexible Manufacturing System. New Age International Pvt Ltd Publishers. 9. Basak, Ö., & Albayrak, Y. E. (2014). Petri Net Based Decision System Modeling In Real-Time Scheduling and Control of Flexible Automotive Manufacturing Systems. Computers & Industrial Engineering, 2-11. 10. Chahal, V. (2012). An Efficient Approach of Good Manufacturing Flexibility by FMS and RMS with Minimizing the Overall Wastage by JIT. Proceedings of the National Conference on Trends and Advances in Mechanical Engineering, Faridabad, Haryana, 833-838. 11. Baruwa, O. T., Piera, M. A., & Guasch, A. (2014). Deadlock-Free Scheduling Method for Flexible Manufacturing Systems Based On Timed Colored Petri Nets and Anytime Heuristic Search. IEEE Transactions on Systems, Man, and Cybernetics: Systems, issue 99, 1-16. 12. Li, Z., Wu, N., & Zhou, M. (2012). Deadlock Control of Automated Manufacturing Systems Based On Petri Nets— A Literature Review. IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews, Vol. 42, No. 4, 437-462. 13. David, R., & Alla, H. (2010). Discrete, Continuous, and Hybrid Petri Nets, 2nd Edition. Berlin: Springer. 14. Xing, K., Han, L., Zhou, M., & Wang, F. (2012). Deadlock-Free Genetic Scheduling Algorithm for Automated Manufacturing Systems Based On Deadlock Control Policy. Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, Vol. 42, No. 3, 603-615.