InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Theory of Computation » "Petri Net, Theory and Applications", book edited by Vedran Kordic, ISBN 978-3-902613-12-7, Published: February 1, 2008 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 13

Scheduling Analysis of FMS Using the Unfolding Time Petri Nets

By Jong kun Lee and Ouajdi Korbaa
DOI: 10.5772/5322

Article top

Overview

A Petri net.
Figure 1. A Petri net.
Illustrative example.
Figure 2. Illustrative example.
Cyclic Petri net.
Figure 3. Cyclic Petri net.
Occurrence net of Fig. 3.
Figure 4. Occurrence net of Fig. 3.
Unfolding net of Fig. 3.
Figure 5. Unfolding net of Fig. 3.
A two shared resources example.
Figure 6. A two shared resources example.
Transitive matrix of the illustration example.
Table 1. Transitive matrix of the illustration example.
The five BUCs of M1.
Figure 7. The five BUCs of M1.
Example of the unfolding of M1.
Figure 8. Example of the unfolding of M1.
Results of the permutations of BUC in M1.
Figure 9. Results of the permutations of BUC in M1.
The BUC of M2.
Figure 10. The BUC of M2.
Example of unfolding of M2.
Figure 11. Example of unfolding of M2.
Results of permutations of BUC in M2.
Figure 12. Results of permutations of BUC in M2.
Optimal schedule of Bs1.
Figure 13. Optimal schedule of Bs1.
Optimal schedule of Bs2.
Figure 14. Optimal schedule of Bs2.
Linear schedule of Bs1.
Figure 15. Linear schedule of Bs1.
Linear schedule of Bs2.
Figure 16. Linear schedule of Bs2.
Illustrative example.
Figure 17. Illustrative example.
Hillion’s schedule.
Figure 18. Hillion’s schedule.
Korbaa’s schedule.
Figure 19. Korbaa’s schedule.
Proposed schedule.
Figure 20. Proposed schedule.
Total relation graph.
Figure 21. Total relation graph.

Scheduling Analysis of FMS Using the Unfolding Time Petri Nets

Jong kun Lee1 and Ouajdi Korbaa2

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 D=[111000011011101000001110000111000010] I: T->P is the input function, O: T->P is the output function. PT=ϕ , Mo is an initial marking, N is the set of positive integers. : TN is a time function which associate to each transition of T a deterministic rational.

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 NS=<PS,TS,FS,MS, S>,where PS P, TS T, FSF,MS (Mo> and S then we can say that NS is sub-net of N.

The number of occurrences of an input place Pi in a transition tj is given by #(Pi,I(tj)), and the number of occurrences of an output place Pi in a transition tj is given by #(Pi,O(tj)).

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:

MoM={M|M:PN},

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 = (x1,x2,…,xn)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=(y1,y2,…,yn)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:

C=[I,j] = #(Pi,I(tj)), matrix of input function,C+=[I,j] = #(Pi,O(tj)), matrix of output function.

(Example):

media/image5.jpeg

Figure 1.

A Petri net.

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

Let CP= C(C+)TCT=(C+)TC be the labeled place transitive matrix: LCP

The elements of LCP=Cdiag(t1,t2,...,tn)(C+)T describe the direct transferring relation that is from one place to another one through one or more transitions.

(Def. 3.4): Let LCP be the mm place transitive matrix. If a transition LCP appears s times in the same column of tk , then we replace LCP in tk by LCP in tk/s .

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 L*CP from MR(K+1) be an m-vector of nonnegative integer. The transformation is defined by:

M(k)
media/image15.jpeg

Figure 2.

Illustrative example.

(Example):

This example net explained like that MR(k+1)T=M(k)TL*CP , then we can obtain (Fig. 2):

M(k)=[P1(k),P2(k),P3(k)]T and LBP=[00t100t2000] .

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, NS=<PS, TS, IS, OS,MoS, s>

Define MR=[0,0,t1(P1(k))+t2(P2(k))]T and consider one shared resource (machine)

Find the all-relational places, of the shared resource, in each column and row LCP and make an element of own BUC with this initial marking place.

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 (BUCi | i=1,…,n), and each BUCi = (Pi,Ti,Fi,Mi,i,) satisfies the following conditions.

LCP

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                          Pi= P_BUCi,       Ti= {tÎ| sÎPi, (s, t)ÎF or (t, s)ÎF},        Fi= {(p, t)ÎF, (t, p)Î| pÎPi, tÎTi},"tiÎt,ti(t) =t(t) and"pÎMi, Mi(p) = M(p). ).

() Since the p is an element of Pi, ti Ti, such that p ti. And by the BUC definition, Pi = P_BUCi, P_BUCi is a set of place which is obtained by the BUC algorithm, such that P_BUCi P. So, we say that if p ti is then p tT is true.

() Consider if p P and p P_BUCi then P P_BUCi. If p P, t T such that p t. And ptiptT , in this case, we can say that ptTit but by the definition of BUC, Pi is a set of places which is obtained by the BUC algorithm, such that Pi P. So if p P and p P_BUCi then P P_BUCi 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).

media/image23.png

Figure 3.

Cyclic Petri net.

media/image24.png

Figure 4.

Occurrence net of Fig. 3.

(Def.4.1) (OCN (Occurrence net)). An occurrence net is an acyclic Time Petri net N=<P,T,F,Mo,> 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,Mo,>

Output: the OCN of N, N’=<P’,T’,F’,Mo ,’>.

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

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

  2. Choose a transition t T

  3. 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.

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

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

  6. 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’,Mo’,’> be an OCN and N=<P,T,F,Mo,> be a cyclic net, and labeling function L’:P’P and T’ T then OCN satisfying follows conditions:

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

  2. pP’, pt1 and p t2 implies t1 =t2.

  3. t1,t2,t3T’,t1F’*t3 and t2F’*t3 and t1 t2 implies t1 =t2.

  4. t1,t2T’, L’(t1)=L’(t2) and t1=t2 implies t1 =t2.

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:

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

  2. 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 ti’ of an occurrence net is a cut off transition, if there exists another transition tj’ such that BM (ti’)=BM (tj’) and |ti’| |tj’|, where |ti’| is the cardinality of {ti’}. 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’,Mo,’> is obtained from the occurrence net by removing all the places and transitions, which succeed the cut-off (Fig. 5).

media/image25.png

Figure 5.

Unfolding net of Fig. 3.

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):

tTit = i=1Pi

Subject to BM (x>FM where X=(xt) 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 f (UTPN) is the necessary time to go from the initial marking Mo to the object marking. f (UTPN) is composed of h(ti) and g(ti), where h(ti) is an operating time of transition ti, and g(ti) is an operating time of the next transition ti (we call it minimum waiting time to fire transition ti). Then, the schedule duration can be computed by the following recurrent formula:

Min  z = tTxi and f(UTPN) =h(ti) +g(ti)

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:

f(UTPN)=Max1jn{(i=1jh(ti))+g(tj)}

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(mi) be the degree of operation time in the machine, then

Optimize UTPN = min (f(UTPNi))

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

So, this degree of d(mi) 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:

d(mi)=ϕ(mi)γ(mi)

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:

WIP=i(OStobecarriedbyiOperatingtime)CT

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

WIP =11+910 = 2

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.

media/image35.png

Figure 6.

A two shared resources example.

media/image36.png

Table 1.

Transitive matrix of the illustration example.

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).

media/image37.png

Figure 7.

The five BUCs of M1.

media/image38.png

Figure 8.

Example of the unfolding of M1.

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.

media/image39.png

Figure 9.

Results of the permutations of BUC in M1.

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).

media/image40.png

Figure 10.

The BUC of M2.

media/image41.png

Figure 11.

Example of unfolding of M2.

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

d(M1)= 103 = 3.3d(M2) = 103 = 3.3
(11)
Suf1 = t2t4t6 (13), Suf2 = t2t6t4 (14) Suf3 = t4t6t2
(13)
media/image44.png

Figure 12.

Results of permutations of BUC in M2.

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)

media/image45.png

Figure 13.

Optimal schedule of Bs1.

media/image46.png

Figure 14.

Optimal schedule of Bs2.

media/image47.jpeg

Figure 15.

Linear schedule of Bs1.

media/image48.jpeg

Figure 16.

Linear schedule of Bs2.

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:

Suf4 = t4t2t6 (13), Suf5 = t6t4t2 (11), Suf6 = t6t2t4 ,

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):

μ(γ)=tγD(t)

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:

WIP = palletstypeiOStobecarriedbyiOperatingtimeCT i WIP =Operating Times of OSp1CT           +Operating Times of OSp2CT         =7+7+711  +3+311= 3 WIP =Operating Times of OSp1CT           +Operating Times of OSp2CT         =7+7+711  +3+311= 3
media/image52.png

Figure 17.

Illustrative example.

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.

media/image53.png

Figure 18.

Hillion’s schedule.

media/image54.png

Figure 19.

Korbaa’s schedule.

media/image55.jpeg

Figure 20.

Proposed schedule.

media/image56.png

Figure 21.

Total relation graph.

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 - E. Best, L. Cherkasova, J. Desel, J. Esparza, 1990 Characterization of Home States in Free Choice Systems, Hildesheimer Informatik-Berichte 9 90, Universitat Hildesheim
2 - J. Carlier, P. Chretienne, 1988 Timed Petri nets Schedules, In: Advanced in PN, G. Rozenberg(Ed.), 340 of LNCS, 62 84 , 0-38750-580-6Verlag,Berlin, Germany
3 - H. Camus, 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 - J. Esparza, S. Lomer, W. Vogler, 1996 An Improvement of McMillans unfolding Algorithms, IN: LNCS 1055, 87 106
5 - C. H. Hwang, D. I. Lee, 1997 A Concurrency Characteristic in Petri net Unfolding,” Proceeding of SMC’97, 4266 4273
6 - H. Hillion, J. M. Proth, X. L. Xie, 1987 A Heuristic Algorithm for Scheduling and Sequence Job-Shop problem, Proceeding of 26th CDC 1987, 612 617
7 - S. Julia, R. Valette, M. Tazza, 1995 Computing a feasible Schedule Under A Set of Cyclic Constraints, Proceeding of 2nd International Conference on Industrial Automation, 141 146 , Nancy 7-9, Juin, 1995
8 - A. Kondratyev, M. Kishinevsky, A. Taubin, S. Ten, 1998 Analysis of Petri nets by Ordering Relations in Reduced Unfolding, Formal Methods in System Design, 12 1 5 38
9 - O. Korbaa, H. Camus, J. C. Gentina, 1997 FMS Cyclic Scheduling with Overlapping production cycles, Proceeding of ICATPN’97, 35 52
10 - D. Y. Lee, F. Di Cesare, 1995 Petri Net-based heuristic Scheduling for Flexible Manufacturing, In: Petri Nets in Flexible and Agile Automation, Zhou MC. (Ed.), 149 187 , Kluwer Aca. Pub., USA
11 - J. K. Lee, O. Korbaa, 2006 Scheduling Analysis in FMS Using the Unfolding Time Petri nets, Mathematics and Computer in Simulation, 70 419 432 ,
12 - J. K. Lee, O. Korbaa, J. C. Gentina, 2001 Slice Analysis Method of Petri nets in FMS Using the Transitive Matrix, Proceeding of INCOM01, 0-08043-246-8Austria,Control Problem in Manufacturing, Elsevier Science
13 - J. K. Lee, O. Korbaa, 2004 Modeling and analysis of radio-driven FMS using unfolding time Petri Nets, Computer Ind. Eng. (CIE), 4 639 653
14 - J. Liu, Y. Itoh, I. Miyazawa, T. Seikiguchi, 1999 A Research on Petri nets Properties using Transitive matrix”, Proceeding of IEEE SMC99, 888 893 ,
15 - T. Murata, 1989 Petri Nets: Properties, Analysis an Applications, Proceedings of the IEEE, 77 4 April 1989, 541 580 .
16 - K. Mc Millan, 1995 A technique of state space search based on unfolding, Formal Methods in System Design 6 1 45 65
17 - H. Ohl, H. Camus, E. Castelain, J. C. Gentina, 1995 Petri nets Modeling of Ratio-driven FMS and Implication on the WIP for Cyclic Schedules, Proceeding of SMC’95, 3081 3086
18 - P. Richard, 1998 Scheduling timed marked graphs with resources : a serial method, Proceeding of INCOM’98
19 - A. Taubin, A. Kondratyev, M. Kishnevsky, 1997 Application of Petri Nets unfolding to Asynchronous Design, Proceeding of IEEE-SMC 1997, 4279 4284
20 - C. Valentin, 1994 Modeling and Analysis methods for a class of Hybrid Dynamic Systems”, Proceeding of Symposium ADPM’94,221 226
21 - W. Zuberek, W. Kubiah, 1993 Throughput Analysis of Manufacturing Cells Using Timed Petri nets, Proceeding of ICSYMC 1993, 1328 1333