Dynamic routing and the performance of automated manufacturing cells

IIE Transactions (2000) 32, 975±988 Dynamic routing and the performance of automated manufacturing cells THOMAS O. BOUCHER*, ALI YALCIN and TSUTA TAI Industrial and Systems Engineering, Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854, USA E-mail: tboucher@rci.rutgers.edu Received April 1999 and accepted December 1999 There has been a considerable amount of research done on the ``cell formation'' problem, in which machining cells are designed to process a family of components. More recently, it has been suggested that machining cells should be designed so that they take advantage of the ¯exibility for processing parts that have alternate, or multiple machine routing possibilities. It is argued that such ¯exibility will improve machine utilization as well as other measures of cell performance and may reduce the need for centralized cell loading and scheduling algorithms. Unfortunately, if the cell is automated, routing ¯exibility requirements can create a complex control problem for the cell controller. In this paper we implement a cell controller designed to handle the requirements of the ¯exible routing of parts and compare the performance of the cell to the case in which each part has only one routing. We ®nd that signi®cant improvements occur when the cell design is capable of processing parts with ¯exible routings. 1. Introduction Cellular Manufacturing (CM) has proven to be an important concept for manufacturing system organization. In CM, each cell is dedicated to processing a speci®c family of parts. It has been shown that this grouping and specialization of machines leads to a reduced set-up time, reduced work-in-process inventory, and subsequent reductions in cost when compared to traditional job shops (Boucher and Muckstadt, 1985). One of the drawbacks of CM is the potential for under utilization of machines and consequent low production throughput. The major problem in this regard is the loss of ¯exibility that may occur if the machines in the cell are functionally dissimilar, limiting machining operations with respect to the choice of machines that can perform the operation. This has led to an interest in designing cells that incorporate ¯exibility in the cell design. The primary work has been in the area of incorporating routing ¯exibility (Al-Quattan, 1990; Rajamani et al., 1990; Sankaran and Kasilingam, 1993) i.e., the ability of the cell to handle parts with alternate routing plans. There have also been researchers who have addressed the allocation of ¯exible operations among a system of cells, requiring intercellular ¯ows in order to complete all machining operations (Askin et al., 1997; Dahel and Smith, 1993; Tilsley and Lewis, 1977). *Corresponding author 0740-817X Ó 2000 ``IIE'' In this study we are interested in the performance of the ``¯exible automated'' cell as a basic manufacturing unit. We address the problems associated with the operational control of such cells when they are highly automated with respect to materials handling and supervisory control. In this mode, many of the issues associated with ¯exible manufacturing systems in general apply to the operation and control of a manufacturing cell. We are interested in the control of ¯exible manufacturing cells such that we improve the overall system performance in terms of regular performance measures, such as ¯ow time, throughput, and machine utilization. This problem is related to research in ¯exible manufacturing systems in general. Some researchers have addressed increasing the performance of ¯exible manufacturing systems at the operation and control level over the past several years. This has included evaluating the bene®ts of increased routing ¯exibility due to alternative machining (Abdin, 1986; Benjaafar et al., 1995; Lin and Solberg, 1991), and/or routing ¯exibility due to alternative sequencing (Benjaafar and Ramakrishnan, 1996; Lin and Solberg, 1991; Rachamadugu et al., 1993). An important observation, made by Rachamadugu and Stecke (1994) is that ``¼most of the research to date has not adequately addressed the bene®ts that can be obtained by using routing ¯exibility.'' In most of the approaches to scheduling ¯exible manufacturing systems, the part routing is determined a-priori. During operation, each part type has only one route through the system. If routing ¯exibility is allowed during operations, it may be 976 possible to o€ load bottleneck machines by dynamically allocating parts to available machines, improving machine utilization and decreasing ¯ow time. Lin and Solberg (1991) argued that the choice of part process plans should be deferred until knowledge of the real-time state of the factory is available. Using a simulation, they compared the performance of a-priori chosen single routing plans with multiple routing plans and found that the latter reduced mean ¯ow time while increasing system throughput and machine utilization. In their simulations the order of magnitude of the improvement was about 10%. Lin and Solberg (1991) point out the fact that a realtime control system that would be capable of routing or scheduling parts based on multiple process plans would be more complicated than current practice and ``¼calls for new control algorithms.'' For example, in their simulations they employed simple dispatching rules. They noted that ``¼there were deadlocks using these rules, that is, some parts were stuck in the system for a long time. Therefore, unless there are good deadlock resolution strategies, these rules are not recommended.'' Deadlock is an even more critical issue in an automated manufacturing cell (Ezpeleta et al., 1997; Fanti et al., 1997; Lawley et al., 1998; Ramaswamy and Joshi, 1996; Reveliotis et al., 1997; Viswanadham et al., 1990; Wysk et al., 1991). Deadlock occurs when parts are assigned to machines such that further ¯ow of these parts is permanently inhibited (Ramaswamy and Joshi, 1996; Reveliotis et al., 1997). In manufacturing cells, limited space and subsequent bu€er capacities restricts the movement of parts among machines. The most restrictive example of this is the ``direct access'' system in which parts must proceed from one operation to another without any intermediate storage. It has been shown by Wysk et al. (1991) that, when two parts occupy machines and each part requires the other machine for the next operation, a ``circular wait'' condition occurs and neither part can proceed with further machining. In this study, we focus on direct access cellular manufacturing systems. The performance of a manufacturing unit (cell, plant) can always be improved by good planning and scheduling practices. This has been studied by many researchers in the context of ¯exible manufacturing systems and ¯exible manufacturing cells (Byrne and Chutima, 1997; Nof et al., 1979; Rajamani et al., 1990; Raman et al., 1989; Sawik, 1990; Stecke and Solberg, 1981; Sun et al., 1994; Wilhelm and Shin, 1985; Yamagata et al., 1991) and some included considerations of ¯exible routing within the manufacturing system (Ghosh and Gaimon, 1992; Lee and Di Cesare, 1994; Nasr and Elsayed, 1990; Stecke, 1992; Stecke and Raman, 1994, 1995). Unfortunately, most sophisticated scheduling methods require solving complex models and, once a schedule is ®xed, interruptions such as machine breakdowns and other random events can defeat the purpose of the schedule. In general, Boucher et al. a ®xed schedule of part routings is not very robust in recovering from system disturbances (Dutta, 1990; Jain and Elmaraghy, 1997). Rachamadugu and Stecke (1994) have suggested that the use of routing ¯exibility in lieu of sophisticated scheduling can substantially improve system performance and obviate the need for scheduling (Rachamadugu and Stecke, 1994). Exploiting routing ¯exibility during the execution of production, particularly when deadlocks must be avoided, requires a relatively sophisticated real-time controller. Most of the performance analysis research on FMS and automated ¯exible machining cells ignores the real-time control requirements. Some researchers have incorporated control issues in their work (Ezpeleta et al., 1997; Fanti et al., 1997; Lawley et al., 1997a, b, 1998; Lee and Di Cesare, 1994; Ramadge and Chase, 1992; Ramaswamy and Joshi 1996; Reveliotis et al. 1997; Yalcin and Boucher, 1998) but, with the exception of Lawley et al., (1998), they have not conducted suitable experiments to evaluate the e€ects of the real-time controller operation on system performance. In this study we implement a real-time controller capable of executing alternative routing sequences while avoiding deadlock and we evaluate its e€ect on the resulting system performance. We focus on the evaluation of performance di€erences between automated manufacturing cells that incorporate routing ¯exibility versus those that do not. This cell controller is interfaced to a simulation model of a manufacturing cell so that it can direct the allocation of parts among the machining operations dynamically in real-time. A set of experiments are then run that compare the performance of the system when incoming parts have routing ¯exibility versus no routing ¯exibility. A statistical analysis of resulting performance measures gives insight into the bene®ts associated with exploiting routing ¯exibility during the deadlock free operation and control of an automated manufacturing cell. The rest of the paper is organized as follows. Section 2 introduces the control model. In Section 3, the experiment is de®ned and Section 4 presents the results of the simulation runs. Section 5 addresses algorithmic and software design issues and, ®nally, in Section 6 some conclusions are drawn. 2. The cell controller It is assumed that each part entering the cell has a unique identi®cation, each part occupies one resource at a time and that each resource can process only one part at a time. A typical example of a machining cell is shown in Fig. 1. In this example, there are three resources in this cell: machine 1, machine 2, and a robot. Parts are allowed to enter the cell via the input bu€er (I1) and parts leave the cell after completing machining via the output bu€er (O1). Dynamic routing and the performance of automated manufacturing cells Fig. 1. A ¯exible manufacturing cell. The process plan for a part shows one or more sequences of machine visitations, each performing an operation, to completely machine a part. Figure 2 illustrates two parts. Part A has two alternate process plans. It can be processed either in M1-M2-M1 or M2-M1-M2. Part B has only one set of operations in M2-M1, and one routing. We propose to model the controller as a ®nite automata using the underlying theory of Ramadge and Wonham (1987) for modeling and control of discrete event systems based on languages generated by ®nite automata. Brandin (1996) discusses the application of this theory for controllers implemented on Programmable Logic Controller (PLC) platforms. However, his paper does not address issues of deadlock avoidance or system performance. In the following section, we give a brief review of basic concepts for ®nite automata. This will be followed by its application to the cell controller of Fig. 1. 2.1. Some basic concepts of ®nite automata A symbol r represents an event in a system. A string x is a ®nite sequence of events that take place in a system. An alphabet R is a ®nite set of symbols. A language L is a set of strings from some alphabet. A ®nite automaton is formally de®ned by a ®ve-tuple: G ˆ R; Q; d; qo ; Qm †; where Q is the set of states q, R is a ®nite alphabet of events, d: R ´ Q ® Q is the transition function, qo Î Q is the initial state and Qm Ì Q is the set of marked (®nal) 977 states. Throughout this paper we will represent initial states with a double circle and ®nal states with a ®lled circle. Generally d is a partial function de®ned for some R(q) Ì R. G can also be represented as a directed graph with node set Q and an edge q ® q¢ labeled by r for each (r, q, q¢) such that q¢ = d(r,q). L(G) = {x| x Î R*, d(x,q0) Î Q is de®ned}, where x is a string and R* is the set of all strings over the alphabet R. In other words L(G) is the set of all possible sequences of events (strings) which take the initial state to some reachable state in Q. Lm(G) = {x| x Î R*, d(x,q0) Î Qm}. Lm(G) is the marked language generated by G which represents the sequence of events that take the initial state to some marked (®nal) state, Qm. For the ®nite automaton G, Qa = {q Î Q | ($w Î R*) d(w,qo) = q}, i.e., the set of all the states that can be reached from the initial state is called the accessible states subset. Also, for the ®nite automaton G, Qca = {q Î Q | ($w Î R*) d(w,q) = Qm}, i.e., the set of all the states q from which some marked (®nal) state can be reached is called the co-accessible states subset. The ®nite automaton G is said to be ``trim'' if it is accessible (Q = Qa) and co-accessible (Q = Qca). In the theory of supervisory control of Ramadge and Wonham (1987), the uncontrolled behavior of the plant is given by a ®nite automaton that is modi®ed to accept control. This is done by de®ning a set of events, Rc Í R, which accept control. Those that are uncontrollable are represented by Ru, and R ˆ Ru [ Rc . A supervisor is an agent that enables or disables controllable events in the plant such that the language generated satis®es some speci®cations. Formally the supervisor consists of a ®nite automaton S and an output function w (control pattern). S = (S, w), where: S ˆ R; X ; n; xo ; Xm † and w : R  X ! 0: disable; 1: enable† such that w r; x† ˆ 0 or 1 if r 2 Rc and 1 if r 2 Ru : The supervisor and the plant are coupled to form a closed loop system. Assume that at a given time the plant is in state qi and the supervisor is in state xj. A set of events r Î R can occur in the uncontrolled process in state qi. According to the state xj only a subset of the r Î Rc may be permitted. The supervisor generates a control pattern w. This concept of a closed loop system is illustrated in Fig. 3. The closed loop system is denoted by S/G. Two languages generated by S/G are of interest: L(S/G) = L(S) Ç L(G) is the sequences of events of the closed loop system. Lm(S/G) = Lm(S) Ç Lm(G) is the marked sequences of events of the closed loop system. 2.2. The ®nite automata model of the manufacturing cell Fig. 2. Process plans for part types A and B. The ¯exible manufacturing cell model (G) describes the uncontrolled plant behavior. For illustrative purposes, we 978 Fig. 3. Closed loop coupled system. will consider the cell con®guration shown in Fig. 1. The cell has two machines, M1 and M2, a robot for material handling, and input and output bu€ers. Figure 4 is the transition graph for this cell. The states of the plant (Q = {ii, bi, ib, bb}) describe the status of machines in the cell. For example, ``ib'' is the state where M2 is busy and M1 is idle. The events (R = {I1M1, I1M2, M1O1, M2O1}) describe the movement of the part by the robot, which can be controlled by a supervisor that enables or disables the initiation of the event. For example, when the cell is in state ``ii'', with a part in the bu€er, the part can be loaded on either M1 or M2. These events are described as I1M1 and I1M2, respectively. Notice that in state ``bb'' the robot cannot load a new part to the cell. In this state the robot has no location in which to load a new part. The only possible moves that exist are M2O1 and M1O1. If the part on M1 is required to go to M2 next and the part on M2 is required to go to M1 next, the system becomes deadlocked due to the ``circular wait'' condition described in Section 1. In this example qo = ii and qf = ii, qf 2 Qm . In the ®nal state all parts in the cell are cleared. The transition function, d: R ´ Q ® Q de®nes the events that transition the cell among states. For example, in Fig. 4, d(I1M1, ii) ® bi is de®ned. Boucher et al. Each part process plan is modeled as a ®nite automaton. The transition graphs of each automaton for these process plans are shown in Fig. 5. The states of the model describe the processing phase the part is in and the events describe the part movements required between machines. The initial and ®nal states are denoted by subscripts ``i'' and ``f ''. These models will be used to synthesize the supervisor for the cell. The supervisor de®nes the rules that govern the desired behavior of the cell. The part ®nite automatons describe the rules for routing the part through the cell. For example, for Part B, B = (R, B, dB, bi, bf), where B is the part states (B = {bi, b1, b2, bf}), bi and bf are the initial and ®nal states, and R is the alphabet as previously de®ned. The transition function, dB: R ´ B ® B, De®nes the events that transition the part from state to state. Thus, dB(M2M1, b1) ® b2. When the rules that govern the routings of all of the parts under consideration are combined together, a proper supervisor for the cell is synthesized. The procedure for doing this is described in the next section. 2.4. Creating the supervisory controller The ®nite automata models of the uncontrolled plant and the process plans are used to de®ne the controller based on the common language, R. This controller restricts the events that are allowed to occur at any time based on the current states of the plant (qc) and process plans (xc), and whether or not the event is a legal transition in both the plant model (G) and the process plan model (S). There are two steps in the process of creating this controller: (i) shu‚ing the process plans; and (ii) coupling the shu‚ed process plans with the plant model. Step 1, shu‚ing (denoted by symbol ``||'') (Ramadge and Wonham, 1987), is taking the Cartesian product of the remaining states of the process plans of the parts 2.3. The ®nite automata models of the process plans The process plan of a part explicitly de®nes the possible routes a part may take for complete processing. The process plans of two parts, A and B, are illustrated in Fig. 2. Part A has routing ¯exibility. It has to visit M1 and M2, but one of them twice. Part B must visit M2 and M1 in that order. Fig. 4. Transition graph for cell in Fig. 1. Fig. 5. Finite automata for part types A and B. 979 Dynamic routing and the performance of automated manufacturing cells currently under consideration by the controller. When the supervisor is informed that a new part is ready to enter the cell, the ®nite automata model of that part is shu‚ed with the ®nite automata models of the parts already in the cell. This is illustrated in Fig. 6, where it is assumed that we are in a state of the system when part A is in state a1 and part B is in the input bu€er (xc = a1bi). The transition graph of the shu‚e of parts A and B shows all the possible movements (events) that take the parts from one state to another. In order to keep track of which part is moved, we have modi®ed event names to include part identi®ers. The ®nal state is reached when both parts have cleared the cell (Xm = afbf). An important point to note about Fig. 6 is that it contains some illegal states. For example, state a3b1 is a state in which both part A and part B are on M2. This should not be allowed based on the rules governing the operation of the cell. Also, state a1b1 is the state in which part A is on M1 and should next be routed to M2. However, part B is on M2 and should next be routed to M1. This is a deadlock state. In order to avoid these unwanted states, it is necessary to couple the process plan models to the plant model. This is the second step in creating the supervisory controller. Step 2 in creating the supervisor is the coupling of Fig. 6 with the cell ®nite automata. The coupled supervised discrete event process is de®ned as: S=G ˆ R; Q  X ; d  n; xc  qc ; Xm  Qm †; where the product operation is the Cartesian product and qc is the current state of the cell model. The transition graph for S/G is shown in Fig. 7. Figure 7 allows only the legal moves that should be allowed to occur in the system. The manner in which the act of coupling restricts the supervisor to process only legal moves can be explained as follows. The coupled system transition matrix (d ´ n) contains only the events satisfying both the cell transition Fig. 7. Transition graph of coupled supervisor and plant model. matrix and the process plan transition matrix. So, as previously pointed out, state a3b1 of Fig. 6 is a state in which both part A and part B are on M2. In Fig. 6 this state is reachable from state a3bi by event I1M2,B. However, in Fig. 7, the coupled system shows state a3bi.ib, indicating that there is already one part on M2 (part A). In the cell ®nite automata, d does not de®ne the event I1M2 when the cell is in state ib (see Fig. 4). Therefore, the event is not allowed from state a3bi.ib in the coupled system. This is why Fig. 7 does not contain this transition at that state. From the transition graph we can determine: Lm S=G† ˆ ‰ M1M2; A M2M1; A M1O1; A I1M2; B M2M1; B M1O1; B†; M1M2; A M2M1; A I1M2; B M1O1; A M2M1; B M1O1; B†Š: The language Lm(S/G) takes the coupled system from an initial state to the combined ®nal state of all the parts. Since all the parts have completed processing in their ®nal state, the strings in Lm(S/G) are deadlock-free execution sequences. Each string is a path from the initial state of the transition digraph (a1bi.bi) to the marked state (afbf.ii). Finally, the control pattern, w, for the supervisor synthesized above is shown in Table 1. The control pattern shown in Table 1 restricts the movement of parts in the cell to deadlock-free sequences. Assume for example that a new part is queued for production (state a1bi.bi). In Table 1, the loading event I1M2 Table 1. Supervisory control pattern, w State Fig. 6. Transition graph of the shu‚e of parts A and B from initial state a1bi. a1bi.bi a3bi.ib a5bi.bi afbi.ii a5b1.bb afb1.ib afb2.bi I1M1 I1M2 M1M2 M2M1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 M2O1 M1O1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 980 is disabled by the control pattern in state a1bi. If this event is allowed to happen, the cell would become deadlocked (state a1b1.bb). The deadlock situation would arise because Part B would be on M2 and it can only go to M1. However M1 is occupied by Part A and Part A needs to go to M2. With regard to our control problem, we should point out that we do not ``force'' a particular path. The controller allows ``opportunistic routing'' of the parts based on which part is available to be moved and whether or not the controller has enabled the move in the supervisory control pattern, w. The robot is allowed to perform moves that are enabled. Therefore, if a new part is in the input bu€er it is available to be moved. However, the robot will perform the move only if the supervisor has indicated that the move is enabled at that point in time. 3. Experimental design The real-time controller designed in Section 2 is a maximally permissive controller that avoids deadlock and accommodates routing ¯exibility. The objective of this experiment is to demonstrate this controller and to compare its e€ects on schedules with routing ¯exibility versus no routing ¯exibility. The following performance measures will be compared: average ¯ow time, minimum ¯ow time, maximum ¯ow time, makespan, and machine utilization. An experimental tool was built that is composed of two software modules: (i) a simulation model of a four machine, one robot direct address manufacturing cell; and (ii) a controller based on the ®nite automata model shown in Section 2. The simulation model is programmed using Arena software and the controller is written in the C programming language and communicates with Arena using Windows DDE. This experimental tool emulates the interaction between a physical cell and its supervisory controller. A block diagram showing the relationship between the controller and the simulator is shown in Fig. 8. Each time the simulation model completes the execution of an event, the event r is reported to the controller. The controller then updates the current state of the transition graph of the coupled system (Fig. 7). Based on the control pattern (Table 1), the controller then sends a message to the simulator indicating the allowable next actions, w. Fig. 8. Software modules for experimental tool. Boucher et al. Therefore, each part movement that the simulator wants to execute is conditioned on being given permission by the controller. In this fashion the controller ensures that the simulator does not perform a move that is not allowable based on the control pattern. The supervisor, i.e., the coupled system (Fig. 7) and the supervisory control pattern (Table 1), is updated each time a new part enters the input bu€er of the cell (enters the initial, or subscript i state). A new control pattern, w, is determined to allow the new part to be loaded. The simulator will either load the new part, if allowed at the time, or execute the next allowed event on its event calendar. The following three variables were used as the controlling parameters to design the cases for the set of experiments: 1. Number of unique part types. 2. Number of parts simultaneously considered for control. 3. Routing path ¯exibility. The domain of the experimental space is shown in Fig. 9. The ``number of unique part types'' refers to the population of parts from which random arrivals are generated. Four levels were considered: 2, 5, 10, and 20. Each part population is used to generate random arrivals to the cell from that part population. Therefore, these four levels re¯ect di€erences in the variety of part types that the cell is handling. The part population was constructed by randomly generating 20 parts and three attributes: (i) number of machining operations; (ii) machines assigned to those operations; and (iii) processing times for each operation. From this population, two sets were de®ned. One in which alternative routing was possible and one with only a single route. Table 2 summarizes the 20 part types. From the 20 randomly generated part types, subsets of 10, 5 and 2 were randomly selected to construct the other population sets. The ``number of parts simultaneously considered for control'' refers to how many of the randomly generated parts are simultaneously being processed in the cell or available in the input bu€er. Two cases were considered: four and ®ve parts. So, for example, if ®ve parts are Fig. 9. Variables used in experimental design. 981 Dynamic routing and the performance of automated manufacturing cells Table 2. Population of parts Part number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Operation Processing time Alt #1 Alt #2 1 2 3 4 1 2 3 1 2 3 1 2 1 1 2 1 2 3 1 2 3 4 1 2 3 4 1 2 1 1 2 1 1 2 1 2 1 2 1 1 2 3 1 2 3 1 43 32 20 35 20 63 36 38 36 76 56 66 26 72 77 59 77 52 77 76 56 40 55 41 32 72 35 64 43 56 53 70 72 76 29 37 49 28 53 49 61 41 27 61 33 74 M2 M1 M3 M4 M3 M4 M1 M1 M2 M4 M2 M4 M3 M1 M3 M1 M2 M3 M2 M3 M4 M1 M1 M2 M3 M4 M2 M4 M2 M3 M1 M3 M4 M2 M4 M1 M4 M3 M4 M2 M4 M1 M4 M1 M2 M4 M3 M4 M2 M1 M1 M2 M3 M4 M3 M1 M3 M1 M4 M4 M2 M3 M4 M1 M4 M1 M2 M3 M3 M4 M1 M2 M3 M1 M4 M4 M2 M1 M1 M3 M2 M3 M2 M1 M3 M1 M3 M2 M2 M3 M4 M1 considered and three of the ®ve parts are in machining, the two remaining parts in the input bu€er are being evaluated for loading on the remaining available machine. As a part ®nishes processing, another is loaded into the input bu€er. The third dimension, ``routing path ¯exibility'', is the variable of interest for comparison purposes. The single routing path treatment ®xes the process plan so that the next move of the part must be made to one speci®c machine. The multiple routing path treatment allows the part to be moved to either one of two speci®c machines in the cell. Therefore, in Table 2, part 1 may have operation 1 performed on either M2 or M3, operation 2 on either M1 or M4, and so on. In Table 2, Alt #1 is used for the single routing path case. Twenty replications (cases) were run for each cell of Fig. 9. The part sequence for each replication was generated by taking a random sample of size 25 from the relevant population of parts (2, 5, 10, 20). Since each sample used a di€erent random number seed, the 20 replications (cases) provided 20 unique sequences of 25 randomly selected parts. The 20 replications of the 2 ´ 4 pairings of four and ®ve parts considered and number of part types were then run for the two treatments of interest: single routing versus multiple routing. This yielded 20 pairwise comparisons in each cell that could be used to analyze differences between the two treatments. The statistical analysis of results is given in the next section. 4. Experimental results 4.1. Routing ¯exibility versus single routes The 20 pairwise comparisons in each cell were subjected to paired-sample t-tests on the di€erence between means, ld. The test considers the hypothesis: H0 : ld ˆ 0; HA : ld 6ˆ 0; where ld = ls ) lm and s denotes the single-routing treatment and m denotes multiple-routing treatment. The test statistic is: d p ; t0 ˆ Sd = n where: n 1X dj ; dj ˆ xj s† ÿ xj m†; d ˆ n jˆ1 2P P 2 31=2 n n 1 2 ÿ d d jˆ1 j 7 6 jˆ1 j n Sd ˆ 4 5 : nÿ1 The test statistic for a two-tail test with 19 degrees of freedom and a 99.9% con®dence interval is 3.883. Table 3 shows the results on regular measures of performance: mean ¯ow time, min ¯ow time, max ¯ow time, and makespan. In most cases, the null hypothesis is rejected above the 99% level of signi®cance. Except for min ¯ow time, the multiple routing treatments are signi®- 982 Boucher et al. Table 3. Single versus multiple process plans Four parts simultaneously controlled Five parts simultaneously controlled Part types Mean, d Standard deviation, Sd t-statistic C.I. Mean ¯ow time 20 59 22 11.8 * 10 66 27 10.8 * 5 68 25 12.4 * 2 121 22 24.7 * 20 67 38 7.8 * 10 80 36 9.9 * 5 64 28 10.4 * 2 145 27 24.3 * Part types Mean, d Standard deviation, Sd t-statistic C.I. Minimum ¯ow time 20 10 7 5 18 20 1.6 1.2 insig. insig. 5 0 0 ± insig. 2 21 8 12.4 * 20 4 22 0.8 insig. 10 8 24 1.4 insig. 5 )2 8 1.0 insig. 2 23 4 22.8 * Part types Mean, d Standard deviation, Sd t-statistic C.I. Maximum ¯ow time 20 10 164 172 118 179 6.2 4.3 * * 5 137 83 7.4 * 2 269 177 6.8 * 20 212 113 8.4 * 10 254 270 4.3 * 5 193 173 5.0 * 2 357 268 6.0 * Part types Mean, d Standard deviation, Sd t-statistic C.I. Makespan 20 397 146 12.2 * 5 473 163 13.0 * 2 816 148 24.6 * 20 402 199 9.0 * 10 467 202 10.4 * 5 387 135 12.8 * 2 807 141 25.7 * 10 474 139 15.3 * * The t-statistic for 99.9% con®dence level is 3.883 for 19 degrees of freedom cantly better than the single routing treatments both for four or ®ve parts considered simultaneously. When four parts are simultaneously considered for control, the order of magnitude of the improvement on each criterion is shown in Table 4. In general, for this experiment, multiple process plans provide between 24±44% improvement over single process plans on regular measures of performance except for min ¯ow time. The greatest percentage improvements are made in the maximum ¯ow time. Decreased maximum ¯ow time indicates that not only are parts ¯owing through the system more quickly but also no one part is getting stuck in the system for extended periods of time. The primary factor that accounts for the superior performance of multiple process plans is the fact that assigning jobs to alternate machines reduces the processing time on the bottleneck machine in the cell. In these simulations the total machining times were the same in each pairwise trial. Therefore, both the single process plans and the multiple process plans are required to have the same total machining time. The advantage of the multiple process plans is that the machining can be assigned more equally among machines, better balancing the workload of the machines in the cell. This point is shown very well in Fig. 10, which is a comparison of machine utilization for some typical cases with and without routing ¯exibility. 4.2. Considering more parts for simultaneous control It can be argued that better machine utilization can be obtained by increasing the selection of jobs to move into the cell when machines are available. This improved machine Table 4. Comparison of average results; (4 parts simultaneously controlled) 20 10 5 2 Mean ¯ow time Single process plan Multiple process plan Percent improvement (%) 243 184 24 279 213 24 248 180 27 314 193 38 Minimum ¯ow time Single process plan Multiple process plan Percent improvement (%) 41 35 17 58 53 9 70 70 0 132 111 16 Maximum ¯ow time Single process plan Multiple process plan Percent improvement (%) 564 399 29 645 472 27 519 382 27 609 340 44 Makespan Single process plan Multiple process plan Percent improvement (%) 1618 1221 25 1888 1414 25 1658 1185 29 2080 1265 39 983 Dynamic routing and the performance of automated manufacturing cells Fig. 10. Average machine utilization (four parts simultaneously controlled). utilization would result in shorter makespans. We conjectured that an improvement would be possible for both the case of single route and multiple route parts if more parts were simultaneously considered for loading in the cell. Since there are four machines in the cell, considering more than four parts provides more options for the next part to be introduced to the cell. However, as shown in Table 5, this was not the case. The e€ect of considering more jobs simultaneously did not improve the performance of the cell under multiple routing. Going from four to ®ve parts considered simultaneously resulted in no signi®cant performance improvement when the parts had multiple routings. It is important to note that the performance of single routing plans when considering ®ve or six parts simultaneously is still signi®cantly worse than the performance of multiple routing plans when considering four parts simultaneously. This is indicated in the last rows of Table 5. 5. Computational issues Finite automata models tend to grow exponentially in state space as problem size grows. This occurs because the shu‚ing of the states of the ®nite automata of the new part, n1, with the ®nite automata of the parts in the system, n2, yields the Cartesian product, n1 ´ n2, for the shu‚ed system. In this application, the cell size (number of machines) and the routing requirements (number of operations and number of parts being simultaneously considered) govern problem size. Since we are addressing real-time control, it is clear that the state space size and computation time should be addressed. Table 5. Comparison on mean makespan for number of parts considered for processing Part types 20 10 5 2 Multiple routing: ®ve versus four parts Change in mean 6 55 t-statistic 0.2 1.7 C.I. insig. insig. 95 5.7 * )4 0.2 insig. Single routing: ®ve versus four parts Change in mean 11 48 t-statistic 0.5 1.6 C.I. insig. insig. 10 0.6 insig. )13 1.8 insig. Single routing: six versus ®ve parts Change in mean )7 )10 t-statistic 0.3 0.4 C.I. insig. insig. 12 1.0 insig. 10 1.7 insig. Multiple routing (four parts) versus single routing (six parts) Change in mean )401 )512 )495 )813 t-statistic 15.0 12.4 16.4 25.6 C.I. * * * * * The t-statistic for 99.9% con®dence level is 3.883 for 19 degrees of freedom 984 Boucher et al. 5.1. Controlling state space size In this research we propose a method for limiting the state space the controller must consider by an adjustment in the manner in which the cell and the supervisor are coupled. When a new part is considered for processing in the cell, the ®nite automata model of the new parts process plan needs to be shu‚ed with the ®nite automata models of the parts already in the cell to obtain a new supervisor S. This has been demonstrated in Section 2.4 with an example. Shu‚ing the ®nite automata models of parts leads to exponential growth of state space when many parts are simultaneously considered for processing. In order to keep the size of the state space to a level that can be evaluated in real time, we use the already existing coupled system model to determine the new event sequences that allow all the parts in the cell to be completely processed. The state space of the coupled system is much smaller compared with the state space of the supervisor obtained by shu‚ing. We will formally prove that using the coupled system for generating the supervisor is not more restrictive (will not restrict the marked language) then the supervisor obtained by the methodology described in Section 2.4. Therefore, this approach to state space reduction saves computational time without restricting the marked language of the coupled system. Fig. 11. Transition graph of S0 . Consider another part of part type B that is going to be loaded into the cell at this time. The transition graph of the ®nite automata model SP jjS 0 is depicted in Fig. 12. When SP jjS 0 is coupled with the plant model G as described in Section 2.5, the resulting transition graph of the ®nite automata model is illustrated in Fig. 13. Theorem 1. Let SP represent the ®nite automaton model of a new part and S be the ®nite automaton generated by shu‚ing the process plans of parts already in the cell. Also let S 0 be the generator for Lm S=G† 2 R . A supervisor obtained by SP jjS 0 is not more restrictive then a supervisor obtained by SP jjS. Proof by contradiction. Assume that SP jjS 0 is more restrictive than SP jjS contradicting the theorem stated. Then the following relationship can be established regarding the marked languages of the supervisors coupled with the plant model. Fig. 12. Transition graph of SP jjS 0 . ÿ
Lm SjjSp †=G  Lm S 0 jjSP †=G†: The above statement is true if there exists a string w 2 R such that w 2 Lm S† and w 2 Lm G† but w 2 = Lm S 0 †. 0 However, since S is the generator for Lm S=G†, then Lm S 0 † ˆ Lm S=G† ˆ Lm S† \ Lm G†. Clearly, any string that is a member of Lm S† and Lm G† must also be included in Lm S 0 †. Therefore such a string w cannot exist j and SP kS 0 is not more restrictive than SP jjS. We will illustrate the above theorem with an example. Consider a time when the coupled system in the example in Section 2 has reached state a5b1.bb. The ®nite automata corresponding to S 0 at this point is shown below in Fig. 11. Fig. 13. Transition graph of S 0 jjSP †=G. Dynamic routing and the performance of automated manufacturing cells It is left to the reader to verify that the same event sequence is obtained by using the methodology described in Section 2. We only note that the size of the supervisor S obtained by the traditional approach of shu‚ing the ®nite automata models of the parts individual process plans would lead to 8 ´ 4 ´ 4 = 128 states for the three parts simultaneously considered for processing. On the other hand as seen in Fig. 12, the state space is only 16 when shu‚ing Sp jjS 0 . It is important to note that the amount of reduction in state space cannot be generalized. The reduction depends on factors such as the ¯exibility related to parts and the time that a new part is considered for processing. 5.2. Computer algorithms In this section we will brie¯y describe the programmed algorithms used in implementing the controller described in Section 2.4. One of the input ®les used in these computations is a ®le that relates the ®nite automata model of the part process plan to the state of the cell. This is shown for parts A and B in Fig. 14. These ®les are constructed by combining the part states of Fig. 5 with the corresponding plant states of Fig. 4. The plant states are the tuple (M1 M2). As explained in Section 2.4, the marked language of the coupled system, Lm(S/G), determines the control pattern for each state of the system. A Depth First Search algorithm (Tarjan, 1972), which is widely used in ®nding routes through directed graphs is used to determine the marked language of the coupled model. The algorithm begins at the initial node and evaluates the nodes adjacent to the initial node. If the node being evaluated is illegal, it is deleted from the graph and no further fathoming of its successor nodes is considered. The part process plan/plant state list is used during the shu‚ing process in order to identify illegal states. Illegal states are states in which more than one part is occupying the same machine. These states are identi®ed by taking the bitwise logical AND of the plant states corresponding to the nodes of the process plans that are being shu‚ed. Fig. 14. Part process plan/plant state lists for parts A and B. 985 If the logical AND does not return a zero, the state is not legal. So, for example, plant_state(a1) AND plant_ state(b1) = (1 0) AND (0 1) = (0 0) is legal. In that state (a1b1), part A is on M1 and part B is on M2. However, plant_state(a2) AND plant state(b1) = (1 0) AND (1 0) = (1 0) is not legal. In this state both part A and part B would be occupying M2 simultaneously. Determining illegal nodes as described above is analogous to the coupling process described in Section 2.4. Instead of using the coupled system transition matrix (d ´ n) to check if an event is enabled, a simple AND operation determines if the state that will be reached after executing the event is physically possible in the cell. The next adjacent legal node is then visited and the process continues until all marked sequences of the coupled model are found. The completion of this process for the example problem yields the generator of the marked language as shown in Fig. 15. If another part arrives, it is the generator depicted in Fig. 15 that is shu‚ed and coupled with the newly arrived part. This process was explained in Section 5.1. 5.3. Computation time Employing the state space reduction technique of Section 5.1 in updating the coupled system transition graph yields computation times that are realistic for supervisory controllers of manufacturing cells. The longest computational cycle for the controller occurs when a new part enters the input bu€er, requiring that the transition graph and the supervisory control pattern be recomputed. In all other circumstances, the computational time between receiving event r and returning the control rule w is trivial. When a new transition graph and control rule are calculated, the computational time is proportional to the number of states (nodes) in the transition graph of the shu‚ed model and the amount of time required to ®nd the marked language of the coupled model. Fig. 15. Generator for the marked language of the coupled model. 986 Boucher et al. Table 6. Experimental problem state space (400 MHz Pentium II, 128 MB RAM) States generated in shu‚ing Transitions generated in shu‚ing States for the generator of Lm(S/G) Transitions for the generator of Lm(S/G) CPU time, shu‚ing (seconds) CPU time, determining Lm(S/G) (seconds) CPU time, 1st deadlock-free path (seconds) Total CPU time, rows 5 + 6 (seconds) Average Minimum Maximum 1338 5193 554 1510 0.01 0.23 <0.01 0.24 212 672 113 284 <0.01 <0.01 <0.01 <0.01 4710 19 616 1731 4683 0.06 1.26 <0.01 1.32 In the experiments of Section 3, the largest problem size considered was a four-machine cell, ®ve parts considered simultaneously, with multiple routings for each part. Table 6 shows the average, minimum, and maximum state spaces encountered for this problem size. In Table 6, rows 1 and 2 show the state space size generated during the shu‚ing process. Row 5 is the CPU time required to perform shu‚ing, which includes labeling the shu‚ed states as either legal or illegal. Rows 3 and 4 show the state space size for the generator of the marked language. The reduction in state space results from deleting the illegal states and the deadlock states. Row 6 is the CPU time required for this step. The Depth First Search algorithm is searching for legal and deadlock free paths from the initial node to the ®nal node of the graph, where all parts under consideration are completely processed. Row 7 is the CPU time for ®nding the ®rst legal and deadlock free path. Row 7 has signi®cance with respect to real time performance, since the existence of a single deadlock-free sequence is enough to enable the ®rst event in the sequence; i.e., to give permission for the new part to enter the cell. Of course, all the marked sequences must eventually be found in order to prepare the supervisor for the next request to load the cell with a new part. Note that the state space and CPU times are well within that which is required for real time control. However, due to the fact that state space grows exponentially with increasing cell size, these results cannot be expected to pertain to larger systems. Table 6 indicates that, for problems of the size considered here, the proposed methodology can be implemented in real time. 6. Conclusion In this paper we addressed some issues related to realtime operational control of automated manufacturing cells. In particular, we have implemented a maximally permissive deadlock-free controller that can incorporate routing ¯exibility. The controller makes the decision on what machine should perform the next operation on a given part in real time by considering the current state of the cell and the routing requirements of parts. We have conducted experiments to investigate the e€ects of routing ¯exibility on the cell's performance as well as the computational time associated with the control algorithm. Our results show that incorporating dynamic routing into control decreases average ¯ow time and makespan. This indicates that both for low variety/high volume and high variety/low volume cells considering routing ¯exibility results in considerable gains in performance. The greatest improvements were in the maximum ¯ow time, indicating that parts are not getting stuck in the cell for extended periods of time. Minimizing maximum ¯ow time is very important for systems that work with tight due dates and a high number of part types. From our results we can conclude that one practice to improve the performance of manufacturing cells is to incorporate routing ¯exibility into real time operational control of the cell. When this is coupled with more ecient scheduling policies appropriate to ¯exible manufacturing systems, further increases in resource utilization and system performance would be expected. References Abdin, M.F. (1986) Solution of scheduling problems of job shop type FMS with alternative machine tools. Computers and Industrial Engineering, 11, 214±245. Al-Quattan, I. (1990) Designing ¯exible manufacturing cells using branch and bound method. International Journal of Production Research, 28(2), 325±336. Askin, R.G., Selim, H.M. and Vakharia, A.J. (1997) A methodology for designing ¯exible cellular manufacturing systems. IIE Transactions, 29(7), 599±610. Benjaafar, S., Morin, T.L. and Talavage, J.J. (1995) Strategic value of ¯exibility in sequential decision making. European Journal of Operations Research, 82(3), 438±457. Benjaafar, S. and Ramakrishnan, R. (1996) Modelling, measurement and evaluation of sequencing ¯exibility in manufacturing systems. International Journal of Production Research, 34(5), 1195±1220. Boucher, T.O. and Muckstadt, J.A. (1985) Cost estimating methods for evaluating the conversion from a functional layout to group technology. IIE Transactions, 17(3), 268±276. Dynamic routing and the performance of automated manufacturing cells Brandin, B.A. (1996) The real-time supervisory control of an experimental manufacturing cell. IEEE Transactions on Robotics and Automation, 12(1), 1±14. Byrne, M.D. and Chutima, P. (1997) Real time operational control of an FMS with full routing ¯exibility. International Journal of Production Economics, 51, 109±113. Dahel, N.E. and Smith, S.B. (1993) Designing ¯exibility into cellular manufacturing systems. International Journal of Production Research, 31(6), 933±945. Dutta, A. (1990) Reacting to scheduling exceptions in FMS environments. IIE Transactions, 22(4), 300±314. Ezpeleta, E., Colom, J.M. and Martinez, J. (1997) Petri net based deadlock prevention policy for ¯exible manufacturing systems. IEEE Transactions on Robotics and Automation, 11(2), 173±184. Fanti, M.P., Maione, B., Mascolo, B. and Turchiano, B. (1997) Eventbased feedback control for deadlock avoidance in ¯exible production systems. IEEE Transactions on Robotics and Automation, 13(3), 347±363. Ghosh, S. and Gaimon, C. (1992) Routing ¯exibility and production scheduling in a ¯exible manufacturing system. European Journal of Operational Research, 60, 344±364. Jain, A.K. and Elmaraghy, H.A. (1997) Production scheduling and rescheduling in ¯exible manufacturing. International Journal of Production research, 35(1), 281±309. Lawley, M., Reveliotis, S. and Ferreira, P. (1997a) Flexible manufacturing system structural control and the neighborhood policy: part 1, correctness and scalability. IIE Transactions, 29, 877±887. Lawley, M., Reveliotis, S. and Ferreira, P. (1997b) Flexible manufacturing system structural control and the neighborhood policy: part 2, generalization, optimization, and eciency. IIE Transactions, 29, 889±899. Lawley, M.A., Reveliotis, S. and Ferreira, P.M. (1998) A correct and scaleable deadlock avoidance policy for ¯exible manufacturing systems. IEEE Transactions on Robotics and Automation, 14(5), 796±809. Lee, D.Y. and Di Cesare, F. (1994) Scheduling ¯exible manufacturing systems using Petri nets and heuristic search. IEEE Transactions on Robotics and Automation, 10(2), 123±132. Lin, G.Y.-J. and Solberg, J.J. (1991) E€ectiveness of ¯exible routing control. International Journal of Flexible Manufacturing Systems, 3, 189±211. Nasr, N. and Elsayed, E.A. (1990) Job shop scheduling with alternative machines. International Journal of Production Research, 28(9), 1595±1609. Nof, S.Y., Barash, M.M. and Solberg, J.J. (1979) Operational control of item ¯ow in versatile manufacturing systems. International Journal of Production Research, 17, 479±489. Rachamadugu, R., Nandkeolyar, U. and Schreiber, T. (1993) Scheduling with sequencing ¯exibility. Decision Sciences, 24(2), 315±342. Rachamadugu, R. and Stecke, K.E. (1994) Classi®cation and review of FMS scheduling procedures. Production Planning and Control, 5(1), 2±10. Rajamani, D., Singh, N. and Aneja, Y.P. (1990) Integrated design of cellular manufacturing systems in the presence of alternative process plans. International Journal of Production Research, 28(8), 1541±1554. Ramadge, P.J. and Chase, C. (1992) On real-time scheduling policies for ¯exible manufacturing systems. IEEE Transactions on Automatic Control, 37, 491±496. Ramadge, P.J. and Wonham, W.M. (1987) Supervisory control of a class of discrete event processes. SIAM Journal of Control and Optimization, 25(1), 206±230. Raman, N., Rachamadugu, R.V. and Talbot, F.B. (1989) Real-time scheduling of an automated machining center. European Journal of Operational Research, 40, 222±242. 987 Ramaswamy, S.E. and Joshi, S.B. (1996) Deadlock-free schedules for automated manufacturing workstations. IEEE Transactions on Robotics and Automation, 12(3), 391±400. Reveliotis, S.A., Lawley, M.A. and Ferreira, P.M. (1997) Polynomialcomplexity deadlock avoidance policies for sequential resource allocation systems. IEEE Transactions on Automatic Control, 42(10), 1344±1357. Sankaran, S. and Kasilingam, R.G. (1993) On cell size and machine requirements planning in group technology systems. European Journal of Operational Research, 69, 373±383. Sawik, T. (1990) Modeling and scheduling of a ¯exible manufacturing system. European Journal of Operational Research, 45, 177±190. Stecke, E.K. (1992) Procedures to determine part mix ratios for independent demands in ¯exible manufacturing systems. IEEE Transactions on Engineering Management 39(4), 359±369. Stecke, E.K. and Raman, N. (1994) Production planning decisions in ¯exible manufacturing systems with random material ¯ows. IIE Transactions, 26(5), 2±17. Stecke, E.K. and Raman, N. (1995) FMS planning decisions, operating ¯exibilities, and system performance. IEEE Transactions on Engineering Management, 42(1), 82±89. Stecke, K.E. and Solberg, J.J. (1981) Loading and control policies for a ¯exible manufacturing system. International Journal of Production Research, 19, 481±490. Sun, T.-H., Cheng, C.-W. and Fu, L.-C. (1994) A Petri net based approach to modeling and scheduling for an FMS and a case study. IEEE Transactions on Industrial Electronics, 41(6), 593± 600. Tarjan, R.E. (1972) Depth ®rst search and linear graph algorithm. SIAM Journal of Computing, 1(2), 146±160. Tilsley, R. and Lewis, F.A. (1977) Flexible cell production systems ± a realistic approach. Annals of CIRP, 25, 269±271. Viswanadham, N., Narahari, Y. and Johnson, T.L. (1990) Deadlock prevention and deadlock avoidance in ¯exible manufacturing systems using Petri net models. IEEE Transactions on Robotics and Automation, 6(6), 713±723. Wilhelm, W.E. and Shin, H.-M. (1985) E€ectiveness of alternative operations in a ¯exible manufacturing system. International Journal of Production Research, 23(1), 65±79. Wysk, R.A., Yang, N.S. and Joshi, S. (1991) Detection of deadlocks in ¯exible manufacturing cells. IEEE Transactions on Robotics and Automation, 7(6), 853±858. Yalcin, A. and Boucher, T.O. (2000) Deadlock avoidance in ¯exible manufacturing systems using ®nite automata. IEEE Transactions on Robotics and Automation, Forthcoming. Yamagata, K., Tamura, H. and Hatono, I. (1991) Modeling and online scheduling of ¯exible manufacturing systems using stochastic Petri nets. IEEE Transactions on Software Engineering, 17, 126± 132. Biographies Thomas O. Boucher is Professor of Industrial Engineering at Rutgers University. He holds a B.S. in Electrical Engineering from the University of Rhode Island, an M.B.A. in Finance from Northwestern University, and a M.S. and Ph.D. in Industrial Engineering from Columbia University. His research and teaching interests include computer automation and computer integration in manufacturing, production planning and control, and engineering and industrial economics. He is the author of the textbook Computer Automation in Manufacturing (Chapman & Hall, 1996) and co-author of Analysis and Control Production Systems (Prentice-Hall, 1994). Professor Boucher is a senior member of IIE, IEEE, and SME. 988 Ali Yalcin received his B.S. and M.S. degrees in Industrial and Systems Engineering from Rutgers University, New Brunswick New Jersey in 1995 and 1997. He is currently a Doctoral student and research assistant at Rutgers University. His research areas are modeling, analysis, control and scheduling of automated manufacturing systems and manufacturing information systems. He is a student member of the IEEE. Boucher et al. TsuTa Tai is a Senior System Analyst at Aspentech, Supply Chain Division (Formerly known as Chesapeake Decision Science). He holds a M.S. in Computer Science from Rochester Institute of Technology. He is currently working on his M.S. degree in Industrial Engineering at Rutgers University.