(PDF) Iterative multimodal processes scheduling - DOKUMEN.TIPS (2024)

Annual Reviews in Control 38 (2014) 113–122

Contents lists available at ScienceDirect

Annual Reviews in Control

journal homepage: www.elsevier .com/ locate /arcontrol

Iterative multimodal processes scheduling

http://dx.doi.org/10.1016/j.arcontrol.2014.03.0111367-5788/� 2014 Elsevier Ltd. All rights reserved.

⇑ Corresponding author.E-mail addresses: [emailprotected] (G. Bocewicz), izabela@m-tech.

aau.dk (I. Nielsen), [emailprotected] (Z. Banaszak).

Grzegorz Bocewicz a,⇑, Izabela Nielsen b, Zbigniew Banaszak c

a Department of Computer Science and Management, Koszalin University of Technology, Sniadeckich 2, 75-453 Koszalin, Polandb Department of Mechanical and Manufacturing Engineering, Aalborg University, Aalborg East, Denmarkc Department of Business Informatics, Warsaw University of Technology, Narbutta 85, 02-524 Warsaw, Poland

a r t i c l e i n f o

Article history:Received 14 January 2014Accepted 17 March 2014Available online 16 April 2014

a b s t r a c t

The paper considers the problem of Automated Guided Vehicles (AGVs) fleet scheduling subject to theright match-up of local cyclic acting AGV schedules to given workpiece machining schedules. The maincontribution of this work is the solution to a constraint satisfaction problem aimed at AGVs fleet match-up scheduling while taking into consideration assumed itineraries of concurrently manufactured producttypes. In other words, assuming a given layout of FMS’s material handling and production routes ofsimultaneously manufactured work orders as well as cyclic schedules of concurrently manufacturedproduct types, the goal is to provide a declarative model enabling multimodal processes, i.e. employingAGVs, hoists, lifts, etc. demand-responsible scheduling of transportation/handling services. An algebra-like driven approach to cyclic scheduling based on step-by-step composition of multimodal transporta-tion network sub-structures is proposed. Results of computational experiments assessing scalability ofthe method provided are presented as well.

� 2014 Elsevier Ltd. All rights reserved.

1. Introduction

Design and operational issues arising in an Automated GuidedVehicles (AGVs) served Flexible Manufacturing System (FMS)(Trouillet, Korbaa, & Gentina, 2007) when deciding on how toachieve a desired system performance are usually hard to deter-mine and evaluate (Song & Lee, 1998; Wang, Yang, & Zhang,2007). The problems concerning material transportation routingand scheduling belong to NP-hard ones (Fazlollahtabar &Saidi-Mehrabad, 2013; Levner, Kats, Alcaide, Pablo, & Cheng,2010). Since, most processes observed in steady state manufactur-ing are periodic reoccurring, cyclic schedules, and following this,cyclic scheduling methods can be considered. This kind of repre-sentation (illustrating execution of each operations) enable toshow which behaviors (consisting of many cyclic concurrentthreads corresponding with routes of AGVs, routes of transportedwork pieces, etc.) can exist in any given structure (limited by thenumber of resources and their capacities). Since cyclic schedulesencompass repetitive character of manufacturing processes thecyclic processes modeling approach seems to be a reasonable per-spective (Bocewicz & Banaszak, 2013; Levner et al., 2010; Liebchen& Möhring, 2002; Von Kampmeyer, 2006). In that context, ourcontribution provides a discussion of some solubility issues

concerning solvability of the cyclic processes scheduling in onlinemode enabling to avoid exhaustive searching, however at the costof losing of some admissible solutions.

Many models and methods have been considered to date(Levner et al., 2010). Among them the mathematical programmingapproach (Von Kampmeyer, 2006), Petri Nets (Holloway, Krogh, &Giua, 1997; Li, Liu, Hanisch, & Zhou, 2012; Song & Lee, 1998;Trouillet et al., 2007), and multi-agent systems (Bernaer, 2006)frameworks belong to the more frequently used. Most of theseare oriented at finding of a minimal cycle or maximal throughputwhile assuming deadlock-free processes flow. Alternative frame-works enabling analytical approaches to deadlock avoidance poli-cies implementation use the max-plus algebra (Polak, Majdzik,Banaszak, & Wójcik, 2004), and constraint logic programming(Bocewicz & Banaszak, 2013).

The last of above mentioned frameworks seems to be well sui-ted for AGVs fleet cyclic scheduling subject to assumed itinerariesof concurrently manufactured product types (Bocewicz, Nielsen, &Banaszak, 2013). In that context, our contribution can be seen as itssignificant extension while taking into account schedules of con-currently manufactured product types and stream-like flows ofa*gVs along the same cyclic transportation route. Then its goal isto propose a declarative framework aimed at refinement and pro-totyping of the cyclic steady states for both: concurrently executedlocal cyclic processes (encompassing AGVs activity) and concur-rently executed multimodal processes (encompassing concurrentflows of multi-product manufacturing). The following question is

114 G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122

the main focus of the research: Can the assumed AGVs fleet assign-ment reach its goal subject to constraints assumed on concurrentmulti-product manufacturing at hand? For all practical purposesthe above question remains unsolved due to its complexity. Thisis especially problematic as many manufacturing companies wouldstand to reap considerable rewards through better fleet assignmentand scheduling. The presented approach addresses this throughsolving the step-by-step elementary constraint satisfaction prob-lems (CSPs) instead of solving of a CSP as an elementary CSPscomposition.

The rest of the paper is organized as follows: In Section 2, anillustrative example of a AGV system and its System of ConcurrentlyFlowing Cyclic Processes (SCCPs) model as well as routing andscheduling of multimodal processes in the context of SCCP is pre-sented. Section 3 provides a AGVs fleet scheduling problem formu-lated in terms of a declarative modeling framework. Then aniterative scheduling method formulated in terms of CSP aimed atsolution of provided problem is considered in Section 4. Illustrativeexample of the proposed approach is discussed in Section 5, and re-sults of numerical experiments assessing its scalability are de-scribed in Section 6. Concluding remarks are presented in Section 7.

2. Multimodal processes

The material handling system of the FMS layout shown inFig. 1a, encompassing the network of AGVs periodically circulatingalong cyclic routes can be modeled in terms of SCCPs shown inFig. 1b. Consider four local cyclic processes: P1, P2, P3, P4 and theirstreams: P1

1, P21, P1

2, P13, P2

3, P14, associated with the operation of six

AGVs, and two multimodal processes mP1, mP2 representingtwo products production routes (Bielli, Boulmakoul, & Mouncif,2006; Zografos & Androutsopoulos, 2008). The processes are exe-cuted along given routes composed of ten resources associatedwith eight workstations (resources R1, R9 and R6, R10 are treatedas input/output buffers of workstations R1=9 and R1=6, respectively):R ¼ fR1;R2; . . . ;R10g.

(a)

(b)

Fig. 1. An AGV system (a) and it’s SCCP representation (b).

Distinguished, local P and multimodal mP processes are definedin the following way:

� P = {Pi|i = 1, ..., n} – the set of local processes described bysequences of operations executed on resources R, whereeach Pi is specified by the set of streams: Pi ¼

P1i ; P

2i ; . . . ; Pk

i ; . . . ; PlsðiÞi

n o,

� mP = {mPi|i = 1, ..., w} – the set of multimodal processesdescribed by sequences of some sub-sequences from local pro-cesses P, where each mPi is specified by the set of streams:

mPi ¼ mP1i ;mP2

i ; . . . ;mPki ; . . . ;mPlmsðiÞ

i

n o.

Taking into account pipeline flows of streams of local andmultimodal processes can be seen as a meaningful extensionof our earlier work (Bocewicz et al., 2013) allowing one to ana-lyse admissible cyclic steady states of serial manufacturing ofdifferent products. The operations of multimodal process’sstreams require execution of some local processes. For example,transport operations between resources in mP1 (Fig. 1b) requirestreams of local processes P1, P2, P3, respectively. This meansthe routes of multimodal process are also determined by subse-quences of routes of the local processes through which theyhave to be processed. Note that the resources belonging tothese routes are simultaneously shared by both local andmultimodal processes.

Moreover, it is assumed that both kind of processes are cyclicand act concurrently. Local processes are synchronized by a mutualexclusion protocol, i.e. guaranteeing the only one process simulta-neously can be executed on a shared resource. However, that con-straint does not concern the multimodal processes.

2.1. Structure

In order to describe the system shown in Fig. 1b let us introducethe notations (Bocewicz & Banaszak, 2013):

� pki ¼ ðpk

i;1; pki;2; . . . ; pk

i;j; . . . ; pki;lrðiÞÞ specifies the route of the stream

of a local process Pki (the k-th stream of the i-th local process

Pi), and its components define the resources used in course ofprocess operations execution, where pk

i;j 2 R, R = {R1, R2, ... ,Rc, ... , Rm} – denotes the set of resources used for the j-th oper-ation in the k-th stream of the i-th local process; in the rest ofthe paper, the j-th operation executed on the resource pk

i;j in

the stream Pki will be denoted by ok

i;j; lr(i) – is the length ofthe cyclic process route (all streams of Pi are of the samelength). For example, in the SCCP from Fig. 1 the routes ofstreams of processes P1, P2, P3 and P4 (e.g. AGVS), are definedby the following sequences: p1

1 ¼ ðR1;R3;R2;R9Þ, (i.e. the AGV

P11 moves along the workstations R1, R3, R2, R9), p2

1 ¼ðR9;R1;R3;R2Þ, p1

2 ¼ ðR3;R5;R4Þ, p13 ¼ ðR7;R8;R2;R4Þ, p2

3 ¼ðR8;R2;R4;R7Þ, P1

4 = (R6, R10, R7, R5).� tk

i ¼ ðtki;1; t

ki;2; . . . ; tk

i;j; . . . ; tki;lrðiÞÞ – specifies the i-th processopera-

tion times, where tki;j denotes the time of execution of the j-th

operation oki;j in the stream Pk

i . In the case of the system from

Fig. 1a time tki;j consists of transportation, load/unload and

processing time of a workpiece.� xk

i;jðlÞ 2 N – the timing of commencement of the operation oki;j in

the l-th cycle,� mpk

i ¼ ðmprq1i1ðai1 ; bi1 Þ_ mprq2

i2ðai2 ; bi2 Þ_ . . . _ mpr

qy

iyðaiy ; biy ÞÞ –

specifies the route of the stream mPki from the multimodal

process mPi (the k-th stream of the i-th multimodal processmPi), where

G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122 115

mprqi ða; bÞ ¼

ðpqi;a;p

qi;aþ1; . . . ;pq

i;bÞ a 6 b

ðpqi;a;p

qi;aþ1 . . . ; pq

i;lrðiÞ;pqi;1; . . . ;pq

i;b�1;pqi;bÞ a > b

(

a, be{1, 2, . . . , lr(i)}, u _ v – concatenation of sequences u and v. Ifu = (u1, . . . , ua), v = (v1, . . . , vb) and ua = v1 then u _ v = (u1, . . . , ua,v2, . . . , vb).

The route mpki is a sequence of sections of local streams routes

pqi and determines the production routestaking into account trans-

portation means (e.g., AGVs). In the considered case, the streams ofmultimodal processes mP1, mP2 (Fig. 1b) are specified by thefollowing sequences: mpk

1 ¼ ððR1;R3Þ_ ðR3;R5Þ_ ðR5;R6ÞÞ ¼ðR1;R3;R5;R6Þ, mpk

2 ¼ ðR10;R7;R8;R2;R9Þ, being the concatenationof p2

1, p12, p1

4 and of p14, p1

3, p11 subsequences, respectively. In the rest

of the paper, the j-th operation of the stream mPki will be denoted

by moki;j. All operation times mtk

i;j of multimodal processes are thesame as relevant operations’ in local processes.

� mxki;jðlÞ 2 N– the timing of commencement of operation mok

i;j inthe l-th cycle,� H = {r1, r2, ..., rc, . . . , rm} – is the set of the priority dispatching

rules, where rc = (sc,1, ..., sc,j, ... , sc,lp(k)) is the sequence compo-nents of which determine an order in which the streams ofprocesses can be executed on the resource Rc, sk;j 2

Sni¼1Pi.

Dispatching rules which determine access order in whichvehicles share resources, (R1, R2, ... , R10) are following: r1 ¼ðP1

1; P21Þ,r2 ¼ ðP2

3; P11; P

22; P

13Þ, r3 ¼ ðP1

2; P11; P

21Þ, r4 ¼ ðP2

3; P12; P

13Þ,

r5 ¼ ðP14; P

12Þ, r6 ¼ ðP1

4Þ, r7 ¼ ðP14; P

13; P

23Þ, r8 ¼ ðP2

3; P13Þ, r9 ¼

ðP21; P

11Þ, r10 ¼ ðP1

4Þ.

Therefore the SCCP can be defined as the pair:

SC ¼ ððR; SLÞ; SMÞ ð1Þ

where R = {R1, R2, ... , Rk, ... , Rm} – the set of resources,SL = (P, U, T, H) – characterizes the structure of local processes

of SCCP, i.e. P = {P1, P2, . . . , Pn} – the set of local processes,

Pi ¼ fP1i ; P

2i ; . . . ; PlsðiÞ

i g – the set of streams belonging to the

process Pi, U ¼ fp11; . . . ; plsð1Þ

1 ; . . . ; p1n; . . . ; plsðnÞ

n g – the set of local pro-

cess routes, T ¼ ft11; . . . ; tlsð1Þ

1 ; . . . ; t1n; . . . ; tlsðnÞ

n g – the set of localprocess operations times, H = {r1, r2, . . . , rm} – the set of dispatch-ing priority rules.

SM = (mP, mP, mT) – characterizes the structure of multimodalprocesses of SCCP, i.e. mP = {mP1, mP2, . . . , mPw} – the set of multi-

modal processes, mPi ¼ fmP1i ;mP2

i ; . . . ;mPlmsðiÞi g – the set of streams

belonging to the process Pi, M = {mp1, mp2, . . . , mpi, ... , mpw} – theset of multimodal process routes, mT ¼ fmt1

1; . . . ;mtlsmð1Þw ; . . . ;

mt1w; . . . ;mtlsmðnÞ

w g – the set of local process operation times.The main question concerns of SCCP cyclic behavior and the

way this behavior depends on local U and multimodal routes M,the set of priority rules H etc.

2.2. Cyclic behavior

The SC model emphasizes structural characteristics of the SCCPmodeled. Due to deadlock occurrence caused by the condition ofmutual exclusion, not every behavior of SCCP are allowed in thesekind of structures. The behavioral characteristics guaranteeingdeadlock-free execution of processes can be specified in terms ofthe admissible states reachability concept, i.e. either driven byboth cyclic steady states and leading to transient states (Bocewicz,Nielsen, Banaszak, & Dang, 2012) or by the cyclic steady state spaceonly (Bocewicz & Banaszak, 2013). The second way, which does nottake into account the initial states leading through the transientstates to the cyclic steady states, seems to be quite close to the

cyclic scheduling methods widely used in many real-life cases(Von Kampmeyer, 2006).

In that context the relevant two-level cyclic schedule XSC

encompassing the SCCP behavior on each of its processes level,i.e. local SL and multimodal SM processes, can be defined asfollows:

XSC ¼ ððX;aÞ; ðmX;maÞÞ ð2Þ

where (X, a)/(mX, ma) – the sequence of operations beginning andperiod of local/multimodal processes executions.

It should also be noted, that the schedule XSC can be defined as asequence of ordered pairs describing behaviors of local (X, a) and

multimodal (mX, ma) processes, where X ¼ fx11;1; . . . ; xlsð1Þ

1;lrð1Þ;

x12;1; . . . ; xlsð2Þ

2;lrð2Þ; . . . ; x1n;1 . . . :; xlsðnÞ

n;lrðnÞg is a set of timings xki;j (for l = 0-th

cycle) of commencement of operations oki;j from the stream Pk

i . By

analogy, the set mX ¼ fmx11;1; . . . ;mxlmsð1Þ

1;lmð1Þ; . . . ;mx1w;1 . . . :;mxlmsðnÞ

w;lmðnÞgconsists of the timing of commencement of multimodal processesoperations, where w – the number of multimodal processes, andlm(i) – the number of operations in the i-th multimodal process(the all streams of mPi are of the same length).

Variables xki;j=mxk

i;j 2 Z describe the timing of commencement ofoperations in the l-th cycle of the SCCP cyclic steady state behavior:xk

i;jðlÞ ¼ xki;j þ l � a=mxk

i;jðlÞ ¼ mxki;j þ l �ma. Since values of xk

i;j=mxki;j

follow from the system structure, the cyclic behavior XSC of SCCPis determined by its structure SC. Moreover, the multimodalprocesses behavior (mX, ma) also depends on the local cyclicprocesses behavior (X, a).

In the general case, besides the structural characteristics ofSCCP the values of considered variables xk

i;j depend on the con-straints imposed by the mutual exclusion protocol, i.e. the set ofpriority dispatching rules H , and operation times, etc. (Bocewicz& Banaszak, 2013) as well as on the way the local and multimodalprocesses interact with each other. For example, in case of the twolevels’ structure model, i.e. including levels SL and SM, the con-straints determining xk

i;j=mxki;j can be expressed by the following

rules (Bocewicz & Banaszak, 2013):

� for local processes: the timing of commencement of operationok

i;j states for a maximum of both: the completion time of theoperation ok

i;j�1 preceding oki;j, and the release time of the

resource pki;j awaiting for ok

i;j execution:

moment of operation oki;jbegining

¼ maxfðmoment of pki;j releaseþ lag time DtÞ;

ðmoment of operation oki;j�1completionÞ

i ¼ 1; . . . ;n; j ¼ 1; . . . ; lrðiÞ; k ¼ 1; . . . ; lsðiÞ; ð3Þ

� for multimodal processes (assuming the different multimodalprocesses can be simultaneously processed on the same sharedresource): the timing of commencement of operation mok

i;j

(determined by the set X ki;j of values mxk

i;j) is equal to the nearest

admissible the completion time of operation moki;j�1 preceding

moki;j.

moment of operationmoki;j begining

¼ dmoment of operationmoki;j�1completioneXk

i;j;

i ¼ 1; . . . ;w; j ¼ 1; . . . ; lmðiÞ; k ¼ 1; . . . ; lsmðiÞ; ð4Þ

where X k

i;j ¼ fxca;bðlÞjxc

a;bðlÞ ¼ xca;b þ l � a; l 2 Zg – the set of admissible

values of mxki;j determined by value of xk

a;b, where xka;b – the timing of

commencement of operation oa,b enabling execution of the opera-tion mok

i;j, [aB] – the smallest integer greater than or equal to a interms of the set B: [aB] = min{k e B: k P a}.

116 G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122

Constraints (3) and (4) describe the relations guaranteeing cyc-lic execution of all operations from the structure SC. In this contextthey play a role of sufficient conditions guaranteeing the SCCP’scyclic behavior.

3. Problem statement

Most problems stated within a SCCP context concern relation-ships among its structure SC. and the behavior of XSC. Therefore,let us consider the SCCP specified (due to (1)) by the given setsof resources R, dispatching rules H, local U, and multimodal pro-cess routes mU, as well. Usually the main question concerns SCCPcyclic behavior, i.e. does there exist a cyclic (collision and deadlockfree) schedule XSC or SCCP structure i.e.: which dispatching rules Hguarantee a given periodicity (in local and multimodal processessense)?

In that context two main kinds of problem are considered:

– ‘‘Direct’’ problem:

given are: the model (1) specifying the structure of the SCCP bythe set of resources R, the sets of routes U and M, the operationtimes T and mT, the sets of priority dispatching rules H. Moreovergiven is the set of constraints (3) and (4) determining the cyclicschedule XSC encompassing the SCCP behavior.

The response to the following question is sought: Are both localand multimodal processes cyclic?

– ‘‘Reverse’’ problem:

given are: the model (1) specifying the structure of the SCCP bythe set of resources R, the sets of routes U and M, the set of prioritydispatching rules H. Moreover given is the set of constraints (3)and (4) determining the cyclic schedule Xlp encompassing the SCCPbehavior.

The response to the following question is sought: What operationtimes T, mT and dispatching rules H guarantee periodicity of localand multimodal processes?

The cases regarding the ‘‘Direct’’ problem formulation havebeen discussed in detail in (Bocewicz et al., 2012). The ‘‘reverse’’problem formulation has also many practical applications, for in-stance, concerning searching for structural parameters guarantee-ing required behavioral characteristics. In the considered case, seeFig. 1, searching for transportation operation times and dispatchingrules guaranteeing cyclic steady state behavior of the SCCP statesfor such an example.

The obtained dispatching rules and determined by them sys-tem’s behavior can be seen as a distributed control procedure pro-vided to the spatially distributed common shared resources whileimposing the right initial process allocations. This kind of controlprocedures can then be directly implemented in SCADA systemsthat tie together decentralized facilities such as shared by techno-logical processes AGVs and machine tools.

In the general case, the considered problems belong to NP-hardones and methods aimed at their solution cannot cope with real-life sized cases (Levner et al., 2010; Sitek & Wikarek, 2008). How-ever, an alternative approach, assuming decomposition of struc-ture SC can be proposed as well.

4. Iterative approach to scheduling

Searching for operation times T, mT and dispatching priorityrules H (reverse problem) boils down to the following constraintsatisfaction problem.

CSXTH ¼ ððfXSC ; TSC ;Hg; fDX ;DT ;DHgÞ; fCLðHÞ;CMgÞ ð5Þ

where XSC, TSC, H – decision variables, XSC – cyclic schedule (2), TSC –sequence of operation times: TSC = (T, mT) (where T, mT are definedin (1)),

DX, DT, DH – domains determining admissible value of decisionvariables: DX : mxk

i;j, xki;j 2 Z; ma, a 2 N; DT : mtk

i;j, tki;j 2 N,

{CL(H), CM} – the set of constraints CL(H) and CM describingSCCP behavior, CL(H) – constraints determining cyclic steady stateof local processes, i.e. their cyclic schedule, (since constraints CL(H)depend on dispatching rules H, hence they can be modified alongthe searching process due to the subsequent changes of H); CM –constraints determining multimodal processes behavior. Of course,the constraints CL(H), CM follow (3), (4).

Values of the variables XSC, TSC, H following constraints CL(H),CM are treated as solution to the problem CSXTH. That means thestructure parameters SC (TSC, H) solving the problem (5) guaranteecyclic steady state behavior of local and multimodal processes XSC

follows (3) and (4)).The standard constraints programming driven software plat-

forms such as ILOG, OzMozart, ECLiPSE can be used for solving(5). However, because of the combinatorial explosion of possiblevariants of parameters TSC, H values and constraints CL(H) depen-dence on H, their straight usage is restricted to small cases veryseldom occurring in practice.

In order to cope with the complexity of problem (5) let usconsider its decomposition into sub-problems CSXTH

i . Note thatthe structure SC (1) can be decomposed into the setofsubstructures S ¼ fSC1; SC2; . . . ; SCi; . . . ; SCzg of sub-structuresSCi = ((Rci, SLi), SMi), where Rci � R – the subset of the set R, SLi =(Pci, Ui, Ti, Hi) – the local processes structure (defined by analogyto (1)), SMi = (mPci, Mpi, mTi) – multimodal processes structure(mPci is treated as a set of multimodal process parts); if thefollowing conditions hold:

� the set S includes the all resources from the set R :Sz

i¼1Rci ¼ R;some resources can be shared by different substructures,� the set S includes the all local (multimodal) processes:Sz

i¼1Ui ¼ UðSz

i¼1Mpi ¼ MÞ, however each particular process orits part belongs to a unique substructure only:

Qzi¼1Ui ¼ ;,

(Qz

i¼1Mpi ¼ ;),� the set S includes the all priority rules.

Szi¼1Hi ¼ H:

� Therefore, the structure SC can be seen as the following compo-sition of the S sub-structures:

SC ¼ ðððSC1 � SC2Þ � SC3Þ � � � � � SCzÞ ð6Þ

where SCa � SCb = SCc and, SCc = ((Rcc, SLc), SMc), elements of SCc arefollowed:

Rcc ¼ Rca [ Rcb; Pcc ¼ Pca [ Pcb; Uc ¼ Ua [ Ub;

Hc = Ha [Hb; mPcc – the set including all parts of multimodalprocesses from the sets mPca and mPcb.Mc – the set of routes ofmultimodal process’s parts mPcc.

An example of the SCCP structure (from Fig. 1b) decompositionis presented in Fig. 2. Each sub-structure SC1, SC2, SC3, SC4 containsonly one local process and one or two parts of multimodalprocesses.

Let us note, that each sub-structure SCi generates thesub-problem CSXTH

i following (5), the solution of which providesparameters guaranteeing cyclic execution of its constituentprocesses. Therefore, the composition of sub-structures SCi leadsto the coupling of corresponding sub-problems CSXTH

i :

CSXTH ¼ ðððCSXTH1

_þCSXTH2 Þ _þCSXTH

3 Þ _þ � � � _þCSXTHz Þ ð7Þ

where CSXTHa

_þCSXTHb ¼ CSXTH

c , and in case:

CSXTHa ¼ ððfXSC

a ; TSCa ;Hag; fDX ;DT ;DHgÞ; fCLðHaÞ;CMgÞ

Fig. 2. Decomposition of the structure from Fig. 1(b).

(a)

(b)

Fig. 3. The schedules of collision-free execution of local processes on the commonshared resource Rci

: the execution of the operation oki;j between the subsequent

performances osq;r (a), execution of the operation os

q;r between the subsequentperformances ok

i;j (b).

G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122 117

CSXTHb ¼ ððfXSC

b ; TSCb ;Hbg; fDX ;DT ;DHgÞ; fCLðHbÞ;CMgÞ

the CSXTHc has following form:

CSXTHc ¼ ððfXSC

c ; TSCc ;Hcg; fDX ;DT ;DHgÞ; fCLðHcÞ;CM; CDgÞ

XSCc ¼ ððX

SCc ;acÞ; ðmXSC

c ;macÞÞ;XSCc ¼ XSC

a [ XSCb ;

mXSCc ¼ mXSC

a [mXSCb ;ac ¼maxfaa;abg; mac ¼maxfmaa;mabg;

TSCc ¼ TSC

a [ TSCb ;mTSC

a [mTSCb

� �; Hc ¼ Ha [Hb:

In order to guarantee the solution of the following couplingCSXTH

a_þCSXTH

b results in cyclic steady state behavior the additionalconstraints CD have to be satisfied.

The idea standing behind of the constraints CD expressed interms of sub-structures SCa, SCb assumes that cyclic schedulesXSC

a , XSCb , corresponding to CSXTH

a and CSXTHb solutions are collision-

free at resources coupling considered sub-structures.In the SCCP modeled by the structure SCd = SCa � SCb, the cyclic

schedule XSCd is reachable if the following conditions hold:

(a) the value of the period aa of the schedule Xa is a total multi-ple of the period ab of schedule Xb:

aaMODab ¼ 0 ð8Þ

(b) operations executed on common shared resourcesRk ¼ Rpa _ Rpb ¼ fRk1 ; . . . ;Rci

; . . . ;Rcqg are performed inmutual exclusion mode, i.e. within cyclically repeatable timewindows of schedules XSC

a , XSCb .

The two local operations oki;j, os

q;r are performed in mutual exclu-sion mode (on the common shared resource Rci

) if the operation oki;j

begins (moment xki;j) after the release (with the delay Dt) of the

resource by the operation osq;r (moment xs

q;r� of the subsequent

operation initiation) and releases the resource (moment xki;j� of

the subsequent operation initiation) before the beginning of thenext execution of the operation os

q;r (moment xsq;r þ ab). Such a

synchronization mechanism guaranteeing time windows of non-overlapping operations performed on common shared resourceRci

can be treated as an extension of the constraints given in(Von Kampmeyer, 2006). The situation considered is shown inFig. 3a. The collision-free execution (coherent with Fig. 3) of thelocal process operations is possible if the constraint below issatisfied:

xki;j P xs

q;r� þ h00 � ab þ Dt� �

^ xki;j� þ h0 � aa þ Dt 6 xs

q;r þ ab

� �h i_ xs

q;r P xki;j� þ h0 � aa þ Dt

� �^ xs

q;r� þ h00 � ab þ Dt 6 xki;j þ aa

� �h ið9Þ

where Rci2 Rk,

r� ¼jþ 1 when jþ 1 6 lrðiÞ

1 when jþ 1 > lrðiÞ

�; r� ¼

rþ 1 when rþ 1 6 lrðqÞ1 when rþ 1 > lrðqÞ

�

h0 ¼0 when jþ 1 6 lrðiÞ1 when jþ 1 > lrðiÞ

�; h00 ¼

0 when r þ 1 6 lrðqÞ1 when r þ 1 > lrðqÞ

�

aa/ab – the period of the schedule Xa/Xb; lr(i)/lr(q) – length of

stream’s route Pki =Ps

q;xki;j=xs

q;r – the moment of the operation oki;j=os

q;r

initiation in the structure SCa/SCb; xki;j� xs

q;r� – moment of initiation

of operation executed after oki;j=os

q;r .Therefore, in case constraint (9) holds operations from local

processes executed on each common shared resource Rci2 Rk of

composed substructures SCa, SCb are performed alternately, i.e.they pass each other.

5. Numerical experiment

Consider SCCP from Fig. 1b modeling the system from Fig. 1aand described by:

� the set of resources: R = {R1, R2, ... , R7},� the set of local process’s stream routes: p1

1 ¼ ðR1;R3;R2;R9Þ,p2

1 ¼ ðR9;R1;R3;R2Þ, p12 ¼ ðR3;R5;R4Þ, p1

3 ¼ ðR7;R8;R2;R4Þ, p23 ¼

ðR8;R2;R4;R7Þ, p14 ¼ ðR6;R10;R7;R5Þ.

� the set of multimodal process routes: mpk1 ¼ ðR1;R3;R5;R6Þ,

mpk2 ¼ ðR10;R7;R8;R2;R9Þ. Required production cycle times asso-

ciated to mP1 and mP2 are the same and equal to a = 11 t.u.Assumed moments of first operations beginning in processesmP1 and mP2 are given by following formulas:

mxi1;1 2 fmxi

1;1ðlÞjmxi1;1ðlÞ ¼ 10þ l � a; l 2 Zg

mxi2;1 2 fmxi

2;1ðlÞjmxi2;1ðlÞ ¼ 8þ l � a; l 2 Zg

A response to the following question is sought: What values ofoperation times T, mT and priority dispatching rules H guaranteeperiodicity of local and multimodal processes?

(a)

(b)

Fig. 4. Illustration of structures composition and coupling of corresponding to them constraint satisfaction problems: SC1 � SC2 (a). (SC1 � SC2) � SC3 (b).

118 G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122

Due to the above proposed iterative approach the structure SC(see Fig. 1b) has to be decomposed into four sub-structures:S ¼ fSC1; SC2; SC3; SC4g (see Fig. 2).

That means the relevant problem CSXTH (5) can also bedecomposed into four sub-problems, associated to the relevantsub-structures SC1, SC2, SC3, SC4:

CSXTH ¼ CSXTH1

_þCSXTH2

� �_þCSXTH

3

� �_þCSXTH

4

� �ð10Þ

Solution to the CSXTH can be obtained through subsequent resolu-tions of sub-problems CSXTH

a_þCSXTH

b seen as subsequent sub-prob-lems coupling. Let us assume a backtracking-free searchingstrategy. This means the solution to the problem CSXTH

1_þCSXTH

2 issought at first. The relevant illustration is shown in Fig. 4a. As a re-sult the Gantt chart (values T, mT and XSC are known), representingcyclic execution of processes P1, P2, was obtained. In turn, the fol-lowing problem ðCSXTH

1_þCSXTH

2 Þ _þCSXTH3 is considered.

Fig. 5. Gantt’s chart of cyclic schedule of local and multimodal processes from SCCPshown in Fig. 1(b).

Table 1The process operation time sti,j and dispatching rules of SCCP from Fig. 1.

i, j tji;1 tj

i;2 tji;3 tj

i;4

P11

1, 1 1 1 1 1

P21

1, 2 1 1 1 1

P12

2, 1 5 3 3 –

P13

3, 1 1 6 1 3

P23

3, 2 1 1 1 1

P14

4, 1 1 8 1 1

H H

r1 P11; P2

1r7 P1

4; P13; P2

3

r2 P23; P1

1; P22; P1

3r8 P2

3; P13

r3 P12; P1

1; P21

r9 P21; P1

1

r 2 1 1 r 1

G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122 119

The obtained solution is presented in Fig. 4b. In other words, atthis stage, the parameters of the subsequently composed sub-structure SC3 guaranteeing cyclic steady state behavior of thestructure ((SC1 � SC2) � SC3) for a given T12, mT12, H12, XSC

12 ofsub-structure (SC1 � SC2) are sought.

Repeating that scheme the final solution T, mT, H, XSC to theproblem (10) has been obtained in time below 1 s.

All stages have been implemented and computed in the con-straint programming environment – OzMozart system (Dual Core2.67, GHz, 2.0, GB RAM).

The Gantt chart of cyclic schedule XSC as corresponding values T,H (it is assumed that mT is the same as T) are shown in Fig. 5 andTable 1.

The obtained operations times T and dispatching priority rulesH result in the schedule XSC following of the all earlier assumedrequirements.

By the blue and red color lines the first stream of the multi-modal process mP1and the1 second stream of the multimodal pro-cess mP2 are distinguished, respectively (see Fig. 5). Theirillustration shows that assumed value of the cycle time holds andequals to 11 t.u. as well as beginnings of subsequent streams inmP1 and mP2 follow formulas mxi

1;1 ¼ 10þ l � 11 andmxi

2;1 ¼ 8þ l � 11, respectively. The resultant cyclic schedule regardsof two products processed along mP1 and three other kind of prod-ucts processed along mP2.

6. Structures composition

The methodology behind the proposed method is illustrated inFig. 6. Due to its main assumption the conditions sufficient for theSCCP periodicity have to be examined iteratively, i.e. in the course

1 For interpretation of color in Fig. 5, the reader is referred to the web version ofthis article.

of step-by-step composition of sub-structures contained in the setS. In other words, at each stage of subsequent SC reconstructionthe resultant operation times T, mT and priority dispatching rulesH has to be checked whether a cyclic behavior of the newly com-posed structure is guaranteed. Iterative structures composition(SC1 � SC2) � � � � � SCz corresponds to an iterative coupling ofconstraints satisfaction problems ðCSXTH

1_þCSXTH

2 Þ _þ � � � _þCSXTHz , i.e.

sub-problems SCi following relevant substructures CSXTHi . Solutions

to the problems denoted by Gð1Þj (see Fig. 6) can be seen as partialsolutions leading to the final solution of the problem CSXTH (5).

In the general case, each CSXTH has a set of admissible solutionsGð1Þj ;Gð2Þj ; � � � ;GðqjÞ

j ; in case the set is empty the following notation isused , see Fig. 6. That means that the final solution to the problemCSXTH (5) follows from the searching tree, see Fig. 6, where twosearch strategies can be considered: the backtracking (i.e. bruteforce search) strategy and greedy strategy. The result followingtree searching due to the back tracking strategy is distinguishedby the green color line (see Fig. 6), and the violet and orangecolor lines illustrate the results following from using the greedystrategy. It should be noted, that computational complexity ofthe backtracking search strategy implemented in the method ofsub-structures iterative composition has an exponential character,i.e. the same as in the case assuming jjSjj ¼ 1 (absence of SCdecomposition).

On the other hand, the polynomial computational complexity ofthe search strategy employed in the proposed method of iterativestructures coupling do not guarantee the final solution, see violetline in Fig. 6.

Let us note that the introduced operator � enablingsub-structures composition (6) assumes the same resources Rksplice. In the general case, allowing to consider other rules ofsub-structures composition the number of potential interstagesolutions GðiÞj may grow dramatically.

Unlike search-based methods treating similar issues whileassuming deadlock-free cases (Chaar & Hammadi, 2004; Yu & Lu,2010; Zhang, He, & Pan, 2010; Zidi & Maouche, 2006) our formaldeclarative programming based approach provide solutions ofguaranteed deadlock avoidance. Another advantage of theproposed approach follows from its scalability. The concept ofthe SCCP structure decomposition and then its step-by-stepreconstruction implemented into the cyclic scheduling procedureenables to decrease the required computation time dramatically.To show it let us consider three SCCP regular structures presentedin Fig. 7, and let us introduce an aggregation index g defined asfollows:

4 P3; P2; P3 10 P4

r5 P14; P1

2– –

r6 P14

– –

Fig. 6. Scheme of iterative structures composition.

(a)

(b)

Fig. 7. Example of SCCP structures specified by the same value of aggregation index g1 = g2 = g3 = 0.5 and different number of local processes operations LO1 = 9, LO2 = 12,LO3 = 15, (a) and their decompositions (b).

120 G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122

g ¼ LPðlpþ 1Þm ; g 2 ð0;1�; ð11Þ

where lp – the number of multimodal processes levels in SC, m – thenumber of resources of the structure SC, LP – the number ofprocesses realized in the structure SC.

So, the structures of the considered SCCPs have the same valuesof an aggregation index g1 = g2 = g3 = 0.5 but different value ofnumber operations LO1 = 9, LO2 = 12, LO3 = 15. The value of the

index significantly influences the time required for solution ofproblem (5), see Fig. 8a.

The illustration presenting the possibility of the solution timedecreasing, provided in Fig. 8b shows that problem (5) solved(for the SCCP structures specified by g = 0.5) without any structuredecomposition takes about 10 h and then can be solved requiringjust about 10 minutes while using four decompositions. Thepossible ways of decompositions of the regular structures areshown in Fig. 8b.

(a) (b)

Fig. 8. Time required for problem (5) resolution without the structure decomposition, for SCCP with g1 = 0.33, g2 = 0.5, g3 = 0.6 (a), for the SCCP specified by g1 = 0.5 whiletaking into account its decomposition into z = 4 substructures, z = 2 substructures and case z = 1 without any decomposition (Oz Mozart, Windows 7, Intel Core Duo23.00 GHz, 4 GB RAM) (b).

G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122 121

Such meaningful advantage follows from the greedy strategyemployed removing backtrackings from solution searching pro-cess. So, the cost that must be paid can be observed in Fig. 8bshowing nodes denoted as ‘‘no solution’’.

7. Concluding remarks

The SCCP structure decomposition enables to decompose theassociated CSP problem. Such observation enables, in turn, search-ing for SCCP cyclic behavior through coupling of elementary CSP(i.e. sub-problems corresponding to the substructures of SCCP)subject to the constraints CD, i.e. conditions sufficient for shufflingof composed cyclic schedules aimed at their mutual matching. Pro-posed greedy, backtracking-free searching strategy can omit somesufficient conditions, however at cost of faster solution of the con-sidered CSP.

The proposed declarative approach, aimed at AGVs fleet sched-uling stated in terms of constraint satisfaction problem representa-tion, provides a unified method for performance evaluation of localas well as supported by them multimodal processes.

The approach leads to solutions based on sufficient conditionsthat allow the designer to compose elementary systems in such away as to obtain the final AGVs scheduling system with requiredquantitative and qualitative behavior features. This provides astep towards a method allowing one to replace the exhaustivesearch for the admissible control by an iterative structuralfeature transportation system design guaranteeing its requiredbehavior.

Declarative modeling approach to refinement and prototypingof the cyclic steady states for both: concurrently executed localcyclic processes (encompassing AGVs activity) and concurrentlyexecuted multimodal processes (encompassing concurrent flowsof multi-product manufacturing) is proposed. However, in casethe considered production orders have to be changed or replacedby the new ones a problem of multimodal processes reschedulingarises.

This new problem addresses the possibility of smoothly chang-ing a system cyclic behavior, i.e. deciding about mutual reachabil-ity between possible (reachable) cyclic steady states. This kind ofpossibility boils down to the change of structure parameters. Thatmeans rescheduling problem can be seen as an instance of recon-figuration problem (Khalgui & Mosbahi, 2011; Khalgui, Mosbahi,Li, & Hanisch, 2011) which aims to find the structure parametersguaranteeing the change of given behaviors. The domain ofrescheduling problems determines our further researchperspective.

Acknowledgements

This work has partly been supported by the EC under 260026-TAPAS.

References

Bernaer, S. (2006). A multi agent system to control complexity in multi modaltransport. In Proceedings of the IEEE conf. on cybernetics and intelligent systems(pp. 1–6). Bangkok.

Bielli, M., Boulmakoul, A., & Mouncif, H. (2006). Object modeling and pathcomputation for multimodal travel systems. European Journal of OperationalResearch, 175(3), 1705–1730.

Bocewicz, G., & Banaszak, Z. (2013). Declarative approach to cyclic steady statesspace refinement: periodic processes scheduling. The International Journal ofAdvanced Manufacturing Technology, 67(1–4), 137–155.

Bocewicz, G., Nielsen, I., Banaszak, Z. (2013). Step-by-step cyclic processesscheduling. In M. Tsuzuki et al. (Eds.), Proceedings of 11th IFAC Workshop onIntelligent Manufacturing Systems (pp. 300–305). Sao Paulo.

Bocewicz, G., Nielsen, P., Banaszak, Z., & Dang, V. Q. (2012). Cyclic steady staterefinement: Multimodal processes perspective. Advances in productionmanagement systems, series: IFIP advances in information and communication(Vol. 384, pp. 18–27). Springer-Verlag.

Chaar, B. F., & Hammadi, S. (2004). Evolutionary approach to the regulation of thetraffic of a system of multimodal transport. Journal Européen des SystèmesAutomatisés, 38(7–8), 901–931.

Fazlollahtabar, H., & Saidi-Mehrabad, M. (2013). Methodologies to optimizeautomated guided vehicle scheduling and routing problems: A review study.Journal of Intelligent & Robotic Systems, 1–21. http://dx.doi.org/10.1007/s10846-013-0003-8.

Holloway, L. E., Krogh, B. H., & Giua, A. (1997). A survey of Petri net methods forcontrolled discrete event systems. Discrete Event Dynamic Systems, 7(2),151–190.

Khalgui, M., & Mosbahi, O. (2011). Formal approach for the development ofintelligent industrial control components. International Journal of ComputerApplications in Technology, 42, 84–107. No.2/3.

Khalgui, M., Mosbahi, O., Li, Z., & Hanisch, H.-M. (2011). Reconfigurable multiagentembedded control systems: From modeling to implementation. IEEETransactions on Computers, 60(4), 538–551.

Levner, E., Kats, V., Alcaide, D., Pablo, L., & Cheng, T. C. E. (2010). Complexity of cyclicscheduling problems: A state-of-the-art survey. Computers & IndustrialEngineering, 59(2), 352–361.

Li, Z. W., Liu, G. Y., Hanisch, H.-M., & Zhou, M. C. (2012). Deadlock prevention basedon structure reuse of petri net supervisors for flexible manufacturing systems.IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans,42(1), 178–191.

Liebchen, C., & Möhring, R. H. (2002). A case study in periodic timetabling. ElectronicNotes in Theoretical Computer Science, 66(6), 21–34.

Polak, M., Majdzik, P., Banaszak, Z., & Wójcik, R. (2004). The performance evaluationtool for automated prototyping of concurrent cyclic processes. FundamentaInformaticae, 60(1–4), 269–289.

Sitek, P., & Wikarek, J. (2008). A declarative framework for constrained searchproblems. In N. T. Nguyen et al. (Eds.). Lecture notes in artificial intelligence (vol.5027, pp. 728–737). Springer-Verlag.

Song, J.-S., & Lee, T.-E. (1998). Petri net modeling and scheduling for cyclic job shopswith blocking. Computers & Industrial Engineering, 34(2), 281–295.

Trouillet, B., Korbaa, O., & Gentina, J.-C. (2007). Formal approach for FMS cyclicscheduling. IEEE SMC Transactions, Part C, 37(1), 126–137.

122 G. Bocewicz et al. / Annual Reviews in Control 38 (2014) 113–122

Von Kampmeyer, T., (2006). Cyclic scheduling problems. In Ph.D. Dissertation,Fachbereich Mathematik/Informatik, Universität Osnabrück, German.

Wang, B., Yang, H., & Zhang, Z.-H. (2007). Research on the train operation plan of theBeijing–Tianjin intercity railway based on periodic train diagrams.TiedaoXuebao/Journal of the China Railway Society, 29(2), 8–13.

Yu, H., & Lu, F. (2010). A multi-modal route planning approach with an improvedgenetic algorithm. The International Archives of the Photogrammetry, RemoteSensing and Spatial Information Sciences, 38, 343–348.

Zhang, X., He, Z., & Pan, Y. (2010). Study on multimodal transport network modelbase on genetic algorithm method. ICLEM, 2010, 3514–3520.

Zidi, S., & Maouche, S. (2006). Ant colony optimization for the rescheduling ofmultimodal transport networks. IMACS Proceedings of Multiconference onComputational, Engineering in Systems Applications, 1, 965–971.

Zografos, K. G., & Androutsopoulos, K. N. (2008). Algorithms for itinerary planning inmultimodal transportation networks. IEEE Transactions on IntelligentTransportation Systems, 9(1), 175–184.

Grzegorz Bocewicz is Assistant Professor at the Department of Electronics andComputer Science of Koszalin University of Technology in Poland. He obtained M.Sc.degree in Telecommunications from the Koszalin University of Technology, Poland,and a Ph.D. degree in Computer Sciences from the Wrocław University of Tech-nology, Poland in 2006 and 2007, respectively. His research interests are in theareas of the operational research, modeling and design of decision support systems,methods of advanced planning and scheduling, constraints programming

techniques, modeling and analyzing of systems of concurrent cyclic processes. He isthe author and co-author over 100 manuscripts including three books, internationaljournals, and conference proceedings.

Izabela Nielsen is Associate Professor at the Department of Mechanical and Man-ufacturing Engineering at Aalborg University in Denmark. In 2005 she obtained aPh.D. with honors from Warsaw University of Technology (Faculty of ProductionEngineering). Her research includes project management, production planning,scheduling and optimization problems for which she has developed methods/models further implemented as diagnostic tools or decision support systems. She isa reviewer for a number of international journals and member of a number ofeditorial boards. She has published more than 80 peer-reviewed papers and bookchapters.

Zbigniew Banaszak obtained his Ph.D. degree in Robotics and Automation from theWrocław University of Technology, Poland, and a D.Sc. in Computer AidedEngineering at Welding Institute of the Ukrainian Academy of Sciences, Ukraine, in1977 and 1998, respectively. Currently he is employed by the Warsaw University ofTechnology where he is professor of Decision Support Systems Engineering. Z.Banaszak published over 400 manuscripts, including 18 books and text-books,with more than 300 ISI citations. His research interests are in the areas of thediscrete event systems theory, decision support systems, constraints programmingdriven planning and scheduling with application to multimodal supply chainnetworks.