Factoring and warehouse distribution centers face numerous and interrelated challenges in their eorts to move products and materials through their facilities. New technologies in navigation and guidance allow true autonomy with more exibility and resource eciency. In this paper we investigate a complete design approach to obtain deadlock-free minimal adaptive routing algorithms for these systems. The approach is based in an abstract view of the system as a Resource Allocation System. The interconnection network and the routing algorithm elaborated by the designer, are the initial information used to obtain in an automatic way a Petri Net model. For this kind of routing algorithms, we prove that the obtained Petri Net belongs to the well-known class of S4P R net systems, and therefore the rich set of analysis and synthesis results can be applied to enforce the liveness property of the routing algorithm.
Nowadays, many factories and warehouse and distribution centers use Automatic Guided Vehicles (AGV s) for item transportation among workstations. The wheeled trailers are the most productive form of AGV for tugging and towing because they haul more conveyor-loads per trip than other AGV types. In this paper we consider a warehouse distribution center as a programmable system for conveyor-loads movement among workstations using tugger AGV . The problem to be investigated concerns the design of Deadlock-Free minimal adaptive routing algorithms for the guidance system of tuggers AGV s, travelling into an warehouse distribution center. We say that the routing algorithm is minimal because only routes of minimal length between two workstations are taken into account. Moreover, the routing algorithms we are considering are adaptive in the sense that the route of a conveyor-load is constructed segment by segment. The assignment of a segment to the route of a conveyor-load is done in a workstation when the rst trailer try to leave the workstation towards its destination workstation.
From the methodological point of view, the design of deadlock-free minimal adaptive routing algorithms is a complex task, where the designer experience is required because deadlock states can appear. There exist several approaches to cope with this problem [15]. They consider more general routing algorithms than those considered in this paper (including, for example, non-minimal routes). Because this generality, very few powerful analysis and synthesis results are available.
Our approach gives a full design cycle for minimal adaptive routing algorithms using Petri Nets as formal model that allows structural analysis of the liveness property of the model. Afterwards, if it is necessary, the initial routing algorithm is changed. From the point of view of software engineering, in the context of the control software for AGV s systems, this paper intends to make contributions in the following directions: (a) The formalization of an abstraction process of the system to retain only the relevant characteristics in the study of deadlock problems in the routing software of AGV s. This abstraction is constructed around a minimal set of concepts processes and resources. (b) The demonstration that for AGVs with minimal adaptive routing algorithms, the proposed abstraction process gives rise to models belonging to a well known class of Petri Nets named S4P R, and so, we have many available results to cope with these systems. (c) A modular methodology to construct the models based on the specication of processes with resources that form the modules. The modules are composed by the fusion of common shared resources (segments) by dierent modules. This paper is organized as follows. In Section 2 an illustrative example is presented. In section 3 the proposed methodology is presented in detail. Section 4 presents the rst step of the methodology consisting of the abstraction of the warehouse distribution center and the routing algorithm to retain only those aspects related to the appearing of deadlocks. Section 5 is devoted to the Petri Net model representing the Resource Allocation view of the system. This section also proves that the Petri Nets obtained for these routing algorithms belong to the class of the S4P R nets. Section 6 presents the analysis and synthesis phases of the methodology that prot the theoretical results known for the class of S4P R. Finally, section 7 presents some conclusions. 2
In this section, a simple example of a warehouse distribution center, will be presented. The specication of this example illustrates the typical situation in the transportation system of items. We start with a layout of the shipping areas dened by a set of workstations W S and a set of segments SG interconnecting the workstations. The connection pattern among workstations will be called the f ramework of the warehouse distribution center. The example that we are considering is an unidirectional ring in clockwise fashion as underlying framework. There are four workstations W S={ w0, w1, w2, w3} and they are interconnected by a set of segments SG={ sa0, sa1, sa2, sl1, sl2, sl3} . This warehouse distribution center is depicted in schematic way in Fig. 1.a. Observe that if a workstation has two output segments, a train can follow any of them. This decision is taken by the local minimal adaptive routing algorithm of the workstation. The other dening element of the warehouse distribution center is the behavior of the conveyors because a train can tow single or multiple trailers hence the length of the conveyors is variable. As the conveyors ow in pipeline fashion through the framework, these can have simultaneously allocated several segments of the framework. The rst trailer of the AV G train is the head of the conveyors and reserve the segments to transit; the last trailer is the tail and release them. Traditionally, each segment supports only one conveyor at time to avoid collisions. In our example, each workstation executes, an instance of the following minimal adaptive routing algorithm parameterized by the identity of the workstation. ALGORITHM 1 Minimal Adaptive Routing Algorithm for workstation i. Input: The head trailer cl from the conveyor-load queue.
Local: Si ⊆ SG, output segments for workstation i
F ⊆ Si, set of non-assigned output segments Output: The next segment to be used for cl begin if (destination(cl) = i) then store the conveyor-load cl in workstation i else if ( sai ∈ F ) then use sai ; F :=F \{ sai} else if ((destination(cl) < i) ∧ (sli ∈ F )) then
use sli ; F :=F \{ sli} else enqueue cl end if end if end if end That means the workstation knows its non-assigned output segments and the algorithm assigns, if it is possible, the output segment that the rst trailer must follows in order to reach its destination. In other words, to reach a destination workstation, wd, dierent to the current workstation wi, the algorithm tries to assign the output segment sai if it is an output free segment of wi. Otherwise, sli is assigned if this segment is an output free segment of wi and the index d of the workstation wd is less than the index i of wi. This reservation is done by the head trailers. The intermediate trailers follow through the reserved segments and the tail trailer release the segments that they will be added to the set of free segments F . The design of minimal adaptive routing algorithms can lead to solutions where deadlock states can be reached. A deadlock state, in a warehouse distribution center, arise when a set of conveyor-loads are in transit to their respective destination workstations but all of them are stopped forever in intermediate workstations. They are waiting for the availability of output segments of these intermediate workstations that have been previously assigned to conveyorloads belonging to this set. Therefore, none of the implied conveyor-loads will reach their destination workstations. The minimal adaptive routing algorithm of our example presents this anomaly that we illustrate by means of the following deadlock state. We have four conveyor-loads, { cl1, cl2, cl3, cl4} , each one composed by more than one trailer. It is easy to verify that the state described in table 1, for the four conveyor-loads in transit, is reachable, where H and T represent the current workstations of the head and tail trailers, respectively. The rest of the columns in the table 1 represent: Allocated segments − segments assigned to the conveyor-load; Destination workstation − represents the destination workstation of the conveyor-load; Next segment − segment to be assigned to the head trailer according to the minimal adaptive routing algorithm. Observe that Conveyor Trailers Allocated Destination Next -loads H T Segments Workstation segment cl1 w0 w3 sl3 w1 sa0 cl2 w1 w0 sa0 w2 sa1 cl3 w2 w1 sa1 w3 sa2 cl4 w3 w2 sa2 w1 sl3 all conveyor-loads are in intermediate workstations and in order to advance in the warehouse distribution center, all conveyor-loads need segments (those given by the minimal adaptive routing algorithm) that they are allocated by other conveyor-loads in the same set (compare the two columns "Allocated Segments" and "Next segment" in the table 1). On the other hand, none of the tail trailers can release segments because if some tail trailer moves ahead, it will be in the same workstation that the head trailer and this is not possible. Therefore, we have reached a deadlock state where the four classical necessary conditions for the existence of a deadlock are fullled. Finally, you can observe that although we are in a deadlock state, there exist two segments, sl1 and sl2, that they are free, and the minimal adaptive routing algorithm cannot assign these segments to the four conveyor-loads of our scenario. 3
In this paper we advocate for a methodology where, after an analysis phase
of the model obtained from the framework (the interconnection network) and
the minimal adaptive routing algorithm, a synthesis procedure transform the
original routing algorithm to make it deadlock-free. In order to implement this
methodology we will make use of Petri Net models. Therefore, the rst task will
be the construction of the Petri Net model that retains only those aspects related
to the appearing of the deadlock states. Deadlocks appear as a consequence of
the allocation of the segments by the conveyor-loads in transit in the warehouse
distribution center. Therefore, we will adopt a Resource Allocation perspective
to abstract the system (RAS view of the warehouse distribution center) where
segments will be considered as resources, that they are used in a conservative
way (they are not created nor destroyed) by the user processes that they are
the conveyor-load moving from a source workstation to a destination
workstation. In next section, from the framework and the routing algorithm we will
obtain a Routing Graph for each destination workstation. One of these Routing
Graphs represents a transition graph where we present the reachable states of a
conveyor-load, composed by more than one trailer, from a source workstation of
the warehouse distribution center to the destination workstation corresponding
to the Routing Graph. From these Routing Graph and the segments
considered as resources, in section 5 we obtain a Petri Net that, in the case of minimal
adaptive routing algorithms, belongs to the well known class of S4P R nets. Now,
using the known analysis results for this class of nets we can characterize the
existence of deadlocks using a structural reasoning. The synthesis procedure is
based on the methods for liveness enforcing developed by dierent authors [
Routing Algorithm Specification
No
Yes
of the constrains on the model to the minimal adaptive routing algorithm
of a given conveyor-load with destination workstation wsi
Fig. 2. Design Flow Methodology. S p e c ii f c a t i o n A b s t r a c t i o n A n a l y s i s S y n t h e s i s P h a s e doMrFom le la 4
The goal of this section is to represent, step by step, the construction of the so called Routing Graph from the information about the framework of the warehouse distribution center and the minimal adaptive routing algorithm. This Routing Graph will represent the sequence of states that a conveyor-load must follow to reach a given destination workstation, wi. The denition of the state concerns the set of segments that the conveyor-load is using each time. Therefore, RG give us the so called Resource Allocation (RAS) view of the warehouse distribution center. First, the framework is formalized through the Warehouse Graph (WG). The W G is a labeled graph W G=(W, S), where W is a set of vertices and S is a set of edges. The set W is equal to W S and S⊆W ×2SG×W , where W S is the set of vertices and SG the set of segments. An edge (w1, s, w2)∈S means that there exists a set of segments s⊆SG from the workstation w1 to the workstation w2, as it is shown in the Fig. 1.b. We are considering the class of minimal adaptive routing algorithms. Therefore we will represent for each destination workstation wi all the paths of minimal length from a workstation wj to the destination workstation wi. This information is captured into the Minimal Path Graph (M P Gi) with destination workstation wi. Each one of these graphs is a subgraph of the W G = (W, S) and it will be an acyclic directed labeled graph, M P Gi=(V, E), where V =W , and E⊆S, verifying that: 1. All output arcs of wi in W G do not belong to E. 2. The function Li:V →IN is well dened: Li(wi)=0 and ∀wj ̸=wi, Li(wj )=k, where k is the length of the minimal path from wj to wi in the W G. 3. All arcs (w1, s, w2) ∈ S in W G, such that Li(wi)+1 ̸=Li(w2), do not belong to E.
The graphs M GPi for the example of Fig. 1 are depicted in the Fig. 3. Observe that we will have four of these graphs, one for each possible destination workstation. Each M P Gi can be seen as the set of paths that can follow a conveyor-load originated in the workstation wj with destination workstation wi, an this path satisfy the minimality condition of the considered routing algorithm. Nevertheless, we are considering conveyor-loads with more than one trailer of length, because a conveyor-load with only one trailer cannot participate into a deadlock, since a deadlock must fulll the Hold and Wait condition. Therefore in our model we must distinguish states according to the workstations where the head and tail trailers can be found. On the other hand, it is important to say that the advancement of the head trailer from a workstation to another can be done if and only if there exists at least a segment that can be allocated for this movement. Segments, therefore are resources in our RAS view of the warehouse distribution center. If the head trailer allocates the needed resources for the movement of the full conveyor-load, the tail trailer take charge of the release operation after the use of a segment. In order to represent the states of a conveyor-load with destination workstation wi we will construct, from the M P Gi, the so called Conveyor Behaviour Graph (CBG) for the destination workstation wi, CBGi=(Q, F ), verifying that. 1. Q⊆V ×V , where ∀wh, wt∈Q, wh=wt or L(wh)<L(wt). That is, the rst component of the dened states corresponds to the workstation where the head trailer is, and the second to the workstation where the tail trailer can be found. 2. F ⊆Q×{ A, R}× 2SG×Q, where F will contain the following edges: (a) Allocation edges ((wh1, wt), A, S, (wh2, wt)), ∀ wt∈V ,∀(wh1, s, wh2) ∈ E. (b) Release edges ((wh, wt1), R, S, (wh, wt2)), ∀ wh∈V ,∀(wt1, s, wt2) ∈ E. Obviously, CBGi is a directed acyclic graph because M P Gi is also a directed acyclic graph. The Fig. 4 shows the Conveyor Behaviour Graph for destination workstation 0, CBG0, corresponding to the M GP0 of Fig. 3. Finally, to construct the announced Routing Graph of our warehouse distribution center we need to incorporate the information corresponding to the routing algorithm. The routing algorithm is a function R:W S×W S→2SG, such that if wc is the current workstation of the head trailer and wd the destination workstation of the conveyor-load R((wc, wd)) determines the output segments of wc to be allocated in order to reach the destination workstation. The model that we will construct is a possibilistic model, in the sense that from a current workstation we can have several alternative transitions, each one corresponding to a dierent allocated segment. Therefore in order to represent this information of the routing algorithm, from each CBGi we will construct the so called Routing Graph (RG) to the destination workstation wi, RGi=(Q′, F ′), where Q ⊆ V × V × SG∗ represents the set of states in which a conveyor-load can be found. ALGORITHM 2 Construction of the RGi = (Q′, F ′) Input: CBGi = (Q, F ) Output: RGi = (Q′, F ′) begin next-level := { (w, w, ε)| (w, w) ∈ Q} Q′ := next-level; F ′ := ∅; while next-level ̸= ∅ do current-level := next-level; next-level := ∅; for each (w1, w2, r) ∈ current-level do for each ((w1, w2), X, S, (w3, w4)) ∈ F do for each c ∈ S do if (c ∈ R(w1, wi)) and (X = A) then next-level := next-level ∪{ (w3, w4, r&c)} ;
Q′ := Q′ ∪ { (w3, w4, r&c)} ;
F ′ := F ′ ∪ { ((w1, w2, r), X, c, (w3, w4, r&c))} ; endif if (r = c&t) and (X = R) then next-level := next-level ∪{ (w3, w4, t)} ;
Q′ := Q′ ∪ { (w3, w4, t)} ;
F ′ := F ′ ∪ { ((w1, w2, c&t), X, c, (w3, w4, t))} ; endif endfor endfor endfor endwhile end The state is characterized by the workstations of the head trailer and the tail trailer, respectively, and the sequence of segments that, in this state, the conveyor-load maintains allocated; F ′ ⊆ Q′ × { A, R} × SG × Q′ is the set of arcs that represents the transition from a state to another by the movement of the head trailer or tail trailer. The movement of the head trailer allocates (A) the segment specied in the arc. Observe, that now in the RGi a path from a state (w, w, ϵ), w̸=wi, that corresponds to the birth of a conveyor-load in the workstation w, to the state (wi, wi, ϵ), represents the routing of a conveyor-load in the warehouse distribution center from the source workstation w to the destination workstation wi. So, in order to obtain this RGi = (Q′, F ′) from the corresponding CBGi(Q, F ), we apply the algorithm 2 (Note: with the symbol &, in the algorithm, we denote the concatenation operation of two strings) In the Fig. 5 the RG0, obtained from the CBG0 of the Fig. 4. Applying the previous algorithm, we use the solid arcs to represent the segment allocation, and the dashed arcs to represent the segment release. 5
In the previous section we have obtained the RAS abstraction of the warehouse distribution center plus the considered path selection algorithm. This abstraction A,sl1
A,sl3 R,sa1
R,sa1 A,sa1 2,1,sa1 R,sa1 R,sa1 2 l s , R 0,3,sl3 2 a s , R lsRwh,wt 3 , 0,0, A,sa2 3,1,sl1,
sa2 A,sl3
A,sl2
A,sa2
A,sl2
A,sa2 3,1,sl1,
sl2 A,sl3 3,1,sa1
,sa2 A,sl3 3,1,sa1
,sl2 A,sl3
A,sl2 3,2,sl2 A,sl3 wh , wt
3,3, A,sl3 is composed by the resources : The set SG of segments; and the set of processes : the set of routing processes to a destination workstation, each one represented by means of the corresponding Routing Graph. From these elements, in this section we proceed to the construction of a Petri Net integrating all processes and all resources.
First, from the RGi(Q′, F ′), we construct the Petri Net Ni = ⟨P0i ∪ P si, Ti, Fi⟩ representing the state space of a conveyor-load born in the warehouse distribution center with destination workstation wi. This construction proceeds according to the following rules. 1. Add a place to the set P si for each vertex of the RGi, (w1, w2, s) ∈ Q′ such that w1 ̸= w2. The name of the place will be formed by the concatenation of identiers of the workstations of the head and tail trailer, w1 and w2, respectively, and the sequence of segments that remain allocated for this conveyor-load and represented by s. All these places are unmarked at the initial marking M0, because in the initial state there are not conveyor-loads in transit. We call these places process places. 2. Add a unique place poi, P oi = { poi} , corresponding to the fusion of states of the form (w, w, ϵ) ∈ Q′. The initial marking of this place will be equal to the maximum number of conveyor-loads that can be simultaneously in transit to the destination workstation wi. If this number is not limited, or it its unknown, then we don’t need to add a place poi, i.e. the number of conveyor-loads with destination workstation wi, in this network, is only limited by the available segments. These places will be called idle places. 3. Add a transition to the set Ti for each arc of the graph RGi. For an arc ((w1, w2, s), X, c, (w3, w4, r)) ∈ F ′, the name of the transition will be w1&w2&s&w3&w4&r. (The concatenation of this strings identifying the elements of the arcs). 4. For each arc ((w1, w2, s), X, c, (w3, w4, r)) ∈ F ′, w1 ̸= w2, add an arc from the place w1&w2&s to the transition w1&w2&s w3&w4&r, and an arc from this transition to the place w3&w4&r. 5. For each arc ((w, w, s), X, c, (w3, w4, r)) ∈ F ′ add an arc from the idle place p0i (if there exists) to the transition w&w&s&w3&w4&r, and an arc from this transition to the place w3, w4, r.
Observe that the net Ni, obtained following the rules of the preceding paragraphs, is a strongly connected state machine. In eect, by construction, each transition has only one input place and only one output place because a transition has been added for each arc in the graph RGi, and the places correspond to the both ends of the directed arc. Moreover, it is a strongly connected state machine because all vertex in RGi, (w1, w2, s), is reachable by a path from a source vertex (w, w, ϵ), since the construction of RGi requires that we can construct the sequence of allocated segments s from a source vertex; and from a vertex (w1, w2, s) always exists a path to the destination vertex (w, w, ϵ). Taking into account that place P0i represent the fusion of all vertices (w, w, ϵ) of the graph RGi, we can conclude that the net Ni is strongly connected. Additionally, we can see that all circuits of Ni contain the place p0, because the original RGi is acyclic. After all these transformations we obtain a set of strongly connected state machines Ni, each one corresponding to a dierent destination workstation in the warehouse distribution center. The last step to obtain the RAS view of the warehouse distribution center is the addition of the resources, that, in this case, they are the segments connecting the workstations, and their integration with to the state machines. This can be done state machine by state machine and constructing the full model by fusion of the resource places with the same name. That is, we are constructing the model in modular way. The two steps to be applied are: 1. Add a place pc to the set PR for each segment c ∈ SG of in the warehouse distribution center. The initial marking of this place will be equal to the maximum number of trailers that can be in transit simultaneously in the segment. (Normally. it will be equal to one representing tha availability of the segment). 2. For each arc of the graph RGi of the form ((w1, w2, s), A, c, (w3, w4, r)) ∈ F ′, add an arc from the place pc, (resource place representing the segment c) to the transition w1&w2&s&w3&w4&r. This arc, in the Petri Net, will represent the allocation of the segment c. For each arc of the graph RGi of the form ((w1, w2, s), R, c, (w3, w4, r)) ∈ F ′ add an arc from the transition w1&w2&s&w3&w4&r to the place c. This arc in the Petri Net represents the release of the segment c.
We denote this net by NiR, representing the routing of the conveyor-loads to the destination workstation wi, and the competition for the resource/segments. The full model is obtained from the dierent NiR by the fusion of the resource places (segments places) with the same name that appear in dierent NiR. The Fig. 6 represents, in an schematic way, the full Petri Net corresponding to the example in Fig. 2. In this Fig. 2 the names of places and transitions have been simplied in order to maintain readable. In order to identify the states of the conveyor-loads with the places that represent them, we have used the simplied notation hi+tj ; that it means that the head trailer is in workstation i and the tail trailer is in workstation j.
The nal part of this section is devoted to prove that the obtained Petri
Nets for warehouse distribution centers with minimal path selection algorithms
belong to the subclass of Petri Nets named S4P R [
i∈IN { p0i } .
(c) PR = { r1, r2, . . . , rn} , n > 0. 2. T = ∪i∈IN Ti, Ti ̸= ∅, Ti ∩ Tj = ∅, for all i ̸= j 3. For all i ∈ IN , the subnet Ni generated by PSi ∪ { p0i } ∪ Ti is a strongly connected state machine, such that every cycle contains p0i . 4. For each r ∈ PR there exists a minimal PSemiow, yr ∈ IN| P | , such that { r} = | yr| ∩ PR, yr[r] = 1, P0 ∩ | yr| = ∅, and PS ∩ | yr| ̸ = ∅. 5. PS = ∪r∈PR (| yr| \ { r} ).
Each place p0i is called idle place. Places of PR are called resource places being unique for the whole model. The Places of PS are called process places. This definition must be completed with the denition of the acceptable initial markings . Initial markings represent no activity in the system, allowing the routing of each conveyor-load in isolation.
Denition 2 Let N = ⟨P0 ∪ PS ∪ PR, T, C⟩ be a S4P R net. An initial marking m0 is acceptable for N if and only if: (1) ∀i ∈ IN , m0[p0i ] > 0. (2) ∀p ∈ PS , m0[p] = 0. (3) ∀r ∈ PR, m0[r] ≥ maxp∈| yr|\{ r} yr[p].
From the previous denitions and the procedures described in the sections 4 and 5 to obtain the Petri Net model of an warehouse distribution center the following result can be easily veried.
Proposition 1 Given an warehouse distribution center specied by means of a framework and a minimal adaptive routing algorithm, the Petri Net model obtained through the procedure described in sections 4 and 5, belongs to the class of S4P R net systems.
Proof (Sketch of the proof ). In the section 5, after the rules to obtain the Petri Nets Ni from the corresponding Routing Graph RGi, we have proven that each Ni is a strongly connected state machine, and for all Ni,Nj , i ̸= j, they are disjoint net systems. We have also proven that every cycle of each strongly connected state machine Ni contains P0i . Therefore, to complete the proof we only need to prove the existence of a unique p-semiow yr ∈ IN| P | for each resource r. But this is very easy to proof because from each transition where the resource place r inputs (the resource is allocated) , there exists a unique path, in the strongly connected state machine, to reach each transition where r outputs (the resource is released) . Moreover, all transitions where r is an output place in the state machine Ni are connected by means of a minimal path from some transition where r is an input place. Therefore, the resource r plus all the process places dening the minimal paths connecting the output transitions of r and the input transitions of r form the p-semiow that it is unique because we are dealing with the nets Ni that they are state machines. Observe that the previous result is also true for non-regular frameworks because we are considering in an explicit way the paths to a destination workstation. Therefore, non regularity does not aect the nal Petri Net. Nevertheless, nonminimality of the path selection algorithms can lead to more general class of nets than the S4P R in the case of existence of cycles in the followed route by some conveyor-load. Once we have characterized the type of nets we can obtain, we can use the developed theory for S4P R, trying to interpret these results from the point of view of the warehouse distribution centers, in the next section. In some cases we will see that we arrive to some negative results. 6
The Petri Net model obtained in the previous section belong to the S4P R class. Therefore, we can take advantage of this property and use the theoretical results about the liveness characterization in S4P R. One of this results is presented in the following theorem.
Theorem 2 ([
An equivalent characterization to the previous one is based in the Petri Net
concept of siphon. A siphon is a set of places that if they become a set of empty
places, they remain empty forever (these is a structural denition of siphon but
we prefer to present the deep reason for the appearing of deadlocks in this class of
nets). Therefore, all output transitions of the places of the empty siphon will be
dead forever because at least an input place (that belong to the siphon) is empty
forever. The presence of one of this siphons in the net is potentially bad because
this siphon can become an empty siphon. The verication procedures search
for a siphon and a reachable marking under which the siphon is empty. Empty
siphons represent a generalization of the circular waits, because in a siphon we
can nd an intricate structure of superposed cycles of empty resources. For the
Petri Net in Fig. 6, you can nd the two following bad siphons Di={p1, p2, p3,
p4, p13, p15, p17−to−20, p22, p24, p25, p28, p30, p31, p33, p34, p36, p37, p39, p40,
p42, p43, p45, p46} and Dj ={p1, p2, p3, p4, p6, p13, p15, p17−to−20, p22, p24, p25,
p27, p28, p30, p31, p33, p34, p36, p37, p39, p40, p42, p43, p45, p46} . The deadlock
state described in section 2 corresponds to the reachable marking written as a
symbolic sum mr = p5 + p6 + 5 · p7 + 2 · p8 + · p9 + 2 · p10 + p29 + p32 + p38 + p44. The
reader can easily verify that the siphon Di is insuciently marked or he/she can
verify the mr satisfy the conditions of the theorem 2. Therefore, we conclude that
the proposed path selection algorithm is not deadlock-free. After the previous
analysis phase, the theory of S4P R nets gives results and methods to enforce
the liveness in the case of nets presenting deadlock states. These techniques
transform the initial Petri Net model in such a way that deadlock states become
not reachable. In some sense, they correspond to deadlock prevention techniques.
We can incorporate this phase because we are using Petri Nets as formal model
and they belong to the subclass of S4P R. The known synthesis approaches
enforcing liveness work on the bad siphons that can be found in the Petri Net
model. These techniques can be classied into two groups.
1. Centralized Approach: [
The design of deadlock-free minimal adaptive routing algorithms for warehouse
distribution centers is a complex and tedious task, for which the current
methodologies, in many cases, only supply trial and error procedures. The assistance to
the designer is very small in order to x the problem in the proposed algorithm.
In this paper we propose a methodology oriented to the design of deadlock-free
minimal adaptive routing algorithms trying to cope with all phases of the design.
The rst step in this methodology consists of the abstraction of the system in
order to retain only the elements of the system allowing the study of the appearing
of deadlocks. These elements are the segments of the warehouse distribution
center, that they are seen as the resources for which the routing processes compete
to send conveyor-loads to destination workstations. The other elements are the
routing processes itself that represent the routing sequence through the
framework according to the routing algorithm. The result of this abstraction process is
formalized by means of a Routing Graph for each possible destination
workstation. From the Routing Graphs and the segments we have obtained Petri Nets
that, for the class of routing algorithms that we are considering, belong to the
class of S4P R. Therefore, we prot that the class of S4P R is a well studied
subclass of Petri Nets and using the known results we can proceed with the analysis
and synthesis phases of our methodology. So, the deadlock-free property in the
warehouse distribution center correspond to the liveness-property in our Petri
Net model. The analysis of this liveness property can be done by two alternative
characterizations that have a good interpretation at the level of warehouse
distribution center. Algorithms and methods to verify the property can be found in
[
This work has been partially supported by the European Community’s Seventh Framework Programme under project DISC (Grant Agreement n. INFSO-ICT224498). This work has been also partially supported by the project CICYTFEDER DPI2006-15390.