# Multimodal Processes Rescheduling: Cyclic Steady States Space Approach

Authors: Grzegorz Bocewicz; Robert Wójcik; Zbigniew Antoni Banaszak; Paweł Pawlewski
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The paper concerns cyclic scheduling problems arising in a Multimodal Transportation Network (MTN) in which several unimodal networks (AGVs, hoists, lifts, etc.) interact with each other via common shared workstations as to provide a variety of demand-responsive material handling operations. The material handling transport modes provide movement of work-pieces between workstations along their manufacturing routes in the MTN. The goal is to provide a declarative framework enabling to state a constraint satisfaction problem aimed at AGVs fleet match-up scheduling taking into consideration assumed itineraries of concurrently manufactured product types. In that context, treating the different product types as a set of cyclic multimodal processes is the main objective to discuss the conditions sufficient for FMS rescheduling imposed by production orders changes. To conclude, the conditions sufficient for an FMS rescheduling imposed by changes of production orders treated as cyclic multimodal processes are stated as the paper’s main contribution.


---

## Body

## 1. Introduction

The design and operational issues arising in an Automated Guided Vehicle (AGV) served Flexible Manufacturing System (FMS) when deciding on how to achieve a desired system performance are usually hard to determine and evaluate. This is because productivity of an AGV-served flow shop producing a set of different kinds of products, repetitively, depends on both the job flow sequencing (aimed at maximizing throughput or minimizing cycle time) and the material handling system required to achieve a prespecified throughput, that is, AGVs fleet sizing, assignment and scheduling [1–5]. So, assuming a deterministic system where demand is known in advance and the processing times of each job on each machine is a known constant, in order to improve its productivity, the AGV fleet size and the scheduling/dispatching influence on the system throughput are usually examined [1, 6–9].In opposite to conventionally applied approach assuming AGVs fleet sizing, routing, and timetabling while matching up prescheduled multiproduct manufacturing flow (i.e., providing detailed transportation route and materials load/unload schedule between workstations in FMS), we propose AGVs following a Multimodal Transportation Network (MTN) concept. MTN can be seen as composition of several unimodal networks (AGVs, hoists, lifts, etc.) interacting with each other via common shared workstations as to provide a variety of demand-responsive material handling operations. The material handling transport modes provide movement of work-pieces between workstations along their manufacturing routes in the MTN. The MTN encompasses a well-known multimodal approach to freight transportation supply chains and passenger transportation systems. So, similarly to such systems having ability to use the appropriate mode of transport for movement of goods and people, the assumed material handling transport modes provide movement of work-pieces between workstations along their manufacturing routes in the MTN. In that context, assuming that the modes can be treated as cyclic local transportation processes, and material (e.g., work-pieces/tools) flows supported by them can be treated as multimodal processes, the problems considered can be seen either as aimed at designing of a multimodal network infrastructure guaranteeing assumed materials flow or focused on work-pieces routing ensuring lag-free workstations service.The problems arising concerning material transportation routing and scheduling belong to NP-hard ones [2]. Since the steady state of production flows has a cyclic character, hence servicing them AGV-served transportation processes (usually executed along loop-like routes) encompasses also cyclic behavior. That means that the periodicity of FMS [10] depends on both the periodicity of production flow cyclic schedule and following this schedule the AGVs periodicity. Of course, the Multimodal Transportation Network (MTN) throughput is maximized by the minimization of its cycle time.It seems to be obvious that not all the behaviors (including cyclic ones) are reachable under constraints imposed by the system’s structure. The similar observation concerns the system’s behavior that can be achieved in systems possessing specific structural constraints. Since system constraints determine its behavior, both the system structure and the desired cyclic schedule have to be considered simultaneously. So, the problem solution requires that the system structure must be determined for the purpose of processes scheduling, yet scheduling must be done to devise the system configuration. In that context, our contribution provides a discussion of some solvability issues concerning cyclic processes dispatching problems, especially the conditions guaranteeing solvability of the cyclic processes scheduling as well as direct and/or indirect transitions between assumed cyclic steady states. Their examination may replace exhaustive searches for solution satisfying required system capabilities.Many models and methods have been considered to date [11]. Among them, the mathematical programming approach [1, 12], max-plus algebra [13], constraint logic programming [14–16] evolutionary algorithms, Petri nets [17, 18], and heuristic frameworks [19] belong to the more frequently used. Most of these are oriented at finding a minimal cycle or maximal throughput while assuming deadlock-free processes flow. Note that processes’ operations are blocking if they must stay on a resource (e.g., the station, the machine) after finishing when the next resource is occupied by a job from another process. During this stay the resource is blocked for other processes. The approaches trying to estimate the cycle time from cyclic processes structure and the synchronization mechanism employed (i.e., mutual exclusion instances) while taking into account deadlock phenomena are quite unique.In our approach a declarative framework aimed at refinement and prototyping of the cyclic steady states for concurrently executed cyclic processes modelling material handling systems is employed. These systems are of the type of AGVs fleets in the flexible manufacturing systems (FMS) and are frequently encountered in industry. The following questions are the main focus of the research. Can the assumed material handling system, for example, AGVs, meet load/unload deadlines imposed by flow of scheduled work-pieces processing? Does there exist sufficient AGVS enabling to schedule the AGVs fleet as to ensure lag-free service of scheduled work pieces processing? So, the main question is Can the assumed AGVs fleet assignment reach its goal subject to constraints assumed on concurrent multiproduct manufacturing at hand?Moreover the declarative framework enables to state aproblem of multimodal processes rescheduling which boils down to searching for transient periods allowing the mutual reachability of MTN cyclic behaviors. In the case of MTNs, distinguishing many different cyclic steady states (cyclic behaviors), the following questions play a pivotal role. Does there exist the smooth (direct) transition between two assumed cyclic behaviors? What conditions guarantee the reachability of a given cyclic behavior from any other ones? Is it possible to come back to a given cyclic behavior from any disturbance-born one, for instance, caused by operation time delays, damage of devices, route modifications, and so forth?In other words, the paper’s objective concerns the MTN infrastructure assessment from the perspective of possible FMS oriented requirements imposed by AGVs fleet assignment, sizing, and scheduling (problems of cyclic processes scheduling and rescheduling). Due to the complexity implied in answering the above questions, the combined problem remains unsolved for all practical purposes. This is especially problematic as many manufacturing companies would stand to reap considerable rewards through better fleet assignment and scheduling. The presented approach addresses this through solving the combined rather than the separate problems individually.The rest of the paper is organized as follows. Section2 introduces the Automated Guided Vehicles System (AGVS) modelled in terms of concurrently flowing cyclic processes (SCCPs) and a cyclic steady state space concept. Section 3 regarding multimodal processes rescheduling provides a problem statement concerning AGVs fleet match-up scheduling with an assumed multiproduct manufacturing flow schedule. Sufficient conditions allowing one to search for states with mutual allocation as well as illustrative example of implementing them algorithm usage are discussed. The related work and concluding remarks are presented in Sections 4 and 5, respectively.


## 2. Multimodal Network Modeling

Considered case of multimodal processes rescheduling problem is presented on the example of Automated Guided Vehicle Systems (AGVS) modeled by Systems of Concurrently Flowing Cyclic Processes (SCCPs). To solve this kind of problems a nonempty state space, that is, containing nonempty set of possible cyclic behaviors, is required. For that reason the conditions guaranteeing cyclic behavior are presented, primarily. They are specified in terms of a declarative model formalism distinguishing the structure and behavior as the main components of an SCCP. Relationship linking the structure and reachable behaviors is the main subject of this section.


### 2.1. Model of AGVS

Automated Guided Vehicle Systems are used for material handling within a Flexible Manufacturing System (FMS) and provide asynchronous movement pallets of products through a network of guide paths between the workstations by the AGVs. Each workstation is connected to the guide path network by a pick-up/delivery station where pallets are transferred from/to the AGVs.In AGVS literature, most are related to AGVS design issues, which include determination of the number of vehicles required, flow path design, and route planning as well as vehicle dispatching and traffic management. Recently, an integrated problem of dispatching and conflict free routing of AGVs, that is, integrating the simultaneous assignment, scheduling, and conflict free routing of the vehicles, is receiving increasing attention. The above mentioned problems, in the general case, belong to the class of NP-hard problems. Since most processes observed in steady state manufacturing are periodic, cyclic schedules and following them, cyclic scheduling methods can be considered. Since cyclic schedules encompass repetitive character of manufacturing processes, the cyclic processes modeling approach seems to be a reasonable perspective [13–15].To present some of the design and operational issues that arise in repetitive manufacturing systems served by AGVs in network of loops layout with unidirectional material flow, a case example of a simple FMS is shown in Figure1. The concurrent multiproduct flows are depicted by bold green, blue, and orange color lines, while the transportation loop-like networks are distinguished by double solid line. Both kinds of material (jobs) and transportation (AGVs) flows shown in Figure 1 can be modeled in terms of Systems of Concurrently Flowing Cyclic Processes [14, 15] as shown in Figure 2. In turn, the SCCP framework provides a formal model enabling to state and resolve problems of AGV fleet size minimization as well as steady state cycle time minimization. The cycle time minimization is required to obtain maximum throughput rate.Figure 1
Example of an AGVS.Figure 2
Example of FMS-SCCP model of an AGVS.Eightlocal cyclic processes are considered, namely, P1, P2, P3, P4, P5, P6, P7, and P8. The processes follow the routes are composed of transportation sectors and machines (distinguished in Figure 2 by the set of resourcesR={R1,…,Rc,…,R33}, Rc—the cth resource). Some of the local cyclic processes are pipeline flow processes; that is, they contain streams (representing vehicles from Figure 1) of the processes following the same route while occupying different resources (sectors). For instance, processes P4, P5, and P6 contain two streams: P4={P41,P42}, P5={P51,P52}, and P6={P61,P62}, respectively, and P2 contains three streams: P2={P21,P22,P23}, that is, the processes (vehicles) moving along the same route. The remaining local processes contain unique streams: P1={P11}, P3={P31}, P7={P71}, and P8={P81}. In other words, the streams P11, P21, P22, P23, P31, P41, P42, P51, P52, P61, P62, P71, and P81 represent the 13 vehicles from Figure 1. The kth stream of the ith local process Pi is denoted by Pik.Apart from local processes, we consider threemultimodal processes (i.e., processes executed along the routes consisting of parts of the routes of local processes): mP1, mP2, and mP3.For example, the production route depicted by the orange line corresponds to the multimodal processmP1 supported by AGVs (arbitrarily given), which in turn encompass local transportation streams P11, P21, P23, and P42. This means that the production route specifying how a multimodal process is executed can be considered to be composed of parts of the routes of local cyclic processes.In the system considered each multimodal process consists of four streams:mPi={mPi1,mPi2,mPi3,mPi4}, i=1,2,3, which means that along each production route four work- pieces are processed serially (four balls on the one production lines in Figure 1).Processes can interact with each other through shared resources, that is, the transportation sectors. The routes of the considered local processes (streams) are as follows (see Figure2):
(1)p11=(R16,R3,R13,R6),p21=(R21,R8,R18,R9,R14,R6,R17,R5),p22=(R17,R5,R21,R8,R18,R9,R14,R6),p23=(R14,R6,R17,R5,R21,R8,R18,R9),p31=(R12,R19,R9,R5),p41=(R29,R7,R25,R8,R22,R11,R26,R10),p42=(R26,R10,R29,R7,R25,R8,R22,R11),p51=(R2,R20,R5,R24,R4,R27,R1,R23),p52=(R27,R1,R23,R2,R20,R5,R24,R4),p61=(R32,R4,R28,R7,R31),p62=(R31,R32,R4,R28,R7),p71=(R33,R7,R29,R10),p81=(R1,R27,R4,R30),
where R1-R2, R4-R11, R14, R17-R18, R20-R29, R31, and R32 (due to two streams of process P6, resources R31, R32 represent one sector) are resources shared by local processes, that is, by at least two streams, and R3, R12, R13, R15, R16, R19, R30, and R33 are the nonshared resources, that is, exclusively used by one stream only.In the general case, the routepik is the sequence of resources used in order to execute the operations of the stream Pik. Note that the streams P21, P22, and P23 which belong to P2 and the streams of processes P4, P5, and P6 follow the same route but start from different resources (these streams correspond to vehicles moving along the same route).Similarly the cyclic multimodal processesmP1, mP2, and mP3 follow the routes (see Figure 2) as follows:
(2)mp1k=(R3,R13,R6,R17,R5,R21,R8,R22,R11),11111111111111111111111111k=1,…,4,mp2k=(R2,R20,R5,R24,R4,R28,R7,R29,R10),11111111111111111111111111k=1,…,4,mp3k=(R1,R27,R4,R28,R7,R25,R8,R18,R9,R15,R12),111111111111111111111111111111111k=1,…,4.
Let us assume that mp1k, mp2k, and mp3k can be seen as follows (see Figure 2):
(3)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)),pppppppppppppppppppppplpk=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R29,R10)),ppppppppppppppppppppppplk=1,…,4,mp3k=((R1,R27,R4),(R28,R7),(R25,R8),(R18,R9),(R15,R12)),k=1,…,4,
where one has the following: (R3,R13,R6), (R17,R5), (R21,R8), and (R22,R11)—subsequences of routes p11, p21, p23, and p42 defining the transportation sections of mp1k; (R2,R20,R5), (R24,R4), (R28,R7), and (R29,R10)—subsequences of routes p51, p52, p61, and p71 defining the transportation sections of mp2k; and (R1,R27,R4), (R28,R7), (R25,R8), (R18,R9), and (R15,R12)—subsequences of routes p81, p62, p41, p22, and p31 defining the transportation sections of mp3k.Let us assume also that the considered SCCPs follow the constraints stated below [15]:(i)
a new subsequent operation of the local process may start on a required resource only if the current operation has been completed and the resource has been released;(ii)
each new consecutive operation in the multimodal process may start its execution on an assigned resource only if the current operation has been completed and the resource has been released and an appropriate local process begins its consecutive operation on this resource;(iii)
local/multimodal processes share common resources in the mutual exclusion mode, the operation of a local/multimodal process can only be suspended if the necessary resource is occupied, suspended processes cannot be released, and processes are nonperceptible; that is, a resource may not be taken from a process as long as it is used by it;(iv)
the SCCP resources can be shared by local and multimodal processes as well as by both of them;(v)
multimodal processes encompassing production flow conveyed by AGVs follow local transportation routes;(vi)
different multimodal processes can be executed simultaneously along the same local process;(vii)
local and multimodal processes execute cyclically with periodsα and mα, respectively; resources occur uniquely in each transportation route;(viii)
in a cyclic steady state, eachith stream must cover its local route the same number of times.A resource conflict (caused by the application of the mutual exclusion protocol) is resolved with the aid of a priority dispatching rule [14–16], which determines the order in which streams access shared resources. For instance, in the case of the resource R5, the priority dispatching rule σ50=(P22,P23,P51,P52,P21) determines the order in which streams of local processes can access the shared resource R5; in the case considered the stream P22 is allowed to access as first, then the stream P23 as next, then streams P51, P52, and P21, and then once again P22, and so on. The stream Pik occurs the same number of times (in the considered system once) in each dispatching rule associated with the resources featuring in its route (in the case considered each stream Pik occurs uniquely). The SCCP shown in Figure 2 is specified by the following set of dispatching rules: Θ={Θ0,Θ1}, where Θ0={σ10,…,σ330} is set of rules determining the orders of local processes and Θ1={σ11,…,σ331} is set of rules determining the orders of multimodal processes.In general, the following notation is used.(i)
A sequencepik=(pi,1k,pi,2k,…,pi,jk,…,pi,lr(i)k) specifies the route of the stream of a local processPik (the kth stream of the ith local process Pi). Its components define the resources used in the execution of operations, where pi,jk∈R (the set of resources R={R1,R2,…,Rc,…,Rm}) denotes the resources used by the kth stream of the ith local process in the jth operation; in the rest of the paper, thejth operation executed on the resourcepi,jkin the streamPik will be denoted by oi,jk; lr(i) is the length of the cyclic process route (all streams of Pi are of the same length). For example, the route p11=(R16,R3,R13,R6) of the stream of process P1 (Figure 2) is the sequence p11=(p1,11,p1,21,p1,31,p1,41), where the first element p1,11 is equal to R16, whereas the second, p1,21=R3, and so on, p1,31=R13, p1,41=R6.(ii)
xi,jk(l)∈ℕ is the timing of commencement of operation oi,jk in the lth cycle.(iii)
tik=(ti,1k,ti,2k,…,ti,jk,…,ti,lr(i)k) specifies the operation times of local processes, where ti,jk denotes the time of execution of operation oi,jk.(iv)
mpik=(mpri1q1(ai1,bi1),mpri2q2(ai2,bi2),…,mpriyqy(aiy,biy)) specifies the route of the streammPikfrom the multimodal processmPi (the kth stream of the ith multimodal process mPi), where
(4)mpriq(a,b)={(pi,aq,pi,a+1q,…,pi,bq),a≤b,(pi,aq,pi,a+1q,…,pi,lr(i)q,pi,1q,…,pi,b-1q,pi,bq)a>b,ppppppppppppppppppppppppa,b∈{1,…,lr(i)},is the subsequence of the routepiq=(pi,1q,pi,2q,…,pi,jq,…,pi,lr(i)q) containing elements from pi,aq to pi,bq.In other words, the transportation routempi is a sequence of parts of routes of local processes. For instance, the route followed by process mP1 (see Figure 2) is as follows: mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)), where mpr11(2,4)=(R3,R13,R6); mpr21(7,8)=(R17,R5); mpr23(1,2)=(R21,R8), mpr42(5,6)=(R22,R11).(v)
mxi,jk(l)∈ℕ is the timing of commencement of operation moi,jk in the lth cycle.(vi)
mtik=(mti,1k,mti,2k,…,mti,jk,…,mti,lm(i)k) specifies the operation times of multimodal processes, where mti,jk denotes the time of execution of operation moi,jk and lm(i) is the length of the cyclic process route mpik.(vii)
Θ={Θ0,Θ1} is the set of priority dispatching rules, Θi={σ1i,σ2i,…,σci,…,σmi} is the set of priority dispatching rules for local (i=0)/multimodal (i=1) processes where σci=(sc,1i,…,sc,di,…,sc,lp(c)i) are sequence components which determine the order in which the processes can be executed on the resource Rc, sc,d0∈H (where H is the set of local streams, e.g., in the case presented in Figure 2, H={P11,P21,P22,P23,P31,P41,P42,P51,P52,P61,P62,P71}), and sc,d1∈mH (where mH is the set of multimodal streams, e.g., in case from Figure 2, mH={mP1k,mP2k,mP3k∣k=1⋯4}).Using the above notation, a SCCP can be defined as a tuple:
(5)SC=((R,SL),SM),
where one has the following: R={R1,R2,…,Rc,…,Rm}—the set of resources, m—the number of resources, SL=(U,T,Θ0)—the structure of local processes, that is, U={p11,…,p1ls(1),…,pn1,…,pnls(n)}—the set of routes of local process, ls(i)—the number of streams belonging to the process Pi, n—the number of local processes, T={t11,…,t1ls(1),…,tn1,…,tnls(n)}—the set of sequences of operation times in local processes, Θ0={σ10,σ20,…,σc0,…,σm0}—the set of priority dispatching rules for local processes, SM=(M,mT,Θ1)—the structure of multimodal processes, that is, M={mp11,…,mp1lsm(1),…,mpw1,…,mpwlsm(n)}—the set of routes of a multimodal process, lsm(i)—the number of streams belonging to the process mPiw—the number of multimodal processes, mT={mt11,…,mtwlsm(1),…,mtn1,…,mtwlsm(n)}—the set of sequences of operation times in multimodal processes, and Θ1={σ11,σ21,…,σc1,…,σm1}—the set of priority dispatching rules for multimodal processes.The SCCP model (5) can be seen as a multilevel model, cf. Figure 3, that is, a model composed of an “R level” (resources), an “SL level” (local cyclic processes), and an “SM1 level” (multimodal cyclic processes), as well as an “SMq level” (the qth metamultimodal process). The SL level is defined by the transportation routes structure following the set U of local processes and the set of parameters Θ determining the required system behavior. In turn, the SM1 level takes into account multimodal processes, as well as metamultimodal processes (SM2 level) composed of multimodal processes from the SM1 level. In other words, it is assumed that the variables describing SMq are the same as in the case of SM, whereas the routes of the multimodal process of the qth level remain composed of the processes from the (q-1)th level. The presented model is an extended version of a simplified model limited to R and SL levels, which is introduced in [15].Figure 3
Multilayered model of the SCCP from Figure2.Therefore, in general, theSC=((R,SL),SM) model can be seen as composed of lp levels as follows:
(6)SClp=(((((R,SL),SM1),SM2),…,SMq),…,SMlp).
The SClp model emphasizes structural characteristics of the SCCP modeled. In turn, the behavioral characteristics can be specified in terms of the admissible states reachability concept, that is, either taking into account the state space concept including both cyclic steady states and leading to them transient states [16] or the cyclic steady state space only [14, 15].The second way, which does not take into account initial states leading through the transient states to the cyclic steady states, seems to be quite close to the cyclic scheduling methods widely used in many real-life cases [9, 11].In that context the relevant multilevel cyclic scheduleXlp encompassing the SCCP behavior on each of its processes level, that is, local SL and multimodal SMlp processes, can be defined as follows:
(7)Xlp=(((((X,α),(m1X,m1α)),…,),…,(mqX,mqα)),…,(mlpX,mlpα)),
where one has the following: X,α/(mqX,mqα)—sequence of commencement of operations and periodicity of local/multimodal (ith level) processes executions.It should also be noted that the scheduleXlp can be defined as a sequence of ordered pairs describing behaviors of local (X,α) and multimodal (miX,miα) processes, where X is a sequence of timings xi,jk (for l=0th cycle) of commencement of operations oi,jk from streams Pik executed along local processes X=(x1,11,x1,21,…,xn,lr(n)ls(n)), and by analogy, the sequence mqX=(mqx1,11,mqx1,21,…,mqxw(q),lm(w,q)lsm(w,q)) consists of the timing of commencement of multimodal processes operations (from the qth level, where one has the following: w(q)—the number of multimodal processes at the qth level, lsm(i,q)—the number of streams of the ith process at the qth level, and lm(i,q)—the number of operation of the ith process at the qth level).Variablesxi,jk/mqxi,jk∈ℤ describe the timing of commencement of operations in the qth cycle of the SCCP cyclic steady state behavior: xi,jk(l)=xi,jk+l·α/mqxi,jk(l)=mqxi,jk+l·mqα.Since values ofxi,jk/mqxi,jk follow from system structure, hence the cyclic behavior Xlp of SCCP is determined by its structure SMlp. Moreover, the multimodal processes behavior (miX,miα) also depends on the local cyclic processes behavior (X,α).In the general case, besides depending on the structural characteristics of SCCP the values of the considered variablesxi,jk/mqxi,jk depend on constraints from the mutual exclusion protocol, that is, the set of priority dispatching rules Θ, operation times, and so forth [14, 15] as well as on the way the local and multimodal processes interacting with each other. For example, in case of the two levels structure model, that is, including levels SL and SM as shown in Figure 2, the constraints determining xi,jk/mqxi,jk can be expressed by the following rules [15]:(i)
for local processes: the timing of commencement of operation oi,jk beginning states for a maximum of the completion time of operation oi,j-1k preceding oi,jk and the release time (with delay Δt) of the resource pi,jk awaiting for oi,j execution is as follows:
(8)momentofoperationoi,jkbeginning=max{(momentofpi,jkrelease+lagtimeΔt),pppppppp(momentofoperationoi,j-1kcompletion)}i=1,…,n;j=1,…,lr(i);k=1,…,ls(i);(ii)
for multimodal processes: the timing of commencement of operation moi,jk beginning is equal to the nearest admissible value (determined by set 𝒳i,jk of values mxi,jk) being a maximum of both the completion time of operation moi,j-1k preceding moi,j and the release time (lag time Δtm) of the resource mpi,jk awaiting for moi,j execution. Consider
(9)momentofoperationmoi,jkbeginning=⌈max{(momentofmpi,jkrelease+lagtimeΔtm),momentofoperationmoi,j-1kcompletion}⌉𝒳i,jki=1,…,n;j=1,…,lm(i);k=1,…,lsm(i),
where one has the following: 𝒳i,jk—set of values mxi,jk following the set of local processes X, (𝒳i,jk—the set of moments when operation moi,jk of multimodal process may use required local process) and ⌈a⌉B—the smallest integer greater than or equal to a in terms of the set B: ⌈a⌉B=min{k∈B:k≥a}.In other words, the timing of commencement of operationmoi,j belongs to the set 𝒳i,jk and being coincident with operation processes by relevant local transportation process Pi.The constraints determining (due to introduced rules (8) and (9)) the timing of commencement of operations for the SCCP from Figure 2 are gathered in Tables 1 and 2.Table 1
Constraints determining the local processes behavior of the SCCP from Figure2.
Constraints of the local processes
x
1,1
1
=
x
1,4
1
+
t
1,4
1
-
α
x
4,1
2
=
max
{
(
x
4,8
1
+
Δ
t
-
α
)
,
(
x
4,8
2
+
t
4,8
2
-
α
)
}
—
x
1,2
1
=
x
1,1
1
+
t
1,1
1
x
4,2
2
=
max
{
(
x
4,1
1
+
Δ
t
)
,
(
x
4,1
2
+
t
4,1
2
)
}
x
5,1
2
=
max
{
(
x
5,7
1
+
Δ
t
-
α
)
,
(
x
5,8
2
+
t
5,8
2
-
α
)
}
x
1,3
1
=
x
1,2
1
+
t
1,2
1
x
4,3
2
=
max
{
(
x
4,2
1
+
Δ
t
)
,
(
x
4,2
2
+
t
4,2
2
)
}
x
5,2
2
=
max
{
(
x
5,8
1
+
Δ
t
-
α
)
,
(
x
5,1
2
+
t
5,1
2
)
}
x
1,4
1
=
max
{
(
x
2,7
1
+
Δ
t
)
,
(
x
1,3
1
+
t
1,3
1
)
}
x
4,4
2
=
max
{
(
x
4,3
1
+
Δ
t
)
,
(
x
4,3
2
+
t
4,3
2
)
}
x
5,3
2
=
max
{
(
x
5,1
1
+
Δ
t
)
,
(
x
5,2
2
+
t
5,2
2
)
}
—
x
4,5
2
=
max
{
(
x
4,4
1
+
Δ
t
)
,
(
x
4,4
2
+
t
4,4
2
)
}
x
5,4
2
=
max
{
(
x
5,2
1
+
Δ
t
)
,
(
x
5,3
2
+
t
5,3
2
)
}
x
2,1
1
=
max
{
(
x
2,6
3
+
Δ
t
-
α
)
,
(
x
2,8
1
+
t
2,8
1
-
α
)
}
x
4,6
2
=
max
{
(
x
2,7
3
+
Δ
t
)
,
(
x
4,5
2
+
t
4,5
2
)
}
x
5,5
2
=
max
{
(
x
5,3
1
+
Δ
t
)
,
(
x
5,4
2
+
t
5,4
2
)
}
x
2,2
1
=
max
{
(
x
4,7
2
+
Δ
t
-
α
)
,
(
x
2,1
1
+
t
2,1
1
)
}
x
4,7
2
=
max
{
(
x
4,6
1
+
Δ
t
)
,
(
x
4,6
2
+
t
4,6
2
)
}
x
5,6
2
=
max
{
(
x
5,4
1
+
Δ
t
)
,
(
x
5,5
2
+
t
5,5
2
)
}
x
2,3
1
=
max
{
(
x
2,8
3
+
Δ
t
-
α
)
,
(
x
2,2
1
+
t
2,2
1
)
}
x
4,8
2
=
max
{
(
x
4,7
1
+
Δ
t
)
,
(
x
4,7
2
+
t
4,7
2
)
}
x
5,7
2
=
max
{
(
x
5,5
1
+
Δ
t
)
,
(
x
5,6
2
+
t
5,6
2
)
}
x
2,4
1
=
max
{
(
x
2,1
3
+
Δ
t
)
,
(
x
2,3
1
+
t
2,3
1
)
}
—
x
5,8
2
=
max
{
(
x
5,6
1
+
Δ
t
)
,
(
x
5,7
2
+
t
5,7
2
)
}
x
2,5
1
=
max
{
(
x
2,2
3
+
Δ
t
)
,
(
x
2,4
1
+
t
2,4
1
)
}
x
5,1
1
=
max
{
(
x
5,5
2
+
Δ
t
-
α
)
,
(
x
5,8
1
+
t
5,8
1
-
α
)
}
—
x
2,6
1
=
max
{
(
x
2,3
3
+
Δ
t
)
,
(
x
2,5
1
+
t
2,5
1
)
}
x
5,2
1
=
max
{
(
x
5,6
2
+
Δ
t
-
α
)
,
(
x
5,1
1
+
t
5,1
1
)
}
x
6,1
1
=
max
{
(
x
6,3
2
+
Δ
t
-
α
)
,
(
x
6,5
1
+
t
6,5
1
-
α
)
}
x
2,7
1
=
max
{
(
x
2,4
3
+
Δ
t
)
,
(
x
2,6
1
+
t
2,6
1
)
}
x
5,3
1
=
max
{
(
x
2,5
3
+
Δ
t
)
,
(
x
5,2
1
+
t
5,2
1
)
}
x
6,2
1
=
max
{
(
x
5,1
2
+
Δ
t
)
,
(
x
6,1
1
+
t
6,1
1
)
}
x
2,8
1
=
max
{
(
x
5,7
2
+
Δ
t
)
,
(
x
2,7
1
+
t
2,7
1
)
}
x
5,4
1
=
max
{
(
x
5,8
2
+
Δ
t
-
α
)
,
(
x
5,3
1
+
t
5,3
1
)
}
x
6,3
1
=
max
{
(
x
6,5
2
+
Δ
t
-
α
)
,
(
x
6,2
1
+
t
6,2
1
)
}
—
x
5,5
1
=
max
{
(
x
6,4
2
+
Δ
t
)
,
(
x
5,4
1
+
t
5,4
1
)
}
x
6,4
1
=
max
{
(
x
4,5
2
+
Δ
t
)
,
(
x
6,3
1
+
t
6,3
1
)
}
x
2,1
2
=
max
{
(
x
2,8
1
+
Δ
t
-
α
)
,
(
x
2,8
2
+
t
2,8
2
-
α
)
}
x
5,6
1
=
max
{
(
x
8,3
1
+
Δ
t
)
,
(
x
5,5
1
+
t
5,5
1
)
}
x
6,5
1
=
max
{
(
x
6,2
2
+
Δ
t
)
,
(
x
6,4
1
+
t
6,4
1
)
}
x
2,2
2
=
max
{
(
x
2,1
1
+
Δ
t
)
,
(
x
2,1
2
+
t
2,1
2
)
}
x
5,7
1
=
max
{
(
x
8,2
1
+
Δ
t
)
,
(
x
5,6
1
+
t
5,6
1
)
}
—
x
2,3
2
=
max
{
(
x
2,2
1
+
Δ
t
)
,
(
x
2,2
2
+
t
2,2
2
)
}
x
5,8
1
=
max
{
(
x
5,4
2
+
Δ
t
)
,
(
x
5,7
1
+
t
5,7
1
)
}
x
6,1
2
=
max
{
(
x
6,3
2
+
Δ
t
)
,
(
x
6,5
2
+
t
6,5
2
-
α
)
}
x
2,4
2
=
max
{
(
x
4,5
1
+
Δ
t
)
,
(
x
2,3
2
+
t
2,3
2
)
}
—
x
6,2
2
=
max
{
(
x
6,2
1
+
Δ
t
)
,
(
x
6,1
2
+
t
6,1
2
)
}
x
2,5
2
=
max
{
(
x
2,4
1
+
Δ
t
)
,
(
x
2,4
2
+
t
2,4
2
)
}
x
3,1
1
=
x
3,4
1
+
t
3,4
1
-
α
x
6,3
2
=
max
{
(
x
8,4
1
+
Δ
t
)
,
(
x
6,2
2
+
t
6,2
2
)
}
x
2,6
2
=
max
{
(
x
2,5
1
+
Δ
t
)
,
(
x
2,5
2
+
t
2,5
2
)
}
x
3,2
1
=
x
3,1
1
+
t
3,1
1
x
6,4
2
=
max
{
(
x
6,4
1
+
Δ
t
)
,
(
x
6,3
2
+
t
6,3
2
)
}
x
2,7
2
=
max
{
(
x
2,1
1
+
Δ
t
)
,
(
x
2,6
2
+
t
2,6
2
)
}
x
3,3
1
=
max
{
(
x
2,7
2
+
Δ
t
)
,
(
x
3,2
1
+
t
3,2
1
)
}
x
6,5
2
=
max
{
(
x
7,3
1
+
Δ
t
)
,
(
x
6,4
2
+
t
6,4
2
)
}
x
2,8
2
=
max
{
(
x
1,1
1
+
Δ
t
-
α
)
,
(
x
2,7
2
+
t
2,7
2
)
}
x
3,4
1
=
x
3,3
1
+
t
3,3
1
—
—
—
x
7,1
1
=
x
7,4
1
+
t
7,4
1
-
α
x
2,1
3
=
max
{
(
x
2,8
2
+
Δ
t
-
α
)
,
(
x
2,8
3
+
t
2,8
3
-
α
)
}
x
4,1
1
=
max
{
(
x
7,4
1
+
Δ
t
-
α
)
,
(
x
4,8
1
+
t
4,8
1
-
α
)
}
x
7,2
1
=
max
{
(
x
6,5
1
+
Δ
t
)
,
(
x
7,1
1
+
t
7,1
1
)
}
x
2,2
3
=
max
{
(
x
2,1
2
+
Δ
t
)
,
(
x
2,1
3
+
t
2,1
3
)
}
x
4,2
1
=
max
{
(
x
6,1
2
+
Δ
t
)
,
(
x
4,1
1
+
t
4,1
1
)
}
x
7,3
1
=
max
{
(
x
4,4
2
+
Δ
t
)
,
(
x
7,2
1
+
t
7,2
1
)
}
x
2,3
3
=
max
{
(
x
2,2
2
+
Δ
t
)
,
(
x
2,2
3
+
t
2,2
3
)
}
x
4,3
1
=
max
{
(
x
4,6
2
+
Δ
t
-
α
)
,
(
x
4,2
1
+
t
4,2
1
)
}
x
7,4
1
=
max
{
(
x
4,3
2
+
Δ
t
)
,
(
x
7,3
1
+
t
7,3
1
)
}
x
2,4
3
=
max
{
(
x
2,3
2
+
Δ
t
)
,
(
x
2,3
3
+
t
2,3
3
)
}
x
4,4
1
=
max
{
(
x
2,3
1
+
Δ
t
)
,
(
x
4,3
1
+
t
4,3
1
)
}
—
x
2,5
3
=
max
{
(
x
2,4
2
+
Δ
t
)
,
(
x
2,4
3
+
t
2,4
3
)
}
x
4,5
1
=
max
{
(
x
4,8
2
+
Δ
t
-
α
)
,
(
x
4,4
1
+
t
4,4
1
)
}
x
8,1
1
=
max
{
(
x
5,3
2
+
Δ
t
)
,
(
x
8,4
1
+
t
8,4
1
-
α
)
}
x
2,6
3
=
max
{
(
x
2,5
2
+
Δ
t
)
,
(
x
2,5
3
+
t
2,5
3
)
}
x
4,6
1
=
max
{
(
x
4,1
2
+
Δ
t
)
,
(
x
4,5
1
+
t
4,5
1
)
}
x
8,2
1
=
max
{
(
x
5,2
2
+
Δ
t
)
,
(
x
8,1
1
+
t
8,1
1
)
}
x
2,7
3
=
max
{
(
x
2,6
2
+
Δ
t
)
,
(
x
2,6
3
+
t
2,6
3
)
}
x
4,7
1
=
max
{
(
x
4,2
2
+
Δ
t
)
,
(
x
4,6
1
+
t
4,6
1
)
}
x
8,3
1
=
max
{
(
x
6,3
1
+
Δ
t
)
,
(
x
8,2
1
+
t
8,2
1
)
}
x
2,8
3
=
max
{
(
x
2,7
2
+
Δ
t
)
,
(
x
2,7
3
+
t
2,7
3
)
}
x
4,8
1
=
max
{
(
x
7,1
1
+
Δ
t
-
α
)
,
(
x
4,7
1
+
t
4,7
1
)
}
x
8,4
1
=
x
8,3
1
+
t
8,3
1Table 2
Constraints (9) determining the multimodal processes behavior of the SCCP from Figure 2.
Constraints for streammP11
Constraints for streammP21
Constraints for streammP31
m
x
1,1
1
=
⌈
max
{
(
m
x
1,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
1,9
1
+
m
t
1,9
1
-
m
α
)
}
⌉
𝒳
1,1
1 mx1,21=⌈max{(mx1,34+Δtm-mα),(mx1,11+mt1,11)}⌉𝒳1,11 mx1,31=⌈max{(mx1,44+Δtm-mα),(mx1,21+mt1,21)}⌉𝒳1,31 mx1,41=⌈max{(mx1,54+Δtm-mα),(mx1,31+mt1,31)}⌉𝒳1,41 mx1,51=⌈max{(mx2,41+Δtm),(mx1,41+mt1,41)}⌉𝒳1,51 mx1,61=⌈max{(mx1,74+Δtm),(mx1,51+mt1,51)}⌉𝒳1,61 mx1,71=⌈max{(mx3,81+Δtm),(mx1,61+mt1,61)}⌉𝒳1,71 mx1,81=⌈max{(mx1,94+Δtm),(mx1,71+mt1,71)}⌉𝒳1,81 mx1,91=⌈max{(mx1,94+mt1,94+Δtm),(mx1,81+mt1,81)}⌉𝒳1,91
m
x
2,1
1
=
⌈
max
{
(
m
x
2,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
2,9
1
+
m
t
2,9
1
-
m
α
)
}
⌉
𝒳
2,1
1 mx2,21=⌈max{(mx2,34+Δtm-mα),(mx2,11+mt2,11)}⌉𝒳2,11 mx2,31=⌈max{(mx1,64+Δtm),(mx2,21+mt2,21)}⌉𝒳2,31 mx2,41=⌈max{(mx2,54+Δtm-mα),(mx2,31+mt2,31)}⌉𝒳2,41 mx2,51=⌈max{(mx3,41+Δtm),(mx2,41+mt2,41)}⌉𝒳2,51 mx2,61=⌈max{(mx3,51+Δtm),(mx2,51+mt2,51)}⌉𝒳2,61 mx2,71=⌈max{(mx3,61+Δtm),(mx2,61+mt2,61)}⌉𝒳2,71 mx2,81=⌈max{(mx2,94+Δtm),(mx2,71+mt2,71)}⌉𝒳2,81 mx2,91=⌈max{(mx2,94+mt2,94+Δtm),(mx2,81+mt2,81)}⌉𝒳2,91
m
x
3,1
1
=
⌈
max
{
(
m
x
3,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
3,11
1
+
m
t
3,11
1
-
m
α
)
}
⌉
𝒳
3,1
1 mx3,21=⌈max{(mx3,34+Δtm-mα),(mx3,11+mt3,11)}⌉𝒳3,11 mx3,31=⌈max{(mx2,64+Δtm),(mx3,21+mt3,21)}⌉𝒳3,31 mx3,41=⌈max{(mx2,74+Δtm-mα),(mx3,31+mt3,31)}⌉𝒳3,41 mx3,51=⌈max{(mx2,84+Δtm),(mx3,41+mt3,41)}⌉𝒳3,51 mx3,61=⌈max{(mx3,74+Δtm),(mx3,51+mt3,51)}⌉𝒳3,61 mx3,71=⌈max{(mx1,84+Δtm),(mx3,61+mt3,61)}⌉𝒳3,71 mx3,81=⌈max{(mx3,94+Δtm),(mx3,71+mt3,71)}⌉𝒳3,81 mx3,91=⌈max{(mx3,104+Δtm),(mx3,81+mt3,81)}⌉𝒳3,91 mx3,101=⌈max{(mx3,114+Δtm),(mx3,91+mt3,91)}⌉𝒳3,101 mx3,111=⌈max{(mx1,114+mt1,114+Δtm),(mx3,101+mt3,101)}⌉𝒳3,111
m
x
1,1
1
∈
𝒳
1,1
1
=
{
x
1,2
1
(
l
)
∣
x
1,2
1
(
l
)
=
x
1,2
1
+
l
·
α
,
l
∈
ℤ
} mx1,21∈𝒳1,21={x1,31(l)∣x1,31(l)=x1,31+l·α,l∈ℤ} mx1,31∈𝒳1,31={x1,41(l)∣x1,41(l)=x1,41+l·α,l∈ℤ} mx1,41∈𝒳1,41={x2,71(l)∣x2,71(l)=x2,71+l·α,l∈ℤ} mx1,51∈𝒳1,51={x2,81(l)∣x2,81(l)=x2,81+l·α,l∈ℤ} mx1,61∈𝒳1,61={x2,53(l)∣x2,53(l)=x2,53+l·α,l∈ℤ} mx1,71∈𝒳1,71={x2,63(l)∣x2,63(l)=x2,63+l·α,l∈ℤ} mx1,81∈𝒳1,81={x4,72(l)∣x4,72(l)=x4,72+l·α,l∈ℤ} mx1,91∈𝒳1,91={x4,82(l)∣x4,82(l)=x4,82+l·α,l∈ℤ}
m
x
2,1
1
∈
𝒳
2,1
1
=
{
x
5,1
1
(
l
)
∣
x
5,1
1
(
l
)
=
x
5,1
1
+
l
·
α
,
l
∈
ℤ
} mx2,21∈𝒳2,21={x5,21(l)∣x5,21(l)=x5,21+l·α,l∈ℤ} mx2,31∈𝒳2,31={x5,31(l)∣x5,31(l)=x5,31+l·α,l∈ℤ} mx2,41∈𝒳2,41={x5,72(l)∣x5,72(l)=x5,72+l·α,l∈ℤ} mx2,51∈𝒳2,51={x5,82(l)∣x5,82(l)=x5,82+l·α,l∈ℤ} mx2,61∈𝒳2,61={x6,31(l)∣x6,31(l)=x6,31+l·α,l∈ℤ} mx2,71∈𝒳2,71={x6,41(l)∣x6,31(l)=x6,41+l·α,l∈ℤ} mx2,81∈𝒳2,81={x7,31(l)∣x7,31(l)=x7,31+l·α,l∈ℤ} mx2,91∈𝒳2,91={x7,41(l)∣x7,41(l)=x7,41+l·α,l∈ℤ}
m
x
3,1
1
∈
𝒳
3,1
1
=
{
x
8,1
1
(
l
)
∣
x
8,1
1
(
l
)
=
x
8,1
1
+
l
·
α
,
l
∈
ℤ
} mx3,21∈𝒳3,21={x8,21(l)∣x8,21(l)=x8,21+l·α,l∈ℤ} mx3,31∈𝒳3,31={x8,31(l)∣x8,31(l)=x8,31+l·α,l∈ℤ} mx3,41∈𝒳3,41={x6,42(l)∣x6,22(l)=x6,42+l·α,l∈ℤ} mx3,51∈𝒳3,51={x6,42(l)∣x6,22(l)=x6,42+l·α,l∈ℤ} mx3,61∈𝒳3,61={x4,31(l)∣x4,31(l)=x4,31+l·α,l∈ℤ} mx3,71∈𝒳3,71={x4,41(l)∣x4,31(l)=x4,41+l·α,l∈ℤ} mx3,81∈𝒳3,81={x2,52(l)∣x2,52(l)=x2,52+l·α,l∈ℤ} mx3,91∈𝒳3,91={x2,62(l)∣x2,62(l)=x2,62+l·α,l∈ℤ} mx3,101∈𝒳3,101={x3,31(l)∣x3,31(l)=x3,31+l·α,l∈ℤ} mx3,111∈𝒳3,111={x3,41(l)∣x3,41(l)=x3,41+l·α,l∈ℤ}
Constraints of the rest of streamsmP12, mP13, mP14, mP22, mP23, mP24, mP32, mP33, and mP34 are defined in the same way.


### 2.2. Cyclic Steady State Space

According to the previous section, a set of cyclic process achieved in the structureSClp (6) can be represented as a cyclic schedule Xlp (7) that meets the constraints (8) and (9). Figure 4 presents an example of a cyclic schedule which can be achieved in the system illustrated in Figure 1. It shows that for a set of production plan (represented by multimodal processes mP1, mP2, and mP3) it is possible to organize the work of AGVs responsible for transportation of elements between workstations (local processes P1–P8) in such a way that no deadlocks appear in the system or there is no process waiting at the resources. An assumption was made that the transportation of work-pieces (streams of multimodal processes) takes one unit of time and their loading to/unloading from AGVs (local processes) takes place in the first and the last unit of each operation (see Figure 4).Figure 4
AGVs fleet cyclic schedule matching the multiproduct manufacturing.The work [20] shows that schedules of this kind (ensuring such an organization of AGVs that guarantees the accomplishment of the set of production routes without any stoppages) can be obtained by means of solving the following constraint satisfaction problem (10):
(10)CSXT=(({Xlp,Tlp},{DX,DT}),{CL,CM}),
where one has the following: Xlp, Tlp—decision variables, Xlp—cyclic schedule (7), Tlp—sequence of operation times Tlp=(((T,mT1),…,mTq),…,mTlp), DX, DT, Dα=ℕ—domains determining admissible value of decision variables DX:mqxi,jk, xi,jk∈ℤ,mqα, α∈ℕ; DT:mqti,jk, ti,jk∈ℕ, {CL,CM}—the set of constraints CL and CM describing SCCP behavior, CL—constraints determining cyclic steady state of local processes, that is, their cyclic schedule, and CM—constraints determining multimodal processes behavior.The sequence of operations timesTlp and the sequence of their beginning moments Xlp both of them follow constraints CL, CM which are the sufficient conditions for the SCCP cyclic steady state behavior, that is, the state following the problem (10) solution. In case of two level systems, that is, SL and SM (see Figure 3), the constraints CL, CM can be specified in terms of constraints (8) and their extension (9) [15].Presenting cyclic processes asXlp schedules is commonly used both in SCCP [11, 12, 14, 15] and in various problems of cyclic scheduling. Instead of cyclic schedules, the so-called behavior digraphs [16], that create the state space 𝒫, can also be applied.The digraphGW (denoted by W index, in case of cyclic processes representation) is a digraph whose vertexes represent the admissible states Sr of the system and arcs represent transitions between the states (while depicting a given transition function δ [16]).In the considered case, the state of SCCP describes the present (valid in a givent period) allocation on the resources of local (AGVs) and multimodal (technological routes) processes and describes the current access rights to the resources (determined by dispatching priority rules Θ). Formally, in the state definition, three elements are distinguished that characterize processes at the particular behavior levels (see Figure 3).In this approach, the state of SCCP takes the following form:(11)Sr=((((Slr,m1Sr),…,mlSr),…),mlpSr),
where one has the following: (i) lp—the number of levels of structure SClp (6) and (ii) Slr—the rth state of local processes executed on the SL level (5) as follows:
(12)Slr=(Ar,Zr,Qr),
where one has the following: Ar=(a1r,a2r,…,acr,…,amr)—allocation of processes in the rth state, acr∈P∪{Δ}, acr=Pik—the cth resource Rc is occupied by the local stream Pik, and acr=Δ—the cth resource Rc is unoccupied.Z
r
=
(
z
1
r
,
z
2
r
,
…
,
z
c
r
,
…
z
m
r
) is the sequence of semaphores corresponding to the rth state and zcr∈P is name of the stream (specified in the cth dispatching rule σc, allocated to the cth resource) which was allowed to occupy the cth resource; for example, zcr=Pik means that stream Pik is currently allowed to occupy the cth resource.Q
r
=
(
q
1
r
,
q
2
r
,
…
,
q
c
r
,
…
,
q
m
r
) is the sequence of semaphore indices, corresponding to the rth state and qcr determines the position of the semaphore zcr in the priority dispatching rule σc, zcr=sc,(qcr), qcr∈ℕ. For instance, q2r=2 and z2r=P12 correspond to the semaphore z2r=P12 taking the 2nd position in the priority dispatching rule σ2.(iii)
mlSr is the rth state of multimodal processes executed on the SMl level (6) as follows,
(13)mlSr=(mlAr,mlZr,mlQr),where one has the following:mlAr=(mlA1r,1,…,mlAir,h,…,mlAlw(l)r,lsm(lw(l),l))—allocation of the process streams mlPih; that is,
(14)mlAir,h=(mlai,1r,h,mlai,2r,h,…,mlai,cr,h,…,mlai,mr,h),where one has the following:mlPih—the hth stream of the ith multimodal process from l-level of SClp (6), m—the number of resources R, mlai,cr,h∈{mlPih,Δ}, mlai,cr,h=mlPih means that the cth resource Rc is occupied by the hth stream of multimodal process mlPi, and mlai,cr,h=Δ—the cth resource Rc which is released by the hth stream of multimodal process mlPi.m
l
Z
r
=
(
m
l
z
1
r
,
…
,
m
l
z
c
r
,
…
,
m
l
z
m
r
) and mlQr=(mlq1r,…,mlqkr,…,mlqmr) are the sequences of semaphores and indices defined similarly as Zr and Qr.In the context of the introduced notions (allocation, semaphore, indexes) theXlp schedule presented in Figure 4 illustrates only the allocation of processes in time. The particular allocations are denoted by a frame and symbol “◯” of the state Sr connected with the given allocation. Therefore, the cyclic process represented by Xlp schedule can be described with use of 42 states (S0–S41).The digraphGW=(VW,EW) corresponding to Xlp schedule from Figure 4 was illustrated in Figure 5. The set of vertexes VW={S0,…,S41} includes all the states that can be achieved by the system in the course of implementing processes according to Xlp schedule. The set of arcs EW⊆VW×VW defines the transitions between the states. Transition of the system from the state S0 to the state S1 (denoted by S0→S1, and in Figure 5 as ◯→◯) occurs according to the transition function δ, which was described in [16].Figure 5
The digraphGW following Gantt’s chart from Figure 4.According to this approach, the digraphGW=(VW,EW) depicting the behavior from Figure 4 is a cycle including 42 vertexes; see Figure 5. Apart from Sr states, Figure 5 illustrates also local states Slr (12) which only represent the behavior of local processes. In the discussed case, the number of local states is the same as the number of Sr states. Generally, it does not have to be so, as there are situations when one local state is an element of numerous Sr states [14, 15]. The local states Slr as well as the digraph related to them should be perceived as a projection of Sr states and GW digraph onto the level of local processes.It should be noted that in the discussed example only one cyclic steady state is reachable, that is, as a result of the solution (10); that is, one schedule Xlp was obtained along with one digraph GW corresponding to it. Generally, in the given structure SClp a lot of cyclic steady states can be reachable (which depends on the initial phases of dispatching rules) and therefore, we can consider the cyclic steady state space 𝒫 as a set of digraphs that can be reachable in a given structure of GW digraphs.The cyclic steady state space can be illustrated as a graph being the sum of all reachable digraphs:𝒫=(V𝒫,E𝒫)=GW,1∪GW,2∪⋯∪GW,lg (where GW,a∪GW,b=(Va∪Vb,Ea∪Eb)) are reachable in a given structure. There are also situations where in a given structure no cyclic steady states are reachable; then 𝒫=(∅,∅). The main reason for the lack of cyclic behaviors is the possible deadlocks.The form of the space of states𝒫 is strictly dependent upon the form of SClp structure. In other words, the structure determines behaviors reachable in the system. Another example of a cyclic behavior is shown in Figure 6. It is a cyclic schedule Xlp reachable in SC structure (Figure 2) in which the manner of implementing production routes was changed (routes mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R25,R8,R22,R11)) and mp3k=((R1,R27,R4),(R28,R7),(R29,R10)). There are still seven types of AGVs used for transport (local processes P1–P7) with routes remaining unchanged yet different than previously, when they performed their operations.Figure 6
AGVs fleet cyclic schedule matching the multiproduct manufacturing for system with changed multimodal routes.This situation can be interpreted as introducing a new production order into the system, which requires a new method of processing elements. The presence of cyclic scheduleXlp (providing a solution to the problem (10)) and GW digraph (Figure 7) related to it mean that such an order can be implemented.The state space for structures with different multimodal processes routes.
(a)
(b)The presence of two different cyclic steady states leads to the question of their mutual reachability: Is it possible to smoothly change the system behavior fromGW,1 to GW,2 (Figure 7)? In other words, is it possible to smoothly (with no need to stop the system) proceed from implementing the first production order GW,1 to the other GW,2?


## 2.1. Model of AGVS

Automated Guided Vehicle Systems are used for material handling within a Flexible Manufacturing System (FMS) and provide asynchronous movement pallets of products through a network of guide paths between the workstations by the AGVs. Each workstation is connected to the guide path network by a pick-up/delivery station where pallets are transferred from/to the AGVs.In AGVS literature, most are related to AGVS design issues, which include determination of the number of vehicles required, flow path design, and route planning as well as vehicle dispatching and traffic management. Recently, an integrated problem of dispatching and conflict free routing of AGVs, that is, integrating the simultaneous assignment, scheduling, and conflict free routing of the vehicles, is receiving increasing attention. The above mentioned problems, in the general case, belong to the class of NP-hard problems. Since most processes observed in steady state manufacturing are periodic, cyclic schedules and following them, cyclic scheduling methods can be considered. Since cyclic schedules encompass repetitive character of manufacturing processes, the cyclic processes modeling approach seems to be a reasonable perspective [13–15].To present some of the design and operational issues that arise in repetitive manufacturing systems served by AGVs in network of loops layout with unidirectional material flow, a case example of a simple FMS is shown in Figure1. The concurrent multiproduct flows are depicted by bold green, blue, and orange color lines, while the transportation loop-like networks are distinguished by double solid line. Both kinds of material (jobs) and transportation (AGVs) flows shown in Figure 1 can be modeled in terms of Systems of Concurrently Flowing Cyclic Processes [14, 15] as shown in Figure 2. In turn, the SCCP framework provides a formal model enabling to state and resolve problems of AGV fleet size minimization as well as steady state cycle time minimization. The cycle time minimization is required to obtain maximum throughput rate.Figure 1
Example of an AGVS.Figure 2
Example of FMS-SCCP model of an AGVS.Eightlocal cyclic processes are considered, namely, P1, P2, P3, P4, P5, P6, P7, and P8. The processes follow the routes are composed of transportation sectors and machines (distinguished in Figure 2 by the set of resourcesR={R1,…,Rc,…,R33}, Rc—the cth resource). Some of the local cyclic processes are pipeline flow processes; that is, they contain streams (representing vehicles from Figure 1) of the processes following the same route while occupying different resources (sectors). For instance, processes P4, P5, and P6 contain two streams: P4={P41,P42}, P5={P51,P52}, and P6={P61,P62}, respectively, and P2 contains three streams: P2={P21,P22,P23}, that is, the processes (vehicles) moving along the same route. The remaining local processes contain unique streams: P1={P11}, P3={P31}, P7={P71}, and P8={P81}. In other words, the streams P11, P21, P22, P23, P31, P41, P42, P51, P52, P61, P62, P71, and P81 represent the 13 vehicles from Figure 1. The kth stream of the ith local process Pi is denoted by Pik.Apart from local processes, we consider threemultimodal processes (i.e., processes executed along the routes consisting of parts of the routes of local processes): mP1, mP2, and mP3.For example, the production route depicted by the orange line corresponds to the multimodal processmP1 supported by AGVs (arbitrarily given), which in turn encompass local transportation streams P11, P21, P23, and P42. This means that the production route specifying how a multimodal process is executed can be considered to be composed of parts of the routes of local cyclic processes.In the system considered each multimodal process consists of four streams:mPi={mPi1,mPi2,mPi3,mPi4}, i=1,2,3, which means that along each production route four work- pieces are processed serially (four balls on the one production lines in Figure 1).Processes can interact with each other through shared resources, that is, the transportation sectors. The routes of the considered local processes (streams) are as follows (see Figure2):
(1)p11=(R16,R3,R13,R6),p21=(R21,R8,R18,R9,R14,R6,R17,R5),p22=(R17,R5,R21,R8,R18,R9,R14,R6),p23=(R14,R6,R17,R5,R21,R8,R18,R9),p31=(R12,R19,R9,R5),p41=(R29,R7,R25,R8,R22,R11,R26,R10),p42=(R26,R10,R29,R7,R25,R8,R22,R11),p51=(R2,R20,R5,R24,R4,R27,R1,R23),p52=(R27,R1,R23,R2,R20,R5,R24,R4),p61=(R32,R4,R28,R7,R31),p62=(R31,R32,R4,R28,R7),p71=(R33,R7,R29,R10),p81=(R1,R27,R4,R30),
where R1-R2, R4-R11, R14, R17-R18, R20-R29, R31, and R32 (due to two streams of process P6, resources R31, R32 represent one sector) are resources shared by local processes, that is, by at least two streams, and R3, R12, R13, R15, R16, R19, R30, and R33 are the nonshared resources, that is, exclusively used by one stream only.In the general case, the routepik is the sequence of resources used in order to execute the operations of the stream Pik. Note that the streams P21, P22, and P23 which belong to P2 and the streams of processes P4, P5, and P6 follow the same route but start from different resources (these streams correspond to vehicles moving along the same route).Similarly the cyclic multimodal processesmP1, mP2, and mP3 follow the routes (see Figure 2) as follows:
(2)mp1k=(R3,R13,R6,R17,R5,R21,R8,R22,R11),11111111111111111111111111k=1,…,4,mp2k=(R2,R20,R5,R24,R4,R28,R7,R29,R10),11111111111111111111111111k=1,…,4,mp3k=(R1,R27,R4,R28,R7,R25,R8,R18,R9,R15,R12),111111111111111111111111111111111k=1,…,4.
Let us assume that mp1k, mp2k, and mp3k can be seen as follows (see Figure 2):
(3)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)),pppppppppppppppppppppplpk=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R29,R10)),ppppppppppppppppppppppplk=1,…,4,mp3k=((R1,R27,R4),(R28,R7),(R25,R8),(R18,R9),(R15,R12)),k=1,…,4,
where one has the following: (R3,R13,R6), (R17,R5), (R21,R8), and (R22,R11)—subsequences of routes p11, p21, p23, and p42 defining the transportation sections of mp1k; (R2,R20,R5), (R24,R4), (R28,R7), and (R29,R10)—subsequences of routes p51, p52, p61, and p71 defining the transportation sections of mp2k; and (R1,R27,R4), (R28,R7), (R25,R8), (R18,R9), and (R15,R12)—subsequences of routes p81, p62, p41, p22, and p31 defining the transportation sections of mp3k.Let us assume also that the considered SCCPs follow the constraints stated below [15]:(i)
a new subsequent operation of the local process may start on a required resource only if the current operation has been completed and the resource has been released;(ii)
each new consecutive operation in the multimodal process may start its execution on an assigned resource only if the current operation has been completed and the resource has been released and an appropriate local process begins its consecutive operation on this resource;(iii)
local/multimodal processes share common resources in the mutual exclusion mode, the operation of a local/multimodal process can only be suspended if the necessary resource is occupied, suspended processes cannot be released, and processes are nonperceptible; that is, a resource may not be taken from a process as long as it is used by it;(iv)
the SCCP resources can be shared by local and multimodal processes as well as by both of them;(v)
multimodal processes encompassing production flow conveyed by AGVs follow local transportation routes;(vi)
different multimodal processes can be executed simultaneously along the same local process;(vii)
local and multimodal processes execute cyclically with periodsα and mα, respectively; resources occur uniquely in each transportation route;(viii)
in a cyclic steady state, eachith stream must cover its local route the same number of times.A resource conflict (caused by the application of the mutual exclusion protocol) is resolved with the aid of a priority dispatching rule [14–16], which determines the order in which streams access shared resources. For instance, in the case of the resource R5, the priority dispatching rule σ50=(P22,P23,P51,P52,P21) determines the order in which streams of local processes can access the shared resource R5; in the case considered the stream P22 is allowed to access as first, then the stream P23 as next, then streams P51, P52, and P21, and then once again P22, and so on. The stream Pik occurs the same number of times (in the considered system once) in each dispatching rule associated with the resources featuring in its route (in the case considered each stream Pik occurs uniquely). The SCCP shown in Figure 2 is specified by the following set of dispatching rules: Θ={Θ0,Θ1}, where Θ0={σ10,…,σ330} is set of rules determining the orders of local processes and Θ1={σ11,…,σ331} is set of rules determining the orders of multimodal processes.In general, the following notation is used.(i)
A sequencepik=(pi,1k,pi,2k,…,pi,jk,…,pi,lr(i)k) specifies the route of the stream of a local processPik (the kth stream of the ith local process Pi). Its components define the resources used in the execution of operations, where pi,jk∈R (the set of resources R={R1,R2,…,Rc,…,Rm}) denotes the resources used by the kth stream of the ith local process in the jth operation; in the rest of the paper, thejth operation executed on the resourcepi,jkin the streamPik will be denoted by oi,jk; lr(i) is the length of the cyclic process route (all streams of Pi are of the same length). For example, the route p11=(R16,R3,R13,R6) of the stream of process P1 (Figure 2) is the sequence p11=(p1,11,p1,21,p1,31,p1,41), where the first element p1,11 is equal to R16, whereas the second, p1,21=R3, and so on, p1,31=R13, p1,41=R6.(ii)
xi,jk(l)∈ℕ is the timing of commencement of operation oi,jk in the lth cycle.(iii)
tik=(ti,1k,ti,2k,…,ti,jk,…,ti,lr(i)k) specifies the operation times of local processes, where ti,jk denotes the time of execution of operation oi,jk.(iv)
mpik=(mpri1q1(ai1,bi1),mpri2q2(ai2,bi2),…,mpriyqy(aiy,biy)) specifies the route of the streammPikfrom the multimodal processmPi (the kth stream of the ith multimodal process mPi), where
(4)mpriq(a,b)={(pi,aq,pi,a+1q,…,pi,bq),a≤b,(pi,aq,pi,a+1q,…,pi,lr(i)q,pi,1q,…,pi,b-1q,pi,bq)a>b,ppppppppppppppppppppppppa,b∈{1,…,lr(i)},is the subsequence of the routepiq=(pi,1q,pi,2q,…,pi,jq,…,pi,lr(i)q) containing elements from pi,aq to pi,bq.In other words, the transportation routempi is a sequence of parts of routes of local processes. For instance, the route followed by process mP1 (see Figure 2) is as follows: mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)), where mpr11(2,4)=(R3,R13,R6); mpr21(7,8)=(R17,R5); mpr23(1,2)=(R21,R8), mpr42(5,6)=(R22,R11).(v)
mxi,jk(l)∈ℕ is the timing of commencement of operation moi,jk in the lth cycle.(vi)
mtik=(mti,1k,mti,2k,…,mti,jk,…,mti,lm(i)k) specifies the operation times of multimodal processes, where mti,jk denotes the time of execution of operation moi,jk and lm(i) is the length of the cyclic process route mpik.(vii)
Θ={Θ0,Θ1} is the set of priority dispatching rules, Θi={σ1i,σ2i,…,σci,…,σmi} is the set of priority dispatching rules for local (i=0)/multimodal (i=1) processes where σci=(sc,1i,…,sc,di,…,sc,lp(c)i) are sequence components which determine the order in which the processes can be executed on the resource Rc, sc,d0∈H (where H is the set of local streams, e.g., in the case presented in Figure 2, H={P11,P21,P22,P23,P31,P41,P42,P51,P52,P61,P62,P71}), and sc,d1∈mH (where mH is the set of multimodal streams, e.g., in case from Figure 2, mH={mP1k,mP2k,mP3k∣k=1⋯4}).Using the above notation, a SCCP can be defined as a tuple:
(5)SC=((R,SL),SM),
where one has the following: R={R1,R2,…,Rc,…,Rm}—the set of resources, m—the number of resources, SL=(U,T,Θ0)—the structure of local processes, that is, U={p11,…,p1ls(1),…,pn1,…,pnls(n)}—the set of routes of local process, ls(i)—the number of streams belonging to the process Pi, n—the number of local processes, T={t11,…,t1ls(1),…,tn1,…,tnls(n)}—the set of sequences of operation times in local processes, Θ0={σ10,σ20,…,σc0,…,σm0}—the set of priority dispatching rules for local processes, SM=(M,mT,Θ1)—the structure of multimodal processes, that is, M={mp11,…,mp1lsm(1),…,mpw1,…,mpwlsm(n)}—the set of routes of a multimodal process, lsm(i)—the number of streams belonging to the process mPiw—the number of multimodal processes, mT={mt11,…,mtwlsm(1),…,mtn1,…,mtwlsm(n)}—the set of sequences of operation times in multimodal processes, and Θ1={σ11,σ21,…,σc1,…,σm1}—the set of priority dispatching rules for multimodal processes.The SCCP model (5) can be seen as a multilevel model, cf. Figure 3, that is, a model composed of an “R level” (resources), an “SL level” (local cyclic processes), and an “SM1 level” (multimodal cyclic processes), as well as an “SMq level” (the qth metamultimodal process). The SL level is defined by the transportation routes structure following the set U of local processes and the set of parameters Θ determining the required system behavior. In turn, the SM1 level takes into account multimodal processes, as well as metamultimodal processes (SM2 level) composed of multimodal processes from the SM1 level. In other words, it is assumed that the variables describing SMq are the same as in the case of SM, whereas the routes of the multimodal process of the qth level remain composed of the processes from the (q-1)th level. The presented model is an extended version of a simplified model limited to R and SL levels, which is introduced in [15].Figure 3
Multilayered model of the SCCP from Figure2.Therefore, in general, theSC=((R,SL),SM) model can be seen as composed of lp levels as follows:
(6)SClp=(((((R,SL),SM1),SM2),…,SMq),…,SMlp).
The SClp model emphasizes structural characteristics of the SCCP modeled. In turn, the behavioral characteristics can be specified in terms of the admissible states reachability concept, that is, either taking into account the state space concept including both cyclic steady states and leading to them transient states [16] or the cyclic steady state space only [14, 15].The second way, which does not take into account initial states leading through the transient states to the cyclic steady states, seems to be quite close to the cyclic scheduling methods widely used in many real-life cases [9, 11].In that context the relevant multilevel cyclic scheduleXlp encompassing the SCCP behavior on each of its processes level, that is, local SL and multimodal SMlp processes, can be defined as follows:
(7)Xlp=(((((X,α),(m1X,m1α)),…,),…,(mqX,mqα)),…,(mlpX,mlpα)),
where one has the following: X,α/(mqX,mqα)—sequence of commencement of operations and periodicity of local/multimodal (ith level) processes executions.It should also be noted that the scheduleXlp can be defined as a sequence of ordered pairs describing behaviors of local (X,α) and multimodal (miX,miα) processes, where X is a sequence of timings xi,jk (for l=0th cycle) of commencement of operations oi,jk from streams Pik executed along local processes X=(x1,11,x1,21,…,xn,lr(n)ls(n)), and by analogy, the sequence mqX=(mqx1,11,mqx1,21,…,mqxw(q),lm(w,q)lsm(w,q)) consists of the timing of commencement of multimodal processes operations (from the qth level, where one has the following: w(q)—the number of multimodal processes at the qth level, lsm(i,q)—the number of streams of the ith process at the qth level, and lm(i,q)—the number of operation of the ith process at the qth level).Variablesxi,jk/mqxi,jk∈ℤ describe the timing of commencement of operations in the qth cycle of the SCCP cyclic steady state behavior: xi,jk(l)=xi,jk+l·α/mqxi,jk(l)=mqxi,jk+l·mqα.Since values ofxi,jk/mqxi,jk follow from system structure, hence the cyclic behavior Xlp of SCCP is determined by its structure SMlp. Moreover, the multimodal processes behavior (miX,miα) also depends on the local cyclic processes behavior (X,α).In the general case, besides depending on the structural characteristics of SCCP the values of the considered variablesxi,jk/mqxi,jk depend on constraints from the mutual exclusion protocol, that is, the set of priority dispatching rules Θ, operation times, and so forth [14, 15] as well as on the way the local and multimodal processes interacting with each other. For example, in case of the two levels structure model, that is, including levels SL and SM as shown in Figure 2, the constraints determining xi,jk/mqxi,jk can be expressed by the following rules [15]:(i)
for local processes: the timing of commencement of operation oi,jk beginning states for a maximum of the completion time of operation oi,j-1k preceding oi,jk and the release time (with delay Δt) of the resource pi,jk awaiting for oi,j execution is as follows:
(8)momentofoperationoi,jkbeginning=max{(momentofpi,jkrelease+lagtimeΔt),pppppppp(momentofoperationoi,j-1kcompletion)}i=1,…,n;j=1,…,lr(i);k=1,…,ls(i);(ii)
for multimodal processes: the timing of commencement of operation moi,jk beginning is equal to the nearest admissible value (determined by set 𝒳i,jk of values mxi,jk) being a maximum of both the completion time of operation moi,j-1k preceding moi,j and the release time (lag time Δtm) of the resource mpi,jk awaiting for moi,j execution. Consider
(9)momentofoperationmoi,jkbeginning=⌈max{(momentofmpi,jkrelease+lagtimeΔtm),momentofoperationmoi,j-1kcompletion}⌉𝒳i,jki=1,…,n;j=1,…,lm(i);k=1,…,lsm(i),
where one has the following: 𝒳i,jk—set of values mxi,jk following the set of local processes X, (𝒳i,jk—the set of moments when operation moi,jk of multimodal process may use required local process) and ⌈a⌉B—the smallest integer greater than or equal to a in terms of the set B: ⌈a⌉B=min{k∈B:k≥a}.In other words, the timing of commencement of operationmoi,j belongs to the set 𝒳i,jk and being coincident with operation processes by relevant local transportation process Pi.The constraints determining (due to introduced rules (8) and (9)) the timing of commencement of operations for the SCCP from Figure 2 are gathered in Tables 1 and 2.Table 1
Constraints determining the local processes behavior of the SCCP from Figure2.
Constraints of the local processes
x
1,1
1
=
x
1,4
1
+
t
1,4
1
-
α
x
4,1
2
=
max
{
(
x
4,8
1
+
Δ
t
-
α
)
,
(
x
4,8
2
+
t
4,8
2
-
α
)
}
—
x
1,2
1
=
x
1,1
1
+
t
1,1
1
x
4,2
2
=
max
{
(
x
4,1
1
+
Δ
t
)
,
(
x
4,1
2
+
t
4,1
2
)
}
x
5,1
2
=
max
{
(
x
5,7
1
+
Δ
t
-
α
)
,
(
x
5,8
2
+
t
5,8
2
-
α
)
}
x
1,3
1
=
x
1,2
1
+
t
1,2
1
x
4,3
2
=
max
{
(
x
4,2
1
+
Δ
t
)
,
(
x
4,2
2
+
t
4,2
2
)
}
x
5,2
2
=
max
{
(
x
5,8
1
+
Δ
t
-
α
)
,
(
x
5,1
2
+
t
5,1
2
)
}
x
1,4
1
=
max
{
(
x
2,7
1
+
Δ
t
)
,
(
x
1,3
1
+
t
1,3
1
)
}
x
4,4
2
=
max
{
(
x
4,3
1
+
Δ
t
)
,
(
x
4,3
2
+
t
4,3
2
)
}
x
5,3
2
=
max
{
(
x
5,1
1
+
Δ
t
)
,
(
x
5,2
2
+
t
5,2
2
)
}
—
x
4,5
2
=
max
{
(
x
4,4
1
+
Δ
t
)
,
(
x
4,4
2
+
t
4,4
2
)
}
x
5,4
2
=
max
{
(
x
5,2
1
+
Δ
t
)
,
(
x
5,3
2
+
t
5,3
2
)
}
x
2,1
1
=
max
{
(
x
2,6
3
+
Δ
t
-
α
)
,
(
x
2,8
1
+
t
2,8
1
-
α
)
}
x
4,6
2
=
max
{
(
x
2,7
3
+
Δ
t
)
,
(
x
4,5
2
+
t
4,5
2
)
}
x
5,5
2
=
max
{
(
x
5,3
1
+
Δ
t
)
,
(
x
5,4
2
+
t
5,4
2
)
}
x
2,2
1
=
max
{
(
x
4,7
2
+
Δ
t
-
α
)
,
(
x
2,1
1
+
t
2,1
1
)
}
x
4,7
2
=
max
{
(
x
4,6
1
+
Δ
t
)
,
(
x
4,6
2
+
t
4,6
2
)
}
x
5,6
2
=
max
{
(
x
5,4
1
+
Δ
t
)
,
(
x
5,5
2
+
t
5,5
2
)
}
x
2,3
1
=
max
{
(
x
2,8
3
+
Δ
t
-
α
)
,
(
x
2,2
1
+
t
2,2
1
)
}
x
4,8
2
=
max
{
(
x
4,7
1
+
Δ
t
)
,
(
x
4,7
2
+
t
4,7
2
)
}
x
5,7
2
=
max
{
(
x
5,5
1
+
Δ
t
)
,
(
x
5,6
2
+
t
5,6
2
)
}
x
2,4
1
=
max
{
(
x
2,1
3
+
Δ
t
)
,
(
x
2,3
1
+
t
2,3
1
)
}
—
x
5,8
2
=
max
{
(
x
5,6
1
+
Δ
t
)
,
(
x
5,7
2
+
t
5,7
2
)
}
x
2,5
1
=
max
{
(
x
2,2
3
+
Δ
t
)
,
(
x
2,4
1
+
t
2,4
1
)
}
x
5,1
1
=
max
{
(
x
5,5
2
+
Δ
t
-
α
)
,
(
x
5,8
1
+
t
5,8
1
-
α
)
}
—
x
2,6
1
=
max
{
(
x
2,3
3
+
Δ
t
)
,
(
x
2,5
1
+
t
2,5
1
)
}
x
5,2
1
=
max
{
(
x
5,6
2
+
Δ
t
-
α
)
,
(
x
5,1
1
+
t
5,1
1
)
}
x
6,1
1
=
max
{
(
x
6,3
2
+
Δ
t
-
α
)
,
(
x
6,5
1
+
t
6,5
1
-
α
)
}
x
2,7
1
=
max
{
(
x
2,4
3
+
Δ
t
)
,
(
x
2,6
1
+
t
2,6
1
)
}
x
5,3
1
=
max
{
(
x
2,5
3
+
Δ
t
)
,
(
x
5,2
1
+
t
5,2
1
)
}
x
6,2
1
=
max
{
(
x
5,1
2
+
Δ
t
)
,
(
x
6,1
1
+
t
6,1
1
)
}
x
2,8
1
=
max
{
(
x
5,7
2
+
Δ
t
)
,
(
x
2,7
1
+
t
2,7
1
)
}
x
5,4
1
=
max
{
(
x
5,8
2
+
Δ
t
-
α
)
,
(
x
5,3
1
+
t
5,3
1
)
}
x
6,3
1
=
max
{
(
x
6,5
2
+
Δ
t
-
α
)
,
(
x
6,2
1
+
t
6,2
1
)
}
—
x
5,5
1
=
max
{
(
x
6,4
2
+
Δ
t
)
,
(
x
5,4
1
+
t
5,4
1
)
}
x
6,4
1
=
max
{
(
x
4,5
2
+
Δ
t
)
,
(
x
6,3
1
+
t
6,3
1
)
}
x
2,1
2
=
max
{
(
x
2,8
1
+
Δ
t
-
α
)
,
(
x
2,8
2
+
t
2,8
2
-
α
)
}
x
5,6
1
=
max
{
(
x
8,3
1
+
Δ
t
)
,
(
x
5,5
1
+
t
5,5
1
)
}
x
6,5
1
=
max
{
(
x
6,2
2
+
Δ
t
)
,
(
x
6,4
1
+
t
6,4
1
)
}
x
2,2
2
=
max
{
(
x
2,1
1
+
Δ
t
)
,
(
x
2,1
2
+
t
2,1
2
)
}
x
5,7
1
=
max
{
(
x
8,2
1
+
Δ
t
)
,
(
x
5,6
1
+
t
5,6
1
)
}
—
x
2,3
2
=
max
{
(
x
2,2
1
+
Δ
t
)
,
(
x
2,2
2
+
t
2,2
2
)
}
x
5,8
1
=
max
{
(
x
5,4
2
+
Δ
t
)
,
(
x
5,7
1
+
t
5,7
1
)
}
x
6,1
2
=
max
{
(
x
6,3
2
+
Δ
t
)
,
(
x
6,5
2
+
t
6,5
2
-
α
)
}
x
2,4
2
=
max
{
(
x
4,5
1
+
Δ
t
)
,
(
x
2,3
2
+
t
2,3
2
)
}
—
x
6,2
2
=
max
{
(
x
6,2
1
+
Δ
t
)
,
(
x
6,1
2
+
t
6,1
2
)
}
x
2,5
2
=
max
{
(
x
2,4
1
+
Δ
t
)
,
(
x
2,4
2
+
t
2,4
2
)
}
x
3,1
1
=
x
3,4
1
+
t
3,4
1
-
α
x
6,3
2
=
max
{
(
x
8,4
1
+
Δ
t
)
,
(
x
6,2
2
+
t
6,2
2
)
}
x
2,6
2
=
max
{
(
x
2,5
1
+
Δ
t
)
,
(
x
2,5
2
+
t
2,5
2
)
}
x
3,2
1
=
x
3,1
1
+
t
3,1
1
x
6,4
2
=
max
{
(
x
6,4
1
+
Δ
t
)
,
(
x
6,3
2
+
t
6,3
2
)
}
x
2,7
2
=
max
{
(
x
2,1
1
+
Δ
t
)
,
(
x
2,6
2
+
t
2,6
2
)
}
x
3,3
1
=
max
{
(
x
2,7
2
+
Δ
t
)
,
(
x
3,2
1
+
t
3,2
1
)
}
x
6,5
2
=
max
{
(
x
7,3
1
+
Δ
t
)
,
(
x
6,4
2
+
t
6,4
2
)
}
x
2,8
2
=
max
{
(
x
1,1
1
+
Δ
t
-
α
)
,
(
x
2,7
2
+
t
2,7
2
)
}
x
3,4
1
=
x
3,3
1
+
t
3,3
1
—
—
—
x
7,1
1
=
x
7,4
1
+
t
7,4
1
-
α
x
2,1
3
=
max
{
(
x
2,8
2
+
Δ
t
-
α
)
,
(
x
2,8
3
+
t
2,8
3
-
α
)
}
x
4,1
1
=
max
{
(
x
7,4
1
+
Δ
t
-
α
)
,
(
x
4,8
1
+
t
4,8
1
-
α
)
}
x
7,2
1
=
max
{
(
x
6,5
1
+
Δ
t
)
,
(
x
7,1
1
+
t
7,1
1
)
}
x
2,2
3
=
max
{
(
x
2,1
2
+
Δ
t
)
,
(
x
2,1
3
+
t
2,1
3
)
}
x
4,2
1
=
max
{
(
x
6,1
2
+
Δ
t
)
,
(
x
4,1
1
+
t
4,1
1
)
}
x
7,3
1
=
max
{
(
x
4,4
2
+
Δ
t
)
,
(
x
7,2
1
+
t
7,2
1
)
}
x
2,3
3
=
max
{
(
x
2,2
2
+
Δ
t
)
,
(
x
2,2
3
+
t
2,2
3
)
}
x
4,3
1
=
max
{
(
x
4,6
2
+
Δ
t
-
α
)
,
(
x
4,2
1
+
t
4,2
1
)
}
x
7,4
1
=
max
{
(
x
4,3
2
+
Δ
t
)
,
(
x
7,3
1
+
t
7,3
1
)
}
x
2,4
3
=
max
{
(
x
2,3
2
+
Δ
t
)
,
(
x
2,3
3
+
t
2,3
3
)
}
x
4,4
1
=
max
{
(
x
2,3
1
+
Δ
t
)
,
(
x
4,3
1
+
t
4,3
1
)
}
—
x
2,5
3
=
max
{
(
x
2,4
2
+
Δ
t
)
,
(
x
2,4
3
+
t
2,4
3
)
}
x
4,5
1
=
max
{
(
x
4,8
2
+
Δ
t
-
α
)
,
(
x
4,4
1
+
t
4,4
1
)
}
x
8,1
1
=
max
{
(
x
5,3
2
+
Δ
t
)
,
(
x
8,4
1
+
t
8,4
1
-
α
)
}
x
2,6
3
=
max
{
(
x
2,5
2
+
Δ
t
)
,
(
x
2,5
3
+
t
2,5
3
)
}
x
4,6
1
=
max
{
(
x
4,1
2
+
Δ
t
)
,
(
x
4,5
1
+
t
4,5
1
)
}
x
8,2
1
=
max
{
(
x
5,2
2
+
Δ
t
)
,
(
x
8,1
1
+
t
8,1
1
)
}
x
2,7
3
=
max
{
(
x
2,6
2
+
Δ
t
)
,
(
x
2,6
3
+
t
2,6
3
)
}
x
4,7
1
=
max
{
(
x
4,2
2
+
Δ
t
)
,
(
x
4,6
1
+
t
4,6
1
)
}
x
8,3
1
=
max
{
(
x
6,3
1
+
Δ
t
)
,
(
x
8,2
1
+
t
8,2
1
)
}
x
2,8
3
=
max
{
(
x
2,7
2
+
Δ
t
)
,
(
x
2,7
3
+
t
2,7
3
)
}
x
4,8
1
=
max
{
(
x
7,1
1
+
Δ
t
-
α
)
,
(
x
4,7
1
+
t
4,7
1
)
}
x
8,4
1
=
x
8,3
1
+
t
8,3
1Table 2
Constraints (9) determining the multimodal processes behavior of the SCCP from Figure 2.
Constraints for streammP11
Constraints for streammP21
Constraints for streammP31
m
x
1,1
1
=
⌈
max
{
(
m
x
1,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
1,9
1
+
m
t
1,9
1
-
m
α
)
}
⌉
𝒳
1,1
1 mx1,21=⌈max{(mx1,34+Δtm-mα),(mx1,11+mt1,11)}⌉𝒳1,11 mx1,31=⌈max{(mx1,44+Δtm-mα),(mx1,21+mt1,21)}⌉𝒳1,31 mx1,41=⌈max{(mx1,54+Δtm-mα),(mx1,31+mt1,31)}⌉𝒳1,41 mx1,51=⌈max{(mx2,41+Δtm),(mx1,41+mt1,41)}⌉𝒳1,51 mx1,61=⌈max{(mx1,74+Δtm),(mx1,51+mt1,51)}⌉𝒳1,61 mx1,71=⌈max{(mx3,81+Δtm),(mx1,61+mt1,61)}⌉𝒳1,71 mx1,81=⌈max{(mx1,94+Δtm),(mx1,71+mt1,71)}⌉𝒳1,81 mx1,91=⌈max{(mx1,94+mt1,94+Δtm),(mx1,81+mt1,81)}⌉𝒳1,91
m
x
2,1
1
=
⌈
max
{
(
m
x
2,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
2,9
1
+
m
t
2,9
1
-
m
α
)
}
⌉
𝒳
2,1
1 mx2,21=⌈max{(mx2,34+Δtm-mα),(mx2,11+mt2,11)}⌉𝒳2,11 mx2,31=⌈max{(mx1,64+Δtm),(mx2,21+mt2,21)}⌉𝒳2,31 mx2,41=⌈max{(mx2,54+Δtm-mα),(mx2,31+mt2,31)}⌉𝒳2,41 mx2,51=⌈max{(mx3,41+Δtm),(mx2,41+mt2,41)}⌉𝒳2,51 mx2,61=⌈max{(mx3,51+Δtm),(mx2,51+mt2,51)}⌉𝒳2,61 mx2,71=⌈max{(mx3,61+Δtm),(mx2,61+mt2,61)}⌉𝒳2,71 mx2,81=⌈max{(mx2,94+Δtm),(mx2,71+mt2,71)}⌉𝒳2,81 mx2,91=⌈max{(mx2,94+mt2,94+Δtm),(mx2,81+mt2,81)}⌉𝒳2,91
m
x
3,1
1
=
⌈
max
{
(
m
x
3,2
4
+
Δ
t
m
-
m
α
)
,
(
m
x
3,11
1
+
m
t
3,11
1
-
m
α
)
}
⌉
𝒳
3,1
1 mx3,21=⌈max{(mx3,34+Δtm-mα),(mx3,11+mt3,11)}⌉𝒳3,11 mx3,31=⌈max{(mx2,64+Δtm),(mx3,21+mt3,21)}⌉𝒳3,31 mx3,41=⌈max{(mx2,74+Δtm-mα),(mx3,31+mt3,31)}⌉𝒳3,41 mx3,51=⌈max{(mx2,84+Δtm),(mx3,41+mt3,41)}⌉𝒳3,51 mx3,61=⌈max{(mx3,74+Δtm),(mx3,51+mt3,51)}⌉𝒳3,61 mx3,71=⌈max{(mx1,84+Δtm),(mx3,61+mt3,61)}⌉𝒳3,71 mx3,81=⌈max{(mx3,94+Δtm),(mx3,71+mt3,71)}⌉𝒳3,81 mx3,91=⌈max{(mx3,104+Δtm),(mx3,81+mt3,81)}⌉𝒳3,91 mx3,101=⌈max{(mx3,114+Δtm),(mx3,91+mt3,91)}⌉𝒳3,101 mx3,111=⌈max{(mx1,114+mt1,114+Δtm),(mx3,101+mt3,101)}⌉𝒳3,111
m
x
1,1
1
∈
𝒳
1,1
1
=
{
x
1,2
1
(
l
)
∣
x
1,2
1
(
l
)
=
x
1,2
1
+
l
·
α
,
l
∈
ℤ
} mx1,21∈𝒳1,21={x1,31(l)∣x1,31(l)=x1,31+l·α,l∈ℤ} mx1,31∈𝒳1,31={x1,41(l)∣x1,41(l)=x1,41+l·α,l∈ℤ} mx1,41∈𝒳1,41={x2,71(l)∣x2,71(l)=x2,71+l·α,l∈ℤ} mx1,51∈𝒳1,51={x2,81(l)∣x2,81(l)=x2,81+l·α,l∈ℤ} mx1,61∈𝒳1,61={x2,53(l)∣x2,53(l)=x2,53+l·α,l∈ℤ} mx1,71∈𝒳1,71={x2,63(l)∣x2,63(l)=x2,63+l·α,l∈ℤ} mx1,81∈𝒳1,81={x4,72(l)∣x4,72(l)=x4,72+l·α,l∈ℤ} mx1,91∈𝒳1,91={x4,82(l)∣x4,82(l)=x4,82+l·α,l∈ℤ}
m
x
2,1
1
∈
𝒳
2,1
1
=
{
x
5,1
1
(
l
)
∣
x
5,1
1
(
l
)
=
x
5,1
1
+
l
·
α
,
l
∈
ℤ
} mx2,21∈𝒳2,21={x5,21(l)∣x5,21(l)=x5,21+l·α,l∈ℤ} mx2,31∈𝒳2,31={x5,31(l)∣x5,31(l)=x5,31+l·α,l∈ℤ} mx2,41∈𝒳2,41={x5,72(l)∣x5,72(l)=x5,72+l·α,l∈ℤ} mx2,51∈𝒳2,51={x5,82(l)∣x5,82(l)=x5,82+l·α,l∈ℤ} mx2,61∈𝒳2,61={x6,31(l)∣x6,31(l)=x6,31+l·α,l∈ℤ} mx2,71∈𝒳2,71={x6,41(l)∣x6,31(l)=x6,41+l·α,l∈ℤ} mx2,81∈𝒳2,81={x7,31(l)∣x7,31(l)=x7,31+l·α,l∈ℤ} mx2,91∈𝒳2,91={x7,41(l)∣x7,41(l)=x7,41+l·α,l∈ℤ}
m
x
3,1
1
∈
𝒳
3,1
1
=
{
x
8,1
1
(
l
)
∣
x
8,1
1
(
l
)
=
x
8,1
1
+
l
·
α
,
l
∈
ℤ
} mx3,21∈𝒳3,21={x8,21(l)∣x8,21(l)=x8,21+l·α,l∈ℤ} mx3,31∈𝒳3,31={x8,31(l)∣x8,31(l)=x8,31+l·α,l∈ℤ} mx3,41∈𝒳3,41={x6,42(l)∣x6,22(l)=x6,42+l·α,l∈ℤ} mx3,51∈𝒳3,51={x6,42(l)∣x6,22(l)=x6,42+l·α,l∈ℤ} mx3,61∈𝒳3,61={x4,31(l)∣x4,31(l)=x4,31+l·α,l∈ℤ} mx3,71∈𝒳3,71={x4,41(l)∣x4,31(l)=x4,41+l·α,l∈ℤ} mx3,81∈𝒳3,81={x2,52(l)∣x2,52(l)=x2,52+l·α,l∈ℤ} mx3,91∈𝒳3,91={x2,62(l)∣x2,62(l)=x2,62+l·α,l∈ℤ} mx3,101∈𝒳3,101={x3,31(l)∣x3,31(l)=x3,31+l·α,l∈ℤ} mx3,111∈𝒳3,111={x3,41(l)∣x3,41(l)=x3,41+l·α,l∈ℤ}
Constraints of the rest of streamsmP12, mP13, mP14, mP22, mP23, mP24, mP32, mP33, and mP34 are defined in the same way.


## 2.2. Cyclic Steady State Space

According to the previous section, a set of cyclic process achieved in the structureSClp (6) can be represented as a cyclic schedule Xlp (7) that meets the constraints (8) and (9). Figure 4 presents an example of a cyclic schedule which can be achieved in the system illustrated in Figure 1. It shows that for a set of production plan (represented by multimodal processes mP1, mP2, and mP3) it is possible to organize the work of AGVs responsible for transportation of elements between workstations (local processes P1–P8) in such a way that no deadlocks appear in the system or there is no process waiting at the resources. An assumption was made that the transportation of work-pieces (streams of multimodal processes) takes one unit of time and their loading to/unloading from AGVs (local processes) takes place in the first and the last unit of each operation (see Figure 4).Figure 4
AGVs fleet cyclic schedule matching the multiproduct manufacturing.The work [20] shows that schedules of this kind (ensuring such an organization of AGVs that guarantees the accomplishment of the set of production routes without any stoppages) can be obtained by means of solving the following constraint satisfaction problem (10):
(10)CSXT=(({Xlp,Tlp},{DX,DT}),{CL,CM}),
where one has the following: Xlp, Tlp—decision variables, Xlp—cyclic schedule (7), Tlp—sequence of operation times Tlp=(((T,mT1),…,mTq),…,mTlp), DX, DT, Dα=ℕ—domains determining admissible value of decision variables DX:mqxi,jk, xi,jk∈ℤ,mqα, α∈ℕ; DT:mqti,jk, ti,jk∈ℕ, {CL,CM}—the set of constraints CL and CM describing SCCP behavior, CL—constraints determining cyclic steady state of local processes, that is, their cyclic schedule, and CM—constraints determining multimodal processes behavior.The sequence of operations timesTlp and the sequence of their beginning moments Xlp both of them follow constraints CL, CM which are the sufficient conditions for the SCCP cyclic steady state behavior, that is, the state following the problem (10) solution. In case of two level systems, that is, SL and SM (see Figure 3), the constraints CL, CM can be specified in terms of constraints (8) and their extension (9) [15].Presenting cyclic processes asXlp schedules is commonly used both in SCCP [11, 12, 14, 15] and in various problems of cyclic scheduling. Instead of cyclic schedules, the so-called behavior digraphs [16], that create the state space 𝒫, can also be applied.The digraphGW (denoted by W index, in case of cyclic processes representation) is a digraph whose vertexes represent the admissible states Sr of the system and arcs represent transitions between the states (while depicting a given transition function δ [16]).In the considered case, the state of SCCP describes the present (valid in a givent period) allocation on the resources of local (AGVs) and multimodal (technological routes) processes and describes the current access rights to the resources (determined by dispatching priority rules Θ). Formally, in the state definition, three elements are distinguished that characterize processes at the particular behavior levels (see Figure 3).In this approach, the state of SCCP takes the following form:(11)Sr=((((Slr,m1Sr),…,mlSr),…),mlpSr),
where one has the following: (i) lp—the number of levels of structure SClp (6) and (ii) Slr—the rth state of local processes executed on the SL level (5) as follows:
(12)Slr=(Ar,Zr,Qr),
where one has the following: Ar=(a1r,a2r,…,acr,…,amr)—allocation of processes in the rth state, acr∈P∪{Δ}, acr=Pik—the cth resource Rc is occupied by the local stream Pik, and acr=Δ—the cth resource Rc is unoccupied.Z
r
=
(
z
1
r
,
z
2
r
,
…
,
z
c
r
,
…
z
m
r
) is the sequence of semaphores corresponding to the rth state and zcr∈P is name of the stream (specified in the cth dispatching rule σc, allocated to the cth resource) which was allowed to occupy the cth resource; for example, zcr=Pik means that stream Pik is currently allowed to occupy the cth resource.Q
r
=
(
q
1
r
,
q
2
r
,
…
,
q
c
r
,
…
,
q
m
r
) is the sequence of semaphore indices, corresponding to the rth state and qcr determines the position of the semaphore zcr in the priority dispatching rule σc, zcr=sc,(qcr), qcr∈ℕ. For instance, q2r=2 and z2r=P12 correspond to the semaphore z2r=P12 taking the 2nd position in the priority dispatching rule σ2.(iii)
mlSr is the rth state of multimodal processes executed on the SMl level (6) as follows,
(13)mlSr=(mlAr,mlZr,mlQr),where one has the following:mlAr=(mlA1r,1,…,mlAir,h,…,mlAlw(l)r,lsm(lw(l),l))—allocation of the process streams mlPih; that is,
(14)mlAir,h=(mlai,1r,h,mlai,2r,h,…,mlai,cr,h,…,mlai,mr,h),where one has the following:mlPih—the hth stream of the ith multimodal process from l-level of SClp (6), m—the number of resources R, mlai,cr,h∈{mlPih,Δ}, mlai,cr,h=mlPih means that the cth resource Rc is occupied by the hth stream of multimodal process mlPi, and mlai,cr,h=Δ—the cth resource Rc which is released by the hth stream of multimodal process mlPi.m
l
Z
r
=
(
m
l
z
1
r
,
…
,
m
l
z
c
r
,
…
,
m
l
z
m
r
) and mlQr=(mlq1r,…,mlqkr,…,mlqmr) are the sequences of semaphores and indices defined similarly as Zr and Qr.In the context of the introduced notions (allocation, semaphore, indexes) theXlp schedule presented in Figure 4 illustrates only the allocation of processes in time. The particular allocations are denoted by a frame and symbol “◯” of the state Sr connected with the given allocation. Therefore, the cyclic process represented by Xlp schedule can be described with use of 42 states (S0–S41).The digraphGW=(VW,EW) corresponding to Xlp schedule from Figure 4 was illustrated in Figure 5. The set of vertexes VW={S0,…,S41} includes all the states that can be achieved by the system in the course of implementing processes according to Xlp schedule. The set of arcs EW⊆VW×VW defines the transitions between the states. Transition of the system from the state S0 to the state S1 (denoted by S0→S1, and in Figure 5 as ◯→◯) occurs according to the transition function δ, which was described in [16].Figure 5
The digraphGW following Gantt’s chart from Figure 4.According to this approach, the digraphGW=(VW,EW) depicting the behavior from Figure 4 is a cycle including 42 vertexes; see Figure 5. Apart from Sr states, Figure 5 illustrates also local states Slr (12) which only represent the behavior of local processes. In the discussed case, the number of local states is the same as the number of Sr states. Generally, it does not have to be so, as there are situations when one local state is an element of numerous Sr states [14, 15]. The local states Slr as well as the digraph related to them should be perceived as a projection of Sr states and GW digraph onto the level of local processes.It should be noted that in the discussed example only one cyclic steady state is reachable, that is, as a result of the solution (10); that is, one schedule Xlp was obtained along with one digraph GW corresponding to it. Generally, in the given structure SClp a lot of cyclic steady states can be reachable (which depends on the initial phases of dispatching rules) and therefore, we can consider the cyclic steady state space 𝒫 as a set of digraphs that can be reachable in a given structure of GW digraphs.The cyclic steady state space can be illustrated as a graph being the sum of all reachable digraphs:𝒫=(V𝒫,E𝒫)=GW,1∪GW,2∪⋯∪GW,lg (where GW,a∪GW,b=(Va∪Vb,Ea∪Eb)) are reachable in a given structure. There are also situations where in a given structure no cyclic steady states are reachable; then 𝒫=(∅,∅). The main reason for the lack of cyclic behaviors is the possible deadlocks.The form of the space of states𝒫 is strictly dependent upon the form of SClp structure. In other words, the structure determines behaviors reachable in the system. Another example of a cyclic behavior is shown in Figure 6. It is a cyclic schedule Xlp reachable in SC structure (Figure 2) in which the manner of implementing production routes was changed (routes mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R25,R8,R22,R11)) and mp3k=((R1,R27,R4),(R28,R7),(R29,R10)). There are still seven types of AGVs used for transport (local processes P1–P7) with routes remaining unchanged yet different than previously, when they performed their operations.Figure 6
AGVs fleet cyclic schedule matching the multiproduct manufacturing for system with changed multimodal routes.This situation can be interpreted as introducing a new production order into the system, which requires a new method of processing elements. The presence of cyclic scheduleXlp (providing a solution to the problem (10)) and GW digraph (Figure 7) related to it mean that such an order can be implemented.The state space for structures with different multimodal processes routes.
(a)
(b)The presence of two different cyclic steady states leads to the question of their mutual reachability: Is it possible to smoothly change the system behavior fromGW,1 to GW,2 (Figure 7)? In other words, is it possible to smoothly (with no need to stop the system) proceed from implementing the first production order GW,1 to the other GW,2?


## 3. Multimodal Processes Rescheduling

### 3.1. Problem Formulation

The question of the possibility of smoothly changing the cyclic behaviors of the system is related to the problem of mutual reachability of the two behavior digraphsGW,1, GW,2. The digraphs presented so far (Figure 7) are cycles. In general, a digraph may take the form of the so-called vortex GS, that is, a digraph including a cycle representing a cyclic steady states GW and a tree GT,i representing transient states leading to cyclic steady states. An example of two vortexes GS,1, GS,2 is shown in Figure 8. Formally, the digraph of the vortex type is defined as follows:
(15)GS=(VS,ES)=GW∪(⋃i=1ltGT,i),
where ⋃i=1ltGT,i=GT,1∪GT,2∪⋯∪GT,lt, lt is the number of trees GT,i leading to GW cycle.Figure 8
Illustration of the cyclic steady state space composed of two vortexes.In this approach, the problem of mutual reachability of the behavior digraphs of mutual space of states is defined as follows: there is a given structureSClp and the cyclic steady state space 𝒫=(V𝒫,E𝒫) resulting from it, which includes two vortexes GS,1, GS,2 that represent two cyclic steady processes. It is therefore necessary to find answer to the following question: Are the digraphs GW,1, GW,2 (being subdigraphs of GS,1, GS,2) mutually reachable (Figure 8)? In the case they are mutually reachable the next question is how to make a transition between the digraphs?In other words, the question of mutual reachability of cyclic behaviors can be treated as the question of the possibility of direct or indirect transition between the digraphsGW,1, GW,2. An example of such transitions is shown in Figure 8. An indirect transition should be understood as changing GW,1 into GW,2, resulting from the transition of the state Sx′ into transitory path (a path of digraph GT,i) leading to GW,2. The direct transition means a transition from the state Sx right into the cycle GW,1.


### 3.2. Searching for States with Mutual Allocation

#### 3.2.1. Sufficient Conditions

The possibility of transitions between cyclic steady states depends on the stateSx(Sx′), which is an element of two digraphs: GS,1 and GS,2. In other words, it is necessary that in case of direct transition the following transitions between states occur:(i)
for allSk∈VW,1 (Sk→⋯→Sx→⋯→Sk) for the digraph GW,1,(ii)
for allSl∈VW,2 (Sl→⋯→Sx→⋯→Sl) for the digraph GW,2.In SCCP, transitions of this kind are not acceptable. It results from the property saying that each state has at least one descendant [16] (a descendant is the consecutive state after Sx). The presence of stateSx included simultaneously into two digraphs (GW,1,GW,2) would require the existence of at least two descendants of the state Sx.Although there are no mutual states at the level of the space of states𝒫, the different projections of states upon lower levels of behavior as well as their components (space of allocation, semaphores, etc.) may be elements belonging to numerous digraphs at the same time.An example of such a situation is shown in Figure9, where the idea of a multilevel model of the cyclic steady states space 𝒫 has been applied. The figure shows the projection of the space 𝒫 upon the level of local processes behavior 𝒫SL (the second level in Figure 9) and upon the space of allocation 𝒜 (the lowest level in Figure 9). The elements of the space 𝒜 are the allocations Ar of the local states Slr=(Ar,Zr,Qr) occurring in the space 𝒫SL=(VSL,ESL) (where Slr∈VSL), which at the same time is the projection of the space of states 𝒫.Figure 9
Illustration of cyclic steady state space projections,𝒫SL and 𝒜, for behavior digraphs from Figure 8.It is worth mentioning that some allocations of the space𝒜 are simultaneously mutual for several states. For example, the allocation A2∈𝒜 is at the same time an element of the state Sl3=(A2,Z3,Q3) and the state Sl4=(A2,Z4,Q4). In practice, it means that in both states the local processes (representing, e.g., means of transport such as AGVs) are allocated on the same resources. However, since there are various access rights (determined by Z3, Q3 and Z4, Q4) their further implantation will be different.The existence of states of common allocation can be used for the transitions between various behavior digraphs. The statesSl3 and Sl4 differ only with the sequence of semaphores and indexes. Thus, if in the state Sl3 with allocation A2, the form of Z3, Q3changes into the form of Z4, Q4, we will attain the state Sl4 leading to another cycle.The modification of the stateSl3 into Sl4 by changing the form of semaphores and indexes allows for an indirect transition between cyclic processes of the space 𝒫0. The direct transition is possible as a result of modifying the semaphores and indexes of the states Sl1=(A1,Z1,Q1) and Sl2=(A1,Z2,Q2) mutually sharing the allocation A1. Therefore, the presence of states of mutual allocation implies the possibility of changing the set of cyclic steady states.The considered transitions betweenSl3 and Sl4 as well as Sl1 and Sl2 refer mainly to digraphs occurring only at the local level (i.e., space 𝒫SL). In case of digraphs GS,1, GS,2 of the space 𝒫 a similar procedure should be followed. These states are the projections of the corresponding states from the space 𝒫. The state Sl1 is the projection of the state S1=(Sl1,m1S1), which is an element of the digraph GW,1, and the state S2=(Sl2,m1S2) is the projection of the digraph GW,2.If, among states projecting uponSl1 and Sl2, there are states (e.g., states Sl1 and Sl2) with mutual allocation m1Ax of the multimodal processes, the transition between GW,1 and GW,2 (and therefore also between GS,1 and GS,2) is possible as a result of modifications of corresponding semaphores and indexes (from the form of m1Z1, m1Q1 into the form of m1Z2, m1Q2).The statesS1 and S2 are characterized by mutual allocation of both local and multimodal processes. By means of modifying semaphores and indexes in the state S1, a direct transition from digraph GW,1 to digraph GW,2 is possible.In practice, the change of semaphores and indexes related to them means simply the change of the control rules (change of signaling) of the system, the moment the processes are allocated properly (compatible withS1). The solution of this kind neither stops the implementation of the process (work of AGVs, technological routes) nor creates the need for changing their allocation (shift). In case of the modification of the state S6 the transition is immediate and noninvasive; it only requires the change of control.To sum up the above considerations, we can say that the transition between the two digraphsGW,1 and GW,2 is possible if they include states characterized by mutual allocation at every behavior level. This observation leads to the following two properties.Property 1.
DigraphGW,2 is reachable from the digraph GW,1 (which is denoted by GW,1→GW,2) if there are states Sa∈VW,1 and Sb∈VS,2 (where VW,1 is the set of states of the digraph GW,1 and VS,2 is the set of states of the digraph GS,2) sharing mutual allocation of local and multimodal processes: Aa=Ab; mlAa=mlAb, for l=1⋯lp.Property 2.
Two digraphsGW,1 and GW,2 are mutually reachable (which is denoted by GW,1↔GW,2) if GW,1→GW,2 and GW,2→GW,1.In this approach, the problem of digraphs reachability calls for an answer to the following question: Are there two statesSa∈VW,1 and Sb∈VS,2, sharing the same allocations Aa=Ab; mlAa=mlAb, for l=1⋯lp, among states included into GS,1 and GS,2? If such states exist, the transition between the states is possible as a result of modifications of semaphores and indexes. In this context the direct transition is defined as(16)⋯⟶Sa1⟶Sa2⟶⋯⟶Sa(x-1)⟶(Sax⇝Sbx)⟶Sb(x+1)⟶⋯
and the indirect transition as
(17)⋯⟶Sa1⟶⋯⟶(Sax⇝Sdx)⟶⋯⟶Sdld⟶Sbj⟶Sb(j+1)⋯,
where one has the following: Sa1,…,Sa(x-1),Sax,…,Sala—states of digraph GW,1, Sb1,…,Sb(x-1),Sbx,…,Sblb—states of digraph GW,2, Sd1,…,Sdx,Sb(x+1)…,Sdlb—states included into the transitory digraph leading GT to GW,2, Sa1→Sa2—transition between states with SCCP assumption and transitory function δ [16], Sax, Sbx—states with mutual allocation, and Sax⇝Sbx—transition from the state Sax to Sbx as a result of states modification, consisting of a sequence change of semaphores and indexes from Zax, Qax to Zbx, Qax.


#### 3.2.2. Searching Algorithm

In the situation when digraphsGW,1 and GW,2 and transitory processes leading to them are known (in other words, vortexes GS,1 and GS,2 (15) are known), determining the states with mutual allocation is not a complex task. Due to a small number of states (in practice no more than a few hundred states per vortex), all that has to be done is to successively compare all potential variants. An algorithm corresponding to such an approach looks as Algorithm 1.Algorithm 1
function  StatesCoAll (GS,1=(VS,1,ES,1),GS,2=(VS,2,ES,2))
AC=∅
for allSa∈VW,1
for allSb∈VS,2
if(Aa=Ab) & (m1Aa=m1Ab) &...& (mlpAa=mlpAb)then
AC=AC∪(Sa,Sb)
end
end
end
returnAC
endIn Algorithm1, one has the following: GS,1=(VS,1,ES,1), GS,2=(VS,2,ES,2)—input data, vortexes (15), Sa, Sb—states (15) included in the digraph GW,1, GS,2, and AC—set of pairs (Sa,Sb) of states with mutual allocation.The result of Algorithm1 is the set AC including pairs of states (Sa,Sb) with mutual allocations. The states can be used to determine the direct and indirect transitions between digraphs GW,1 and GW,2. Therefore, the existence of a nonempty set AC means a positive answer to the posed question.To make things simple, an assumption can be made that we take into consideration that direct transitions and the digraphs have the same number of states (denoted byld); thus computational complexity of Algorithm 1 is expressed by the function f(ld)=ld2.Algorithm1 makes it possible to evaluate the mutual reachability of only two digraphs GW,1 and GW,2∈DC (set of all cyclic digraphs existing in the space 𝒫). In case of evaluating the mutual reachability of all digraphs from the set DC, it is necessary to make a search of this kind for a pair of processes. The computational complexity in such case amounts to
(18)f(ld,dc)=12(dc2-dc)·ld2,wheredc=|DC|.Owing to polynomial character of the function of computational complexity, the problem of evaluating the mutual reachability of behavior digraphs is not a difficult one. All the computational effort is focused on the stage of determining cyclic digraphs (set DC), that is, solving the problem (10). In order to do so, methods described in [11, 12, 14–16] can be applied.Among the available methods, however, there is a deficit of those which can help determine transient states leading to cyclic digraphs (i.e., digraphsGT). Their usability is therefore limited to evaluating direct transitions (where no information on transient states (processes) is required).In order to determine the transient states, the method of vortex generation can be used. Vortexes determined with use of this method include cyclic processes as well as all transient processes leading to them. The example below illustrates the use of this method for evaluating mutual reachability of behavior digraphs.


### 3.3. Numerical Example

Consider two AGVs supporting multiproduct manufacturing flows and their SCCP models shown in Figures2 and 7(b). Let us assume that the two series manufacturing of three different products follow the routes distinguished by different colored (green, orange, and blue) bold lines.Each workstation can process only unique work-piece from a unique product kind at a given instance. Successive work-pieces following the product route of a given product kind while taking into account local material handling routes are treated as subsequent streams of manufacturing processes (in a given kind of product manufacturing flow) and are modeled as streams of multimodal processes. For instance, see streams ofmP1, mP2, and mP3 from Figure 2 as follows:
(19)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)),ppppppppppppppppppppppik=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R29,R10)),ppppppppppppppppiiipppppik=1,…,4,mp3k=((R1,R27,R4),(R28,R7),(R25,R8),(R18,R9),(R15,R12)),k=1,…,4,
and Figure 7(b) as follows:
(20)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R18,R9),(R15,R12)),k=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R25,R8,R22,R11)),k=1,…,3,mp3k=((R1,R27,R4),(R28,R7),(R29,R10)),k=1,…,3.Both systems use the same fleet of 13 AGVs. A fleet supports work-pieces movements between workstations along the given manufacturing routes. The AGVs flows are modeled by streamsP11, P21, P22, P23, P31, P41, P42, P51, P52, P61, P62, P71, and P81 of local processes P1–P8. Each workstation (in general system resource) can be serviced only by one AGV at the moment. That means that both kinds of flow, that is, products and AGVs flows, are synchronized by a mutual exclusion protocol.Given are the two cyclic schedules of multiproduct manufacturing supported by AVGs (see Figures4 and 6) and corresponding to them two cyclic digraphs (Figures 7(a) and 7(b)). Due to this schedules in first system four work-pieces mPi1, mPi2, mPi3, mPi4 of each product (i=1,2,3) are simultaneously processed in one cycle and one work-piece of each product is outputted at each 80 u.t. In second system four work-pieces of mP1k and three work-pieces of mP2k, mP3k product are simultaneously processed in one cycle and one work-piece of each product is outputted at each 96 u.t.As mentioned before, operation times from the schedules considered take into account periods required for work-piece processing as well as material handling operations, that is, load/unload periods (1 u.t. for the work-piece load and 1 u.t. for its unload; see Figure4). Moreover, the assumed time lags Δtm (see (9) and constraints from Table 2) enable to take into account the work-pieces transportation between workstations. In the case considered all time lags are the same and equal to Δtm=1. Moreover, it is assumed that the input to R1, R2, and R3 and the output of R10, R11, and R12 workstations are loaded and unloaded by dedicated conveyors.The operation timesmT and T of considered systems are defined in Tables 3 and 4. The timing xi,jk, mxi,jk of commencement of operations following the constraints (8), (9) are presented in Tables 5 and 6.Table 3
Times (units) of operations executions of local and multimodal processes from Figure2.
k
=
1,2
,
3,4
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
R
13
÷
R
33
m
t
1
k
—
—
77
—
64
77
—
20
—
—
20
—
1
m
t
2
k
—
77
—
20
10
—
30
—
—
30
—
—
1
m
t
3
k
77
—
—
49
—
—
20
50
20
—
—
10
1
t
1
1
—
—
76
—
—
2
—
—
—
—
—
—
1
t
2
1
—
—
—
—
4
18
—
1
1
—
—
—
1
t
2
2
—
—
—
—
1
1
—
1
1
—
—
—
1
t
2
3
—
—
—
—
3
1
—
1
1
—
—
—
1
t
3
1
—
—
—
—
—
—
—
—
1
—
—
1
1
t
4
1
—
—
—
—
—
—
4
1
—
1
1
—
1
t
4
2
—
—
—
—
—
—
1
1
—
1
1
—
1
t
5
1
1
61
—
1
1
—
—
—
—
—
—
—
1
t
5
2
1
1
—
1
1
—
—
—
—
—
—
—
1
t
6
1
—
—
—
1
—
—
1
—
—
—
—
—
1
t
6
2
—
—
—
1
—
—
1
—
—
—
—
—
1
t
7
1
—
—
—
—
—
—
1
—
—
34
—
—
1
t
8
1
1
—
—
1
—
—
—
—
—
—
—
—
1Table 4
Times (units) of operations executions of local and multimodal processes from Figure7(b).
k
=
1,2
,
3,4
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
R
13
÷
R
33
m
t
1
k
—
—
91
—
64
91
—
20
20
—
—
20
1
m
t
2
k
—
91
—
20
24
—
68
30
—
—
30
—
1
m
t
3
k
91
—
—
68
—
—
20
50
—
—
—
—
1
t
1
1
—
—
90
—
—
2
—
—
—
—
—
—
1
t
2
1
—
—
—
—
4
28
—
1
1
—
—
—
1
t
2
2
—
—
—
—
1
1
—
1
1
—
—
—
1
t
2
3
—
—
—
—
1
1
—
18
1
—
—
—
1
t
3
1
—
—
—
—
—
—
—
—
1
—
—
15
1
t
4
1
—
—
—
—
—
—
1
1
—
1
1
—
1
t
4
2
—
—
—
—
—
—
60
1
—
1
1
—
1
t
5
1
1
62
—
1
1
—
—
—
—
—
—
—
1
t
5
2
1
1
—
6
1
—
—
—
—
—
—
—
1
t
6
1
—
—
—
13
—
—
1
—
—
—
—
—
1
t
6
2
—
—
—
66
—
—
1
—
—
—
—
—
1
t
7
1
—
—
—
—
—
—
1
—
—
81
—
—
1
t
8
1
1
—
—
1
—
—
—
—
—
—
—
—
1Table 5
The timingxi,jk, mxi,jk of commencement of operations of local and multimodal processes from Figure 2.
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
m
x
1
1
—
—
−10
—
146
68
—
211
—
—
232
—
m
x
2
1
—
55
—
144
133
—
165
—
—
190
—
—
m
x
3
1
9
—
—
87
—
—
137
158
209
—
—
230
x
1
1
—
—
−9
—
—
68
—
—
—
—
—
—
x
2
1
—
—
—
—
66
47
—
−8
−6
—
—
—
x
2
2
—
—
—
—
45
71
—
48
49
—
—
—
x
2
3
—
—
—
—
47
−7
—
51
70
—
—
—
x
3
1
—
—
—
—
—
—
—
—
68
—
—
−10
x
4
1
—
—
—
—
—
—
−7
−2
—
71
0
—
x
4
2
—
—
—
—
—
—
−2
70
—
−6
72
—
x
5
1
69
−9
—
57
53
—
—
—
—
—
—
—
x
5
2
−9
53
—
64
62
—
—
—
—
—
—
—
x
6
1
—
—
—
3
—
—
5
—
—
—
—
—
x
6
2
—
—
—
55
—
—
57
—
—
—
—
—
x
7
1
—
—
—
—
—
—
34
—
—
36
—
—
x
8
1
5
—
—
7
—
—
—
—
—
—
—
—Table 6
The timingxi,jk, mxi,jk of commencement of operations of local and multimodal processes from Figure 7(b).
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
m
x
1
1
—
—
−10
—
174
82
—
239
260
—
—
281
m
x
2
1
—
55
—
172
147
—
193
262
—
—
293
—
m
x
3
1
9
—
—
101
—
—
170
—
—
191
—
—
x
1
1
—
—
−9
—
—
82
—
—
—
—
—
—
x
2
1
—
—
—
—
80
51
—
−9
−1
—
—
—
x
2
2
—
—
—
—
49
85
—
51
53
—
—
—
x
2
3
—
—
—
—
51
−7
—
53
72
—
—
—
x
3
1
—
—
—
—
—
—
—
—
91
—
—
−1
x
4
1
—
—
—
—
—
—
−7
−5
—
85
11
—
x
4
2
—
—
—
—
—
—
13
74
—
11
103
—
x
5
1
78
−10
—
76
53
—
—
—
—
—
—
—
x
5
2
−9
53
—
78
76
—
—
—
—
—
—
—
x
6
1
—
—
—
−9
—
—
5
—
—
—
—
—
x
6
2
—
—
—
9
—
—
76
—
—
—
—
—
x
7
1
—
—
—
—
—
—
1
—
—
3
—
—
x
8
1
5
—
—
7
—
—
—
—
—
—
—
—The values presented in Tables3–6 are the results of solving the problem (10), respectively, for the system from Figure 2 and Figure 7(b). In order to achieve this objective, OzMozart constraint programming environment was applied. The problem solving time in both cases did not exceed 3 seconds (Intel Core 2 Duo 3 GHz, RAM 4 GB).During the analysis of digraphs of the attained schedules, it turned out that it is possible to smoothly change the behavior (with use of the stateS18) from the one presented in Figure 4 into the behavior from Figure 7. The transition was illustrated in Figures 11 and 12. In practice, a transition of this kind means the possibility of changing the current production order into a new one with no need to stop the system.Therefore, a question may be posed whether an inverse situation is possible, when from the behavior represented by digraphGW,2, behavior GW,1 is attained (return to GW,1). In other words, the question is the following: Are the considered behavior digraphs mutually reachable, GW,1↔GW,2?According to Property2 it is possible if GW,1→GW,2 and GW,2→GW,1. The schedule shown in Figure 10 illustrates the reachability GW,1→GW,2. In order to determine whether GW,2→GW,1 is possible, it must be stated (Property 1) if there are states of mutual allocations in digraphs GW,2 and GS,1 (GS,1—digraph including GW,1 and transitory path of states leading to it).Figure 10
The indirect transition between schedules from Figures4 and 6.Figure 11
The indirect transition between schedules from Figures6 and 4.Figure 12
The indirect transition between cyclic steady states:GW,1→GW,2 and GW,2→GW,1.In order to determine these states, Algorithm1 was applied. The use of Algorithm 1 depended upon the knowledge of digraph GS,1. It should be emphasized that the solution of the problem (10) makes it possible to determine the cyclic schedule and digraph GW,1 corresponding to it. It does not allow, however, determining states belonging to transitory processes. In the discussed case digraph GS,1 is unknown. Yet, the state of cyclic processes can be determined from digraph GW,1 by means of searching for parents of the states VW,1 not belonging to this set. Therefore, next state function δ defined in [16] was applied.Based on the determined states, a search for mutual allocation states was carried out. An example of such states are the statesS19, S40. A change of cyclic steady states based on these states (consisting of changing priority rules, semaphores and indexes) was illustrated in Figures 11 and 12.As shown in Figure12 the considered cyclic steady states are mutually reachable (GW,1→GW,2 and GW,2→GW,1). In general case, however, mutual reachability is not always guaranteed. For instance, consider SCCP composed of four cyclic processes shown in Figure 13(a). The cyclic steady state space 𝒫 consists of two vortexes GS,1 and GS,2; see Figure 13(b). There are five different transient periods linking GW,1 and GW,2; see orange arcs. There is not, however, any transient period linking GS,2 and GS,1; that is, there are not any states shared by GW,2 and GS,1 while following Property 1. Moreover, both direct mutual reachability and indirect mutual reachability are not guaranteed in general case of a cyclic steady state space.Illustration of SCCP composed of four local cyclic processes (a) and cyclic steady state space𝒫 including transient states depicting mutual reachability GW,1→GW,2 (b).
(a)
(b)


## 3.1. Problem Formulation

The question of the possibility of smoothly changing the cyclic behaviors of the system is related to the problem of mutual reachability of the two behavior digraphsGW,1, GW,2. The digraphs presented so far (Figure 7) are cycles. In general, a digraph may take the form of the so-called vortex GS, that is, a digraph including a cycle representing a cyclic steady states GW and a tree GT,i representing transient states leading to cyclic steady states. An example of two vortexes GS,1, GS,2 is shown in Figure 8. Formally, the digraph of the vortex type is defined as follows:
(15)GS=(VS,ES)=GW∪(⋃i=1ltGT,i),
where ⋃i=1ltGT,i=GT,1∪GT,2∪⋯∪GT,lt, lt is the number of trees GT,i leading to GW cycle.Figure 8
Illustration of the cyclic steady state space composed of two vortexes.In this approach, the problem of mutual reachability of the behavior digraphs of mutual space of states is defined as follows: there is a given structureSClp and the cyclic steady state space 𝒫=(V𝒫,E𝒫) resulting from it, which includes two vortexes GS,1, GS,2 that represent two cyclic steady processes. It is therefore necessary to find answer to the following question: Are the digraphs GW,1, GW,2 (being subdigraphs of GS,1, GS,2) mutually reachable (Figure 8)? In the case they are mutually reachable the next question is how to make a transition between the digraphs?In other words, the question of mutual reachability of cyclic behaviors can be treated as the question of the possibility of direct or indirect transition between the digraphsGW,1, GW,2. An example of such transitions is shown in Figure 8. An indirect transition should be understood as changing GW,1 into GW,2, resulting from the transition of the state Sx′ into transitory path (a path of digraph GT,i) leading to GW,2. The direct transition means a transition from the state Sx right into the cycle GW,1.


## 3.2. Searching for States with Mutual Allocation

### 3.2.1. Sufficient Conditions

The possibility of transitions between cyclic steady states depends on the stateSx(Sx′), which is an element of two digraphs: GS,1 and GS,2. In other words, it is necessary that in case of direct transition the following transitions between states occur:(i)
for allSk∈VW,1 (Sk→⋯→Sx→⋯→Sk) for the digraph GW,1,(ii)
for allSl∈VW,2 (Sl→⋯→Sx→⋯→Sl) for the digraph GW,2.In SCCP, transitions of this kind are not acceptable. It results from the property saying that each state has at least one descendant [16] (a descendant is the consecutive state after Sx). The presence of stateSx included simultaneously into two digraphs (GW,1,GW,2) would require the existence of at least two descendants of the state Sx.Although there are no mutual states at the level of the space of states𝒫, the different projections of states upon lower levels of behavior as well as their components (space of allocation, semaphores, etc.) may be elements belonging to numerous digraphs at the same time.An example of such a situation is shown in Figure9, where the idea of a multilevel model of the cyclic steady states space 𝒫 has been applied. The figure shows the projection of the space 𝒫 upon the level of local processes behavior 𝒫SL (the second level in Figure 9) and upon the space of allocation 𝒜 (the lowest level in Figure 9). The elements of the space 𝒜 are the allocations Ar of the local states Slr=(Ar,Zr,Qr) occurring in the space 𝒫SL=(VSL,ESL) (where Slr∈VSL), which at the same time is the projection of the space of states 𝒫.Figure 9
Illustration of cyclic steady state space projections,𝒫SL and 𝒜, for behavior digraphs from Figure 8.It is worth mentioning that some allocations of the space𝒜 are simultaneously mutual for several states. For example, the allocation A2∈𝒜 is at the same time an element of the state Sl3=(A2,Z3,Q3) and the state Sl4=(A2,Z4,Q4). In practice, it means that in both states the local processes (representing, e.g., means of transport such as AGVs) are allocated on the same resources. However, since there are various access rights (determined by Z3, Q3 and Z4, Q4) their further implantation will be different.The existence of states of common allocation can be used for the transitions between various behavior digraphs. The statesSl3 and Sl4 differ only with the sequence of semaphores and indexes. Thus, if in the state Sl3 with allocation A2, the form of Z3, Q3changes into the form of Z4, Q4, we will attain the state Sl4 leading to another cycle.The modification of the stateSl3 into Sl4 by changing the form of semaphores and indexes allows for an indirect transition between cyclic processes of the space 𝒫0. The direct transition is possible as a result of modifying the semaphores and indexes of the states Sl1=(A1,Z1,Q1) and Sl2=(A1,Z2,Q2) mutually sharing the allocation A1. Therefore, the presence of states of mutual allocation implies the possibility of changing the set of cyclic steady states.The considered transitions betweenSl3 and Sl4 as well as Sl1 and Sl2 refer mainly to digraphs occurring only at the local level (i.e., space 𝒫SL). In case of digraphs GS,1, GS,2 of the space 𝒫 a similar procedure should be followed. These states are the projections of the corresponding states from the space 𝒫. The state Sl1 is the projection of the state S1=(Sl1,m1S1), which is an element of the digraph GW,1, and the state S2=(Sl2,m1S2) is the projection of the digraph GW,2.If, among states projecting uponSl1 and Sl2, there are states (e.g., states Sl1 and Sl2) with mutual allocation m1Ax of the multimodal processes, the transition between GW,1 and GW,2 (and therefore also between GS,1 and GS,2) is possible as a result of modifications of corresponding semaphores and indexes (from the form of m1Z1, m1Q1 into the form of m1Z2, m1Q2).The statesS1 and S2 are characterized by mutual allocation of both local and multimodal processes. By means of modifying semaphores and indexes in the state S1, a direct transition from digraph GW,1 to digraph GW,2 is possible.In practice, the change of semaphores and indexes related to them means simply the change of the control rules (change of signaling) of the system, the moment the processes are allocated properly (compatible withS1). The solution of this kind neither stops the implementation of the process (work of AGVs, technological routes) nor creates the need for changing their allocation (shift). In case of the modification of the state S6 the transition is immediate and noninvasive; it only requires the change of control.To sum up the above considerations, we can say that the transition between the two digraphsGW,1 and GW,2 is possible if they include states characterized by mutual allocation at every behavior level. This observation leads to the following two properties.Property 1.
DigraphGW,2 is reachable from the digraph GW,1 (which is denoted by GW,1→GW,2) if there are states Sa∈VW,1 and Sb∈VS,2 (where VW,1 is the set of states of the digraph GW,1 and VS,2 is the set of states of the digraph GS,2) sharing mutual allocation of local and multimodal processes: Aa=Ab; mlAa=mlAb, for l=1⋯lp.Property 2.
Two digraphsGW,1 and GW,2 are mutually reachable (which is denoted by GW,1↔GW,2) if GW,1→GW,2 and GW,2→GW,1.In this approach, the problem of digraphs reachability calls for an answer to the following question: Are there two statesSa∈VW,1 and Sb∈VS,2, sharing the same allocations Aa=Ab; mlAa=mlAb, for l=1⋯lp, among states included into GS,1 and GS,2? If such states exist, the transition between the states is possible as a result of modifications of semaphores and indexes. In this context the direct transition is defined as(16)⋯⟶Sa1⟶Sa2⟶⋯⟶Sa(x-1)⟶(Sax⇝Sbx)⟶Sb(x+1)⟶⋯
and the indirect transition as
(17)⋯⟶Sa1⟶⋯⟶(Sax⇝Sdx)⟶⋯⟶Sdld⟶Sbj⟶Sb(j+1)⋯,
where one has the following: Sa1,…,Sa(x-1),Sax,…,Sala—states of digraph GW,1, Sb1,…,Sb(x-1),Sbx,…,Sblb—states of digraph GW,2, Sd1,…,Sdx,Sb(x+1)…,Sdlb—states included into the transitory digraph leading GT to GW,2, Sa1→Sa2—transition between states with SCCP assumption and transitory function δ [16], Sax, Sbx—states with mutual allocation, and Sax⇝Sbx—transition from the state Sax to Sbx as a result of states modification, consisting of a sequence change of semaphores and indexes from Zax, Qax to Zbx, Qax.


### 3.2.2. Searching Algorithm

In the situation when digraphsGW,1 and GW,2 and transitory processes leading to them are known (in other words, vortexes GS,1 and GS,2 (15) are known), determining the states with mutual allocation is not a complex task. Due to a small number of states (in practice no more than a few hundred states per vortex), all that has to be done is to successively compare all potential variants. An algorithm corresponding to such an approach looks as Algorithm 1.Algorithm 1
function  StatesCoAll (GS,1=(VS,1,ES,1),GS,2=(VS,2,ES,2))
AC=∅
for allSa∈VW,1
for allSb∈VS,2
if(Aa=Ab) & (m1Aa=m1Ab) &...& (mlpAa=mlpAb)then
AC=AC∪(Sa,Sb)
end
end
end
returnAC
endIn Algorithm1, one has the following: GS,1=(VS,1,ES,1), GS,2=(VS,2,ES,2)—input data, vortexes (15), Sa, Sb—states (15) included in the digraph GW,1, GS,2, and AC—set of pairs (Sa,Sb) of states with mutual allocation.The result of Algorithm1 is the set AC including pairs of states (Sa,Sb) with mutual allocations. The states can be used to determine the direct and indirect transitions between digraphs GW,1 and GW,2. Therefore, the existence of a nonempty set AC means a positive answer to the posed question.To make things simple, an assumption can be made that we take into consideration that direct transitions and the digraphs have the same number of states (denoted byld); thus computational complexity of Algorithm 1 is expressed by the function f(ld)=ld2.Algorithm1 makes it possible to evaluate the mutual reachability of only two digraphs GW,1 and GW,2∈DC (set of all cyclic digraphs existing in the space 𝒫). In case of evaluating the mutual reachability of all digraphs from the set DC, it is necessary to make a search of this kind for a pair of processes. The computational complexity in such case amounts to
(18)f(ld,dc)=12(dc2-dc)·ld2,wheredc=|DC|.Owing to polynomial character of the function of computational complexity, the problem of evaluating the mutual reachability of behavior digraphs is not a difficult one. All the computational effort is focused on the stage of determining cyclic digraphs (set DC), that is, solving the problem (10). In order to do so, methods described in [11, 12, 14–16] can be applied.Among the available methods, however, there is a deficit of those which can help determine transient states leading to cyclic digraphs (i.e., digraphsGT). Their usability is therefore limited to evaluating direct transitions (where no information on transient states (processes) is required).In order to determine the transient states, the method of vortex generation can be used. Vortexes determined with use of this method include cyclic processes as well as all transient processes leading to them. The example below illustrates the use of this method for evaluating mutual reachability of behavior digraphs.


## 3.2.1. Sufficient Conditions

The possibility of transitions between cyclic steady states depends on the stateSx(Sx′), which is an element of two digraphs: GS,1 and GS,2. In other words, it is necessary that in case of direct transition the following transitions between states occur:(i)
for allSk∈VW,1 (Sk→⋯→Sx→⋯→Sk) for the digraph GW,1,(ii)
for allSl∈VW,2 (Sl→⋯→Sx→⋯→Sl) for the digraph GW,2.In SCCP, transitions of this kind are not acceptable. It results from the property saying that each state has at least one descendant [16] (a descendant is the consecutive state after Sx). The presence of stateSx included simultaneously into two digraphs (GW,1,GW,2) would require the existence of at least two descendants of the state Sx.Although there are no mutual states at the level of the space of states𝒫, the different projections of states upon lower levels of behavior as well as their components (space of allocation, semaphores, etc.) may be elements belonging to numerous digraphs at the same time.An example of such a situation is shown in Figure9, where the idea of a multilevel model of the cyclic steady states space 𝒫 has been applied. The figure shows the projection of the space 𝒫 upon the level of local processes behavior 𝒫SL (the second level in Figure 9) and upon the space of allocation 𝒜 (the lowest level in Figure 9). The elements of the space 𝒜 are the allocations Ar of the local states Slr=(Ar,Zr,Qr) occurring in the space 𝒫SL=(VSL,ESL) (where Slr∈VSL), which at the same time is the projection of the space of states 𝒫.Figure 9
Illustration of cyclic steady state space projections,𝒫SL and 𝒜, for behavior digraphs from Figure 8.It is worth mentioning that some allocations of the space𝒜 are simultaneously mutual for several states. For example, the allocation A2∈𝒜 is at the same time an element of the state Sl3=(A2,Z3,Q3) and the state Sl4=(A2,Z4,Q4). In practice, it means that in both states the local processes (representing, e.g., means of transport such as AGVs) are allocated on the same resources. However, since there are various access rights (determined by Z3, Q3 and Z4, Q4) their further implantation will be different.The existence of states of common allocation can be used for the transitions between various behavior digraphs. The statesSl3 and Sl4 differ only with the sequence of semaphores and indexes. Thus, if in the state Sl3 with allocation A2, the form of Z3, Q3changes into the form of Z4, Q4, we will attain the state Sl4 leading to another cycle.The modification of the stateSl3 into Sl4 by changing the form of semaphores and indexes allows for an indirect transition between cyclic processes of the space 𝒫0. The direct transition is possible as a result of modifying the semaphores and indexes of the states Sl1=(A1,Z1,Q1) and Sl2=(A1,Z2,Q2) mutually sharing the allocation A1. Therefore, the presence of states of mutual allocation implies the possibility of changing the set of cyclic steady states.The considered transitions betweenSl3 and Sl4 as well as Sl1 and Sl2 refer mainly to digraphs occurring only at the local level (i.e., space 𝒫SL). In case of digraphs GS,1, GS,2 of the space 𝒫 a similar procedure should be followed. These states are the projections of the corresponding states from the space 𝒫. The state Sl1 is the projection of the state S1=(Sl1,m1S1), which is an element of the digraph GW,1, and the state S2=(Sl2,m1S2) is the projection of the digraph GW,2.If, among states projecting uponSl1 and Sl2, there are states (e.g., states Sl1 and Sl2) with mutual allocation m1Ax of the multimodal processes, the transition between GW,1 and GW,2 (and therefore also between GS,1 and GS,2) is possible as a result of modifications of corresponding semaphores and indexes (from the form of m1Z1, m1Q1 into the form of m1Z2, m1Q2).The statesS1 and S2 are characterized by mutual allocation of both local and multimodal processes. By means of modifying semaphores and indexes in the state S1, a direct transition from digraph GW,1 to digraph GW,2 is possible.In practice, the change of semaphores and indexes related to them means simply the change of the control rules (change of signaling) of the system, the moment the processes are allocated properly (compatible withS1). The solution of this kind neither stops the implementation of the process (work of AGVs, technological routes) nor creates the need for changing their allocation (shift). In case of the modification of the state S6 the transition is immediate and noninvasive; it only requires the change of control.To sum up the above considerations, we can say that the transition between the two digraphsGW,1 and GW,2 is possible if they include states characterized by mutual allocation at every behavior level. This observation leads to the following two properties.Property 1.
DigraphGW,2 is reachable from the digraph GW,1 (which is denoted by GW,1→GW,2) if there are states Sa∈VW,1 and Sb∈VS,2 (where VW,1 is the set of states of the digraph GW,1 and VS,2 is the set of states of the digraph GS,2) sharing mutual allocation of local and multimodal processes: Aa=Ab; mlAa=mlAb, for l=1⋯lp.Property 2.
Two digraphsGW,1 and GW,2 are mutually reachable (which is denoted by GW,1↔GW,2) if GW,1→GW,2 and GW,2→GW,1.In this approach, the problem of digraphs reachability calls for an answer to the following question: Are there two statesSa∈VW,1 and Sb∈VS,2, sharing the same allocations Aa=Ab; mlAa=mlAb, for l=1⋯lp, among states included into GS,1 and GS,2? If such states exist, the transition between the states is possible as a result of modifications of semaphores and indexes. In this context the direct transition is defined as(16)⋯⟶Sa1⟶Sa2⟶⋯⟶Sa(x-1)⟶(Sax⇝Sbx)⟶Sb(x+1)⟶⋯
and the indirect transition as
(17)⋯⟶Sa1⟶⋯⟶(Sax⇝Sdx)⟶⋯⟶Sdld⟶Sbj⟶Sb(j+1)⋯,
where one has the following: Sa1,…,Sa(x-1),Sax,…,Sala—states of digraph GW,1, Sb1,…,Sb(x-1),Sbx,…,Sblb—states of digraph GW,2, Sd1,…,Sdx,Sb(x+1)…,Sdlb—states included into the transitory digraph leading GT to GW,2, Sa1→Sa2—transition between states with SCCP assumption and transitory function δ [16], Sax, Sbx—states with mutual allocation, and Sax⇝Sbx—transition from the state Sax to Sbx as a result of states modification, consisting of a sequence change of semaphores and indexes from Zax, Qax to Zbx, Qax.


## 3.2.2. Searching Algorithm

In the situation when digraphsGW,1 and GW,2 and transitory processes leading to them are known (in other words, vortexes GS,1 and GS,2 (15) are known), determining the states with mutual allocation is not a complex task. Due to a small number of states (in practice no more than a few hundred states per vortex), all that has to be done is to successively compare all potential variants. An algorithm corresponding to such an approach looks as Algorithm 1.Algorithm 1
function  StatesCoAll (GS,1=(VS,1,ES,1),GS,2=(VS,2,ES,2))
AC=∅
for allSa∈VW,1
for allSb∈VS,2
if(Aa=Ab) & (m1Aa=m1Ab) &...& (mlpAa=mlpAb)then
AC=AC∪(Sa,Sb)
end
end
end
returnAC
endIn Algorithm1, one has the following: GS,1=(VS,1,ES,1), GS,2=(VS,2,ES,2)—input data, vortexes (15), Sa, Sb—states (15) included in the digraph GW,1, GS,2, and AC—set of pairs (Sa,Sb) of states with mutual allocation.The result of Algorithm1 is the set AC including pairs of states (Sa,Sb) with mutual allocations. The states can be used to determine the direct and indirect transitions between digraphs GW,1 and GW,2. Therefore, the existence of a nonempty set AC means a positive answer to the posed question.To make things simple, an assumption can be made that we take into consideration that direct transitions and the digraphs have the same number of states (denoted byld); thus computational complexity of Algorithm 1 is expressed by the function f(ld)=ld2.Algorithm1 makes it possible to evaluate the mutual reachability of only two digraphs GW,1 and GW,2∈DC (set of all cyclic digraphs existing in the space 𝒫). In case of evaluating the mutual reachability of all digraphs from the set DC, it is necessary to make a search of this kind for a pair of processes. The computational complexity in such case amounts to
(18)f(ld,dc)=12(dc2-dc)·ld2,wheredc=|DC|.Owing to polynomial character of the function of computational complexity, the problem of evaluating the mutual reachability of behavior digraphs is not a difficult one. All the computational effort is focused on the stage of determining cyclic digraphs (set DC), that is, solving the problem (10). In order to do so, methods described in [11, 12, 14–16] can be applied.Among the available methods, however, there is a deficit of those which can help determine transient states leading to cyclic digraphs (i.e., digraphsGT). Their usability is therefore limited to evaluating direct transitions (where no information on transient states (processes) is required).In order to determine the transient states, the method of vortex generation can be used. Vortexes determined with use of this method include cyclic processes as well as all transient processes leading to them. The example below illustrates the use of this method for evaluating mutual reachability of behavior digraphs.


## 3.3. Numerical Example

Consider two AGVs supporting multiproduct manufacturing flows and their SCCP models shown in Figures2 and 7(b). Let us assume that the two series manufacturing of three different products follow the routes distinguished by different colored (green, orange, and blue) bold lines.Each workstation can process only unique work-piece from a unique product kind at a given instance. Successive work-pieces following the product route of a given product kind while taking into account local material handling routes are treated as subsequent streams of manufacturing processes (in a given kind of product manufacturing flow) and are modeled as streams of multimodal processes. For instance, see streams ofmP1, mP2, and mP3 from Figure 2 as follows:
(19)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R22,R11)),ppppppppppppppppppppppik=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R29,R10)),ppppppppppppppppiiipppppik=1,…,4,mp3k=((R1,R27,R4),(R28,R7),(R25,R8),(R18,R9),(R15,R12)),k=1,…,4,
and Figure 7(b) as follows:
(20)mp1k=((R3,R13,R6),(R17,R5),(R21,R8),(R18,R9),(R15,R12)),k=1,…,4,mp2k=((R2,R20,R5),(R24,R4),(R28,R7),(R25,R8,R22,R11)),k=1,…,3,mp3k=((R1,R27,R4),(R28,R7),(R29,R10)),k=1,…,3.Both systems use the same fleet of 13 AGVs. A fleet supports work-pieces movements between workstations along the given manufacturing routes. The AGVs flows are modeled by streamsP11, P21, P22, P23, P31, P41, P42, P51, P52, P61, P62, P71, and P81 of local processes P1–P8. Each workstation (in general system resource) can be serviced only by one AGV at the moment. That means that both kinds of flow, that is, products and AGVs flows, are synchronized by a mutual exclusion protocol.Given are the two cyclic schedules of multiproduct manufacturing supported by AVGs (see Figures4 and 6) and corresponding to them two cyclic digraphs (Figures 7(a) and 7(b)). Due to this schedules in first system four work-pieces mPi1, mPi2, mPi3, mPi4 of each product (i=1,2,3) are simultaneously processed in one cycle and one work-piece of each product is outputted at each 80 u.t. In second system four work-pieces of mP1k and three work-pieces of mP2k, mP3k product are simultaneously processed in one cycle and one work-piece of each product is outputted at each 96 u.t.As mentioned before, operation times from the schedules considered take into account periods required for work-piece processing as well as material handling operations, that is, load/unload periods (1 u.t. for the work-piece load and 1 u.t. for its unload; see Figure4). Moreover, the assumed time lags Δtm (see (9) and constraints from Table 2) enable to take into account the work-pieces transportation between workstations. In the case considered all time lags are the same and equal to Δtm=1. Moreover, it is assumed that the input to R1, R2, and R3 and the output of R10, R11, and R12 workstations are loaded and unloaded by dedicated conveyors.The operation timesmT and T of considered systems are defined in Tables 3 and 4. The timing xi,jk, mxi,jk of commencement of operations following the constraints (8), (9) are presented in Tables 5 and 6.Table 3
Times (units) of operations executions of local and multimodal processes from Figure2.
k
=
1,2
,
3,4
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
R
13
÷
R
33
m
t
1
k
—
—
77
—
64
77
—
20
—
—
20
—
1
m
t
2
k
—
77
—
20
10
—
30
—
—
30
—
—
1
m
t
3
k
77
—
—
49
—
—
20
50
20
—
—
10
1
t
1
1
—
—
76
—
—
2
—
—
—
—
—
—
1
t
2
1
—
—
—
—
4
18
—
1
1
—
—
—
1
t
2
2
—
—
—
—
1
1
—
1
1
—
—
—
1
t
2
3
—
—
—
—
3
1
—
1
1
—
—
—
1
t
3
1
—
—
—
—
—
—
—
—
1
—
—
1
1
t
4
1
—
—
—
—
—
—
4
1
—
1
1
—
1
t
4
2
—
—
—
—
—
—
1
1
—
1
1
—
1
t
5
1
1
61
—
1
1
—
—
—
—
—
—
—
1
t
5
2
1
1
—
1
1
—
—
—
—
—
—
—
1
t
6
1
—
—
—
1
—
—
1
—
—
—
—
—
1
t
6
2
—
—
—
1
—
—
1
—
—
—
—
—
1
t
7
1
—
—
—
—
—
—
1
—
—
34
—
—
1
t
8
1
1
—
—
1
—
—
—
—
—
—
—
—
1Table 4
Times (units) of operations executions of local and multimodal processes from Figure7(b).
k
=
1,2
,
3,4
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
R
13
÷
R
33
m
t
1
k
—
—
91
—
64
91
—
20
20
—
—
20
1
m
t
2
k
—
91
—
20
24
—
68
30
—
—
30
—
1
m
t
3
k
91
—
—
68
—
—
20
50
—
—
—
—
1
t
1
1
—
—
90
—
—
2
—
—
—
—
—
—
1
t
2
1
—
—
—
—
4
28
—
1
1
—
—
—
1
t
2
2
—
—
—
—
1
1
—
1
1
—
—
—
1
t
2
3
—
—
—
—
1
1
—
18
1
—
—
—
1
t
3
1
—
—
—
—
—
—
—
—
1
—
—
15
1
t
4
1
—
—
—
—
—
—
1
1
—
1
1
—
1
t
4
2
—
—
—
—
—
—
60
1
—
1
1
—
1
t
5
1
1
62
—
1
1
—
—
—
—
—
—
—
1
t
5
2
1
1
—
6
1
—
—
—
—
—
—
—
1
t
6
1
—
—
—
13
—
—
1
—
—
—
—
—
1
t
6
2
—
—
—
66
—
—
1
—
—
—
—
—
1
t
7
1
—
—
—
—
—
—
1
—
—
81
—
—
1
t
8
1
1
—
—
1
—
—
—
—
—
—
—
—
1Table 5
The timingxi,jk, mxi,jk of commencement of operations of local and multimodal processes from Figure 2.
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
m
x
1
1
—
—
−10
—
146
68
—
211
—
—
232
—
m
x
2
1
—
55
—
144
133
—
165
—
—
190
—
—
m
x
3
1
9
—
—
87
—
—
137
158
209
—
—
230
x
1
1
—
—
−9
—
—
68
—
—
—
—
—
—
x
2
1
—
—
—
—
66
47
—
−8
−6
—
—
—
x
2
2
—
—
—
—
45
71
—
48
49
—
—
—
x
2
3
—
—
—
—
47
−7
—
51
70
—
—
—
x
3
1
—
—
—
—
—
—
—
—
68
—
—
−10
x
4
1
—
—
—
—
—
—
−7
−2
—
71
0
—
x
4
2
—
—
—
—
—
—
−2
70
—
−6
72
—
x
5
1
69
−9
—
57
53
—
—
—
—
—
—
—
x
5
2
−9
53
—
64
62
—
—
—
—
—
—
—
x
6
1
—
—
—
3
—
—
5
—
—
—
—
—
x
6
2
—
—
—
55
—
—
57
—
—
—
—
—
x
7
1
—
—
—
—
—
—
34
—
—
36
—
—
x
8
1
5
—
—
7
—
—
—
—
—
—
—
—Table 6
The timingxi,jk, mxi,jk of commencement of operations of local and multimodal processes from Figure 7(b).
R
1
R
2
R
3
R
4
R
5
R
6
R
7
R
8
R
9
R
10
R
11
R
12
m
x
1
1
—
—
−10
—
174
82
—
239
260
—
—
281
m
x
2
1
—
55
—
172
147
—
193
262
—
—
293
—
m
x
3
1
9
—
—
101
—
—
170
—
—
191
—
—
x
1
1
—
—
−9
—
—
82
—
—
—
—
—
—
x
2
1
—
—
—
—
80
51
—
−9
−1
—
—
—
x
2
2
—
—
—
—
49
85
—
51
53
—
—
—
x
2
3
—
—
—
—
51
−7
—
53
72
—
—
—
x
3
1
—
—
—
—
—
—
—
—
91
—
—
−1
x
4
1
—
—
—
—
—
—
−7
−5
—
85
11
—
x
4
2
—
—
—
—
—
—
13
74
—
11
103
—
x
5
1
78
−10
—
76
53
—
—
—
—
—
—
—
x
5
2
−9
53
—
78
76
—
—
—
—
—
—
—
x
6
1
—
—
—
−9
—
—
5
—
—
—
—
—
x
6
2
—
—
—
9
—
—
76
—
—
—
—
—
x
7
1
—
—
—
—
—
—
1
—
—
3
—
—
x
8
1
5
—
—
7
—
—
—
—
—
—
—
—The values presented in Tables3–6 are the results of solving the problem (10), respectively, for the system from Figure 2 and Figure 7(b). In order to achieve this objective, OzMozart constraint programming environment was applied. The problem solving time in both cases did not exceed 3 seconds (Intel Core 2 Duo 3 GHz, RAM 4 GB).During the analysis of digraphs of the attained schedules, it turned out that it is possible to smoothly change the behavior (with use of the stateS18) from the one presented in Figure 4 into the behavior from Figure 7. The transition was illustrated in Figures 11 and 12. In practice, a transition of this kind means the possibility of changing the current production order into a new one with no need to stop the system.Therefore, a question may be posed whether an inverse situation is possible, when from the behavior represented by digraphGW,2, behavior GW,1 is attained (return to GW,1). In other words, the question is the following: Are the considered behavior digraphs mutually reachable, GW,1↔GW,2?According to Property2 it is possible if GW,1→GW,2 and GW,2→GW,1. The schedule shown in Figure 10 illustrates the reachability GW,1→GW,2. In order to determine whether GW,2→GW,1 is possible, it must be stated (Property 1) if there are states of mutual allocations in digraphs GW,2 and GS,1 (GS,1—digraph including GW,1 and transitory path of states leading to it).Figure 10
The indirect transition between schedules from Figures4 and 6.Figure 11
The indirect transition between schedules from Figures6 and 4.Figure 12
The indirect transition between cyclic steady states:GW,1→GW,2 and GW,2→GW,1.In order to determine these states, Algorithm1 was applied. The use of Algorithm 1 depended upon the knowledge of digraph GS,1. It should be emphasized that the solution of the problem (10) makes it possible to determine the cyclic schedule and digraph GW,1 corresponding to it. It does not allow, however, determining states belonging to transitory processes. In the discussed case digraph GS,1 is unknown. Yet, the state of cyclic processes can be determined from digraph GW,1 by means of searching for parents of the states VW,1 not belonging to this set. Therefore, next state function δ defined in [16] was applied.Based on the determined states, a search for mutual allocation states was carried out. An example of such states are the statesS19, S40. A change of cyclic steady states based on these states (consisting of changing priority rules, semaphores and indexes) was illustrated in Figures 11 and 12.As shown in Figure12 the considered cyclic steady states are mutually reachable (GW,1→GW,2 and GW,2→GW,1). In general case, however, mutual reachability is not always guaranteed. For instance, consider SCCP composed of four cyclic processes shown in Figure 13(a). The cyclic steady state space 𝒫 consists of two vortexes GS,1 and GS,2; see Figure 13(b). There are five different transient periods linking GW,1 and GW,2; see orange arcs. There is not, however, any transient period linking GS,2 and GS,1; that is, there are not any states shared by GW,2 and GS,1 while following Property 1. Moreover, both direct mutual reachability and indirect mutual reachability are not guaranteed in general case of a cyclic steady state space.Illustration of SCCP composed of four local cyclic processes (a) and cyclic steady state space𝒫 including transient states depicting mutual reachability GW,1→GW,2 (b).
(a)
(b)


## 4. Related Work

Many algorithms for the scheduling and routing of AGVs have been proposed. However, most of the existing results are applicable to systems with a small number of AGVs, offering a low degree of concurrency. With a drastically increased number of AGVs in recent applications (e.g., in the order of a hundred in a container handling system), the combinatorial nature of the fleet scheduling and assignment problems rapidly increases the complexity. For instance, it appears clearly through constraints which relate to assigning a fleet to a route. Suppose that there aren fleet and m routes, the number of binary decisions variables is m×n and theoretically, there are 2n×m solutions to be considered. In fact, according to computational complexity, this problem is NP-hard [2]. A number of papers are concerned with the fleet assignment problem [1–3, 8] and maintenance planning [6, 7, 21]. However, few papers have considered the combination of fleet assignment and maintenance planning [2, 22]. Most publications on fleet assignment have been focused on the assignment of fleets to minimize the fleet operation cost [1, 3, 8]. Some papers on maintenance planning have been focused on planning maintenance tasks to minimize the maintenance cost [6, 7, 21]. Few papers have considered the integration of fleet assignment and maintenance planning [2, 22]. The inventory policy with preventive maintenance consideration is mostly studied for production system [6, 23, 24]. Because of unpredicted situations, rescheduling is required to deal with online decision making. Finally, scheduling and rescheduling fleet assignment and maintenance planning and inventory policy are implemented as a decision support system [22].Because most of real-life available manufacturing processes manifest their cyclic steady state the alternative approach to AGVs fleet dispatching and scheduling, for example, following from the SCCP concept [1, 9, 25] can be considered as well. Many models and methods have been proposed to solve the cyclic scheduling problem so far. Most of these are oriented at finding a minimal cycle or maximal throughput while assuming deadlock-free processes flow. The approaches trying to estimate the cycle time from cyclic processes structure and the synchronization mechanism employed (i.e., mutual exclusion instances) are quite unique.In that context our main contribution is to propose a new modeling framework enabling to state and answer the following questions: Does there exist a control procedure (e.g., a set of dispatching rules and an initial state) guaranteeing an assumed steady cyclic state subject to SCCP’s structure constraints? Does an SCCP’s structure exist such that a steady cyclic state can be achieved?Is the cyclic steady sate space empty? In the case the space is not empty the next question is do the cyclic steady states are mutually reachable?The last question refers to the problem of multimodal processes rescheduling. Most of so far proposed approaches to the rescheduling of processes executed within multimodal transportation networks environment [17, 26–28] are only limited to the deadlock-free cases. It should be noted that, however, the evolutionary algorithms driven approaches frequently used [26–28] are not effective in cases allowing deadlocks occurrence. The approach proposed allows finding deadlock-free transitions between the reachable cyclic steady states while avoiding the deadlocks in the course of the transient state generation.


## 5. Conclusions

The complicated problem which integrates AGVs fleet assignment, routing, and scheduling, generating a suboptimal cyclic schedule for multiproduct manufacturing, is novelty of this research. Such integrated AGVs dispatching problems can be seen as a special case of the cyclic blocking flow-shop one, where the jobs might block either the machine or the AGV at the processing time. Therefore the main class of problems of AGVs fleet match-up scheduling with reference schedule of assumed production flow belong to the NP-hard ones.Besides the above mentioned AGVs dispatching/planning issues the research objective regards a quite large class of digital and/or logistics networks that share common properties even though they have huge intrinsic differences. In other words, besides AGVs that can be treated as a kind of internal transport, other emerging trends concerning the logistics (e.g., supply chains management) and city traffic (e.g., infrastructure of the public transport) issues can be modeled. For instance, the relevant multimodal processes of passengers traveling between destination points in an environment of local processes encompassing the subway lines network might be considered as well. In other words, the passenger’s itinerary including different metro lines can be considered as a plan of a multimodal process routing within a metro network.The proposed declarative approach aimed at AGVs fleet scheduling stated in terms of constraint satisfaction problem representation provides a unified method for performance evaluation of local as well as supported by them multimodal processes.In general case, however, there is not any guarantee that the considered SCCP model of AGVS has a nonempty cyclic steady states space as well as that in case this space is not empty, any direct or indirect mutual reachability can be observed. That means that the decidability of the problem of the space𝒫 reachability and mutual reachability among its cyclic steady states plays a pivotal role in multimodal processes rescheduling.



---

*Source: 407096-2013-12-17.xml*