## 1. Introduction

FMS (flexible manufacturing system) is composed of a set of versatile machines, zig and fixture, and automatic transport system for moving parts between each job. In FMS, one of the important subjects is to formulate the general cyclic state-scheduling problem to minimize the WIP in order to satisfy economical constraints. Various methods have been proposed by researchers (Zuberek, 1987; Korbaa, 1997; Richard, 1998; Murata,1989; Kondratyev, 1996; Hwang, 1997; Liu, 1999; Lee, 2004)) to solve this problem. Hillion (Hillion, 1987) proposed a heuristic algorithm based on the computation of the degree of feasibility after giving a Petri net (PN) model of the system. Also, Valentin (Valentin, 1994) improved this algorithm by using Timed hybrid Petri nets and by introducing available intervals concept. The problem was that this algorithm could not guarantee the feasibility of the solution in one run. Korbaa (Korbaa, 1997) developed an algorithm to find near-optimal solution using the regrouping algorithm. Korbaa tried to get near-optimal solution and to minimize the WIP. For getting an optimal solution long computational time has been required. This means that all these methods have the problem of complexity and computational time. To simplify the calculation process in the scheduling problem and to make shorter computational time for getting many feasible solutions, we consider unfolding Petri nets to analyze the sequence process and to explain the reduced process. We call “unfolding” a PN unfolding, which has the reachability properties of the original net. Structural analysis on “unfolding” is much easier than on the initial model. The advantage of unfolding is that the state space explosion can be avoided since it is based on partial order semantics. To reduce the processing time, we consider an algorithm to select an environment of a shared resource, which has priority over the other ones, using the transitive matrix. In our case, the system has been analyzed to get the best possible solutions based on this environment of shared resource. The model has been divided into slices and create PN slice using this concept. The properties of a PN can be classified into categories: behavioral and structural properties. The behavioral properties are investigated in association with the marking of PN, e.g., reachability, boundness and liveness (Liu, 1999). Both transition and place invariants belong to structural properties in PN. If the behavioral properties used by the transitive matrix are exhibited, it could be easier to analyze the system after slicing off some subnets.

This paper is organized as follows: some definitions of Time Petri Nets(TPN) and unfolding are given in Section 2, and time Petri net slice is presented in Section 3, The scheduling objectives and outline the problems arising during the transformation of the initial model into an unfolding TPN are described in Section 4. In section 5, we introduce an illustration model for FMS, and specially emphasize the different ways of obtaining a closed loop model. In section 6, we are showing the benchmarking resultants after analyze using the performance evaluation factors. A conclusion and some perspectives will end this paper.

## 2. Basic notions of time Petri nets and slices

In this section certain terms that are often used in this paper are defined (Best,1990; Carlier, 1988; Camus, 1997; Esparza, 1996; Julia, 1995; Lee, 1995; Lee, 2004; Lee, 2006; Liu,1999; Murata, 19875; Taubin, 1997).

Let N=<P, T, I, O, Mo,>be a Time Petri Nets, where P is the set of places (m elements), T is the set of transitions (n elements), and ^{} is the input function, O: T->P^{} is the output function.

A transition t T is enabled at a marking M’ = M – ^{}t + t^{}, where ^{}t represents the incoming weights of the fired transition and t^{} the outgoing weights of the fired transition.

We denote by M (t>M’. The set of reachable marking of N is the smallest set (Mo> containing Mo and such that if M (Mo> and M (t>M’ (for some t T) then M’ (t>Mo. A Time Petri Nets N is safe if for every reachable marking M, M(P) {0,1}; and bounded if there is k N such that M(P) {0,…,k}, for every reachable marking M. The set of successors of a node x P T is x ={yP T;(x,y) F: I O}, and the set of its predecessors is ^{}x={y P T; (y,x) F: I O}.

A Time Petri nets N_{S}=<P_{S},T_{S},F_{S},M_{S},_{ S}>,where P_{S} P, T_{S} T, F_{S}F,M_{S} (Mo> and _{S} then we can say that N_{S} is sub-net of N.

The number of occurrences of an input place P_{i} in a transition t_{j} is given by #(P_{i},I(t_{j})), and the number of occurrences of an output place P_{i} in a transition t_{j} is given by #(P_{i},O(t_{j})).

The matrix of the PN structure, S is S=<P,T,C^{-},C^{+}>, where P,T are the finite set of places and transitions, respectively. C^{-} and C^{+} are matrices of m rows (one for each place) by n columns (one for each transition) defined by:

And the incidence matrix C is given by C=C^{+}-C^{-}.

## 3. Invariant and transitive matrix

### 3.1. Invariant

For completeness, we recall the terminologies which were used in (Lee, 2001; Lee,2004; Lee,2006; Liu,1999).

(Def. 3.1): Invariant

A row vector X = (x_{1},x_{2},…,x_{n})0 is called a P-invariant if and only if X •C = 0, where x≠0 and •denotes the vector product.

A column-vector Y=(y_{1},y_{2},…,y_{n})^{T} 0 is called a T-invariant, if and only if C •Y = 0, where Y is an integer solution of the homogeneous matrix equation and Y≠ 0.

(Def.3.2): Place transitive and Transition matrix

The place transitive and transition matrix are defined, respectively as follows:

(Example):

This matrix allows representing the relation between places in terms of output and input. For previous example, we can find that p2 and p3 receive a token after p1 and that p1 receives one token from p2 and another from p3 (Fig.1).

(Def. 3.3): Labeled place transitive matrix

LetThe elements of

(Def. 3.4): Let

Through introducing the mm place transitive matrix, we can evaluate the transition enabling firing, and calculate the Quantity and the Sequence of Transition enabling Firing.

(Def.3.5): Let a reachable marking

(Example):

This example net explained like that

### 3.2. Algorithm and properties

A basic Unit of Concurrency (BUC) is a subnet corresponding to a resource. It contains the incoming transitions of the resource and also the outgoing transitions. We chose the BUC based on the place transitive matrix; in this paragraph we propose an algorithm to determine the BUC.

Algorithm: BUC construction algorithm

Input: N = <P, T, I,O, Mo, >

Output: BUC of N, N_{S}=<P_{S}, T_{S}, I_{S}, O_{S},Mo_{S}, _{s}>

Define

Find the all-relational places, of the shared resource, in each column and row

Find the relational place of selected place in (1).

Link all selected places and transitions with existing arcs on the initial Petri net.

The method of partitioning the model divides the system into BUC. The obtained BUC is defined as follows:

(Def.3.6): BUC

In Time Petri net N= <P, T, I,O, Mo, >, when the places set is divided by the previous algorithm, the BUCs are defined by (BUC_{i} | i=1,…,n), and each BUC_{i} = (P_{i},T_{i},F_{i},M_{i},_{i,}) satisfies the following conditions.

We can say that the flow of control in the Petri nets is based on the tokens flow. If the token is divided into some tokens after firing a transition, the flow of control divides to several flows. Accordingly, we define that the BUC is a set of the executed flow of control based on the functional properties of the net. In the Time Petri net model, the behavioral condition of transition t are all predecessors’ places (^{}t), which are connected with transition t. Petri net Slices are subnets based on BUC at the transition level, and a functional condition is defined according to the following conditions.

When transition t is not shared : satisfy the precondition of transition t only.

When several slices share transition t: satisfy the preconditions in all BUC, which have transition t.

(Theorem. 3.1) Let N be a Time Petri net and Ns be a set of Time Petri net slices that is produced by the slice algorithm. If Ns satisfied the functional conditions, N and Ns are behavioral equivalent (NNs).

(Proof) (We prove this theorem based on the

() Since the p is an element of P_{i}, t_{i} T_{i,} such that p t_{i}. And by the BUC definition, P_{i} = P_BUC_{i}, P_BUC_{i} is a set of place which is obtained by the BUC algorithm, such that P_BUC_{i} P. So, we say that if p t_{i} is then p t_{T} is true.

() Consider if p P and p P_BUC_{i} then P P_BUC_{i}. If p P, t T such that p t. And_{i} is a set of places which is obtained by the BUC algorithm, such that P_{i} P. So if p P and p P_BUC_{i then} P P_BUC_{i} is not true.□

## 4. Unfolding time Petri nets (UTPN)

Unfolding technique, originally proposed by McMillan(McMillian,1995), is a method used to avoid the state explosion problem in the verification of concurrent systems modeled with finite-state Petri nets. The technique is based on the concept of net unfolding; well-unknown partial order semantics of Petri nets (Hwang, 1997; Kondratyev, 1996; Lee,2001; McMillian, 1995).

### 4.1. Occurrence Nets

An occurrence net is a net, which represents clearly causal relations between places, especially transitions, of the original net. In this section, we briefly recall the main definitions (Fig. 3 and 4).

(Def.4.1) (OCN (Occurrence net)). An occurrence net is an acyclic Time Petri net N=<P,T,F,M_{o},> in which every place pP has at most one input transition ( |^{}p|1, F (P x T) (T x P) ) is the flow relations.

An OCN algorithm is summarized as follows (Hwang, 1997; McMillian,1995):

Algorithm: (Occurrence net construction)

Input: N=<P,T,F,M_{o},>

Output: the OCN of N, N’=<P’,T’,F’,M_{o}
^{’},’>.

Make a copy of the place in to the OCN and labeled as p’.

Repeats (2)-(6) until the transitions set becomes empty.

Choose a transition t T

For each place in t, find a copy in the OCN, and if not found then go back to (2).

Do not choose same subnet in OCN twice for a given t.

If any pair of chosen places is not concurrent, go to (1).

Make a copy of t in OCN and labeled as t’. Draw an arc from every places which was chosen to t’.

For each place in t, make a copy in the OCN.

Also, we can see a relationship between OCN and cyclic nets as following definition.

(Def.4.2) Let N’ =<P’,T’,F’,M_{o}’,’> be an OCN and N=<P,T,F,M_{o},> be a cyclic net, and labeling function L’:P’P and T’ T then OCN satisfying follows conditions:

{ s’ s’ T’,F’* (P’ x T’) (T’ x P’)}

pP’, pt

_{1}^{}and p t_{2}^{}implies t1 =t2.t

_{1},t_{2},t_{3}T’,t_{1}F’*t_{3}and t_{2}F’*t_{3}and^{}t_{1}^{}t_{2}implies t_{1}=t_{2}.t

_{1},t_{2}T’, L’(t_{1})=L’(t_{2}) and^{}t_{1}=^{}t_{2}implies t_{1}=t_{2}.

### 4.2. Unfolding

Unfolding is used to verify the occurrence net after cut or truncate, based on local configuration and basic marking (Kondratyev, 1996; McMillian,1995).

(Def.4.3)( Configuration). A set of transitions C’T’ is a configuration in an OCN if:

for each t’C’ the configuration C’ contains t’ together with all its predecessors;

C’ contains no transitions in mutual conflict.

(Def.4.4) Let C’ be a configuration of an occurrence net. A final marking of C’, denoted by FM (C’), is a marking reachable from the initial marking after all transitions of C’ and only those transitions are fired. A final marking of a local configuration of t’ is called a basic marking of t’ and denoted BM (t’). The set of predecessor transitions of t’ of the C’ is called the local configuration of t’ and is denoted as t’.

(Def.4.5) (Cut off). A transition t_{i}’ of an occurrence net is a cut off transition, if there exists another transition t_{j}’ such that BM (t_{i}’)=BM (t_{j}’) and |t_{i}’| |t_{j}’|, where |t_{i}’| is the cardinality of {t_{i}’}. An unfolding is the greatest backward closed subnet of an occurrence net containing no nodes after cut-off transition.

(Def.4.6) An unfolding time Petri net UTPN=<P’,T’,F’,M_{o},’> is obtained from the occurrence net by removing all the places and transitions, which succeed the cut-off (Fig. 5).

Let UTPN be a unfolding Time Petri net, Mo be the initial marking and FM be a final marking, find a sequence x such that: BM (x>FM, and the reachability delay is minimal (Richanrd,1998):

Subject to BM (x>FM where X=(x_{t}) is the characteristic vector of the sequence x.

## 5. Modeling of UTPN

An important sub-class (sliced net) of Time Petri nets is a net in which has an independent control flow and for which all weights associated to arcs are equal to one. In this works, we select an independent control flow based on the machines operations. This Time Petri net can perfectly model the command we want to implement. At the end of the optimization approach we obtained a model where all the operating sequence are linear and the next step is to compute the best schedule.

### 5.1. Computing the optimal schedule

The schedule of a sliced net can be easily computed by playing the token and firing transition as soon as possible. We can compute firing dates of transitions by computing potentials on the sliced net after unfolding. In the unfolding net UTPN, it has one function for compute the makespan time, as * f* (UTPN). The function

*(UTPN) is the necessary time to go from the initial marking Mo to the object marking.*f

*(UTPN) is composed of*f

*(t*h

_{i}) and

*(t*g

_{i}), where

*(t*h

_{i}) is an operating time of transition t

_{i}, and g(t

_{i}) is an operating time of the next transition t

_{i}(we call it minimum waiting time to fire transition t

_{i}). Then, the schedule duration can be computed by the following recurrent formula:

The best schedule of the UTPN is obtained by minimizing the function f(UTPN). We can say that if we find a minimized unfolding net, the schedule of marking is an optimized schedule. So let UTPN be the makespan time of the optimized unfolding schedule. Then the time can be computed using the unfolding net as follows:

To apply our method continuously, we consider some notations about degree of operation time in the machine and minimized WIP. The deciding order is one of the important things in the scheduling problem. We consider a throughput of the operation time in the machine, based on the number of tokens (number of resource share), and the operating time of machine.

Let d(m_{i}) be the degree of operation time in the machine, then

where, (m_{i}) is total operation time of the machine i, and (m_{i} ) is number of token (resource share transition) in machine i.

So, this degree of d(m_{i}) is one parameter to choice the select an order to apply in Unfolding net

In the linear cyclic scheduling problem, the minimization of the number of pallets is one of the important factors.

(Def. 5.1) Let CT be an optimal cyclic time based on the machines work, then WIP lower bound is:

### 5.2. Dispatching rules

We consider a system with two machines such as M1, M2 and two jobs such as OP1 and OP2 in (Camus, 1996). Let us assume that the production ratio corresponds to the production of 50% of OP1, 50% of OP2(Fig. 6).

Now, we show the transitive matrix of the example as shown in Table 1. For simplicity reason, we ignore two places w1, w2 and one transition tw. In this table, initial tokens exist in M1 and M2. The cycle time of OP1 and Op2 are 11 and 9, and the working time of machine M1 and M2 are both 10, respectively. So the cycle time CT is 10. The minimized WIP is:

Also, about the degree of the feasibility time of the machine, M1 and M2 have same priority,

These machines have same operating time (i.e. 10) for three operations showing that it is not important to give the priority for first approach. So we select M1 to start with.

Now, we select row and column of p1, p3, p5, and M1 in (Table 1), and make one slice net based on the selected places and transitions.

1. Slice BUC of M1 and its unfolding nets

Machine M1 involved two tasks (OP1and OP2) in three processes (t1, t3, t5)(Fig. 7 and 8).

In this net, we can find the 6 processes of M1 are as follows (Fig. 9):

Suf1 = t1 t5t3 (15), Suf2 = t5t1t3 (15), Suf3 = t1t3t5 (12),

Suf4 = t3t1t5 (12), Suf5 = t3t5t1 (15), Suf6 = t5t3t1 (15),

where () is an operation time of Sufi.

In M1, we can choose two schedules as transitions sequences: t3-t1-t5 and t1-t3-t5.

2. Modeling of M2 and its unfolding nets

Machine M2 involved two tasks (OP1 and OP2) in three processes (t2, t4 and t6) (Fig. 10,11).

We can show the six processes like as follows (Fig. 12) :

In M2, we can find two solutions like as Suf3 and Suf5. Now, we apply the selected solutions of BUC of M2: {Suf3 and Suf5} to obtain the solution BUC on M1: {Suf3 and Suf4}, then we obtained two solutions. The optimal schedules of two cycles are in Fig. 13 and 14.

Bs1: A3A1B2 (M1) B3B1A2 (M2)

Bs2: A1A3B2 (M1) B3B1A2 (M2)

Finally, we get three pallets rather than two, which is lower bound WIP. Indeed in this model, it is impossible to optimize CT with two pallets, as proved in (Camus,1997). So, we can say that this solution is best possible one(Fig. 15,16).

## 6. Benchmark

### 6.1. Notations

In this section, one example taken from the literature is analyzed in order to apply three cyclic scheduling analysis methods such as Hillion (Hillion, 1987), Korbaa (Korbaa, 1997), and the previously presented approach. The definitions and the assumptions for this work have been summarized (Korbaa,1997).

The formulations for our works, we can summarize as follows:

the sum of all transition timings of

M() (=Mo()), the (constant) number of tokens in ,

C() = ()/M(), the cycle time of ,

Where is a circuit.

C* =Max(C()) for all circuits of the net,

CT the minimal cycle time associated to the maximal throughput of the system:

CT =Max(C()) for all resource circuits = C*

Let CT be the optimal cycle time based on the machines work, then WIP is (Korbaa,1997):

We introduce an illustrative example in Camus(Camus, 1997), two part types (P1 and P2) have to be produced on three machines U1, M1 and M2. P1 contains three operations: u1(2 t.u.) then M1(3 t.u.) and M2(3 t.u.) P2 contains two operations: M1(1 t.u.) and U1(2 t.u.). The production horizon is fixed and equalized to E={3P1, 2P2}. Hence five parts with the production ratio 3/5 and 2/5 should be produced in each cycle. We suppose that there are two kinds of pallets: each pallet will be dedicated to the part type P1 and the part type P2. Each transport resource can carry only one part type. The operating sequences of each part type are indicated as OS1 and OS2. In this case, the cycle time of OP11, OS12 and OS13 are all 7 and Op21 and OS22 all 3, also the machines working time of U1 is 10, M1 is 11 and M2 is 6. So the cycle time CT is 10. The minimization WIP is:

### 6.2. Benchmark

By the example, we can obtain some results like as the following figures (Fig. 18-20).

#### Optimization

The Hillion’s schedule (Hillion, 1987) has 6 pallets, the Korbaa’s schedule (Korbaa, 1997) 3 ones, and the proposed schedule 4 ones. This solution showed that the good optimization of Korbaa’s schedule could be obtained and the result of the proposed schedule could be better than that of the Hillion’s.

Also, the solutions of the proposed approach are quite similar to (a) and (c) in Fig. 20 without the different position.

#### Effect

It’s very difficult problem to solve a complexity value in the scheduling algorithm for evaluation. In this works, an effect values was to be considered as the total sum of the numbers of permutation and of calculation in the scheduling algorithm to obtain a good solution. An effected value of the proposed method is 744, i.e. including all permutation available in each BUC, and selecting optimal solution for approach to next BUC. An effect value to obtain a good solution is 95 in the Korbaa’s method; 9 times for partitions, 34 times for regrouping, and 52 times for calculation cycle time. In the Hillion’s method, an effected value is 260; 20 times for machine’s operation schedule and 240 times for the job’s operation schedule.

#### Time

Based on the three algorithms, we can get time results for obtaining the good solution. Since this example model is simple, they need very small calculation times; 1 sec for the Korbaa’s approach and 1.30sec for both of the Hillion’s and the proposed approaches. The Korbaa’s approach has minimum 1 minute and maximum 23 hours in the 9 machines and 7 operations case in Camus (Camus, 1997), while the proposed approach 3 minutes. Meanwhile the Hillion’s and the Korbaa’s approaches belong to the number of the operation and the machines, the proposed method to the number of resource shares machines. This means that the Hillion’s and the Korbaa’s approaches analyzing times are longer than the proposed one in the large model. As the characteristic resultants of these approaches are shown in Fig. 21, the Korbaa approach is found out to be good and the Hillion approach is to be effectiveness in the time. And on the effort point, the proposed approach is proved to be good.

## 7. Conclusion and future study

In this paper, we focused on the analysis of a cyclic schedule for the determination of the optimal cycle time and minimization of WIP (Work In Process). Especially, this paper product ratio-driven FMS cyclic scheduling problem with each other products and ratios has been dealt. We proposed a model that has two jobs and two machines. And TPN slice and unfolding are applied to analyze this FMS model. We can divide original system into subsystem using TPN slice and change iterated cycle module into acyclic module without any other behavior properties.

Specially, we simulated our approach with IBM PC windows 2000 using Visual C++, then our approach is faster than Korbaa’s approach in the many resource shared. This means that the new approach is more useful to the model that has many resource share machines in any case. If the model has small resource share machines and short operation depths, then it’s useful to approach Korbaa’s.

We are sure that proposed method is very useful to analyze all Petri net models. This proposed method is available to apply to a complex computer simulation, a parallel computer design and analysis, and a distributed control system, etc.

## References

- 1.
Best E. Cherkasova L. Desel J. Esparza J. 1990 Characterization of Home States in Free Choice Systems, - 2.
Carlier J. Chretienne P. 1988 Timed Petri nets Schedules, In: - 3.
Camus H. 1997 Conduite de Systèmes Flexibles de Production Manufacturière Par Composition de Régimes Permanents Cycliques:Modélisation et Evaluation de Performances à l’Aide des Réseaux de Petri, Thèse doctorat USTL - 4.
Esparza J. Lomer S. Vogler W. 1996 An Improvement of McMillans unfolding Algorithms, IN: - 5.
Hwang C. H. Lee D. I. 1997 A Concurrency Characteristic in Petri net Unfolding,” - 6.
Hillion H. Proth J. M. Xie X. L. 1987 A Heuristic Algorithm for Scheduling and Sequence Job-Shop problem, - 7.
Julia S. Valette R. Tazza M. 1995 Computing a feasible Schedule Under A Set of Cyclic Constraints, - 8.
Kondratyev A. Kishinevsky M. Taubin A. Ten S. 1998 Analysis of Petri nets by Ordering Relations in Reduced Unfolding, - 9.
Korbaa O. Camus H. Gentina J. C. 1997 FMS Cyclic Scheduling with Overlapping production cycles, - 10.
Lee D. Y. Di Cesare F. 1995 Petri Net-based heuristic Scheduling for Flexible Manufacturing, In: - 11.
Lee J. K. Korbaa O. 2006 Scheduling Analysis in FMS Using the Unfolding Time Petri nets, - 12.
Lee J. K. Korbaa O. Gentina J. C. 2001 Slice Analysis Method of Petri nets in FMS Using the Transitive Matrix, - 13.
Lee J. K. Korbaa O. 2004 Modeling and analysis of radio-driven FMS using unfolding time Petri Nets, - 14.
Liu J. Itoh Y. Miyazawa I. Seikiguchi T. 1999 A Research on Petri nets Properties using Transitive matrix”, - 15.
Murata T. 1989 Petri Nets: Properties, Analysis an Applications, - 16.
Mc Millan K. 1995 A technique of state space search based on unfolding, - 17.
Ohl H. Camus H. Castelain E. Gentina J. C. 1995 Petri nets Modeling of Ratio-driven FMS and Implication on the WIP for Cyclic Schedules, - 18.
Richard P. 1998 Scheduling timed marked graphs with resources : a serial method, Proceeding of INCOM’98 - 19.
Taubin A. Kondratyev A. Kishnevsky M. 1997 Application of Petri Nets unfolding to Asynchronous Design, - 20.
Valentin C. 1994 Modeling and Analysis methods for a class of Hybrid Dynamic Systems”, - 21.
Zuberek W. Kubiah W. 1993 Throughput Analysis of Manufacturing Cells Using Timed Petri nets,