# Multimodal Processes Rescheduling

Grzegorz Bocewicz, Zbigniew A. Banaszak, Peter Nielsen, Quang-Vinh Dang

► To cite this version:

Grzegorz Bocewicz, Zbigniew A. Banaszak, Peter Nielsen, Quang-Vinh Dang. Multimodal Processes Rescheduling. 19th Advances in Production Management Systems (APMS), Sep 2012, Rhodes, Greece. pp.534-541, 10.1007/978-3-642-40352-1_67. hal-01472288

HAL Id: hal-01472288

https://inria.hal.science/hal-01472288

Submitted on 20 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Multimodal processes rescheduling

Grzegorz Bocewicz¹, Zbigniew A. Banaszak², Peter Nielsen³, Quang-Vinh Dang³

¹Dept. of Electronics and Computer Science, Koszalin University of Technology, Poland,
e-mail: bocewicz@ie.tu.koszalin.pl

²Faculty of Management, Dept. of Business Informatics, Warsaw University of Technology,
Poland, e-mail: Z.Banaszak@wz.pw.edu.pl

³Dept. of Mechanical and Manufacturing Engineering, Aalborg University, Denmark, e-mail:
peter@m-tech.aau.dk; vinhise@m-tech.aau.dk

**Abstract.** Cyclic scheduling problems concerning multimodal processes are usually observed in FMSs producing multi-type parts where the Automated Guided Vehicles System (AGVS) plays a role of a material handling system. Schedulability analysis of concurrently flowing cyclic processes (SCCP) executed in these kinds of systems can be considered using a declarative modeling framework. Proposed representation provides a unified way for performance evaluation of local cyclic as well as supported by them multimodal processes. The main question regards of reachability of a SCCP cyclic behavior. In this context, the sufficient conditions guarantee the reachability of both local and multimodal processes cyclic steady state spaces are discussed.

# 1 INTRODUCTION

A cyclic schedule [1], [5] is one in which the same sequence of states is repeated over and over again. In everyday practice, cyclic scheduling arises in different application domains such as manufacturing, time-sharing of processors in embedded systems, and in compilers for scheduling loop operations for parallel or pipelined architectures as well as service domains covering such areas as workforce scheduling (e.g., shift scheduling, crew scheduling), timetabling (e.g., train timetabling, aircraft routing and scheduling), and reservations (e.g., reservations with or without slack,) [2], [7], [8]. In this paper, such cyclic scheduling problem considered follow from Flexible Manufacturing System (FMS) [3] and employed by them Automated Guided Vehicle (AGV) systems used for material handling. An AGVs provide asynchronous movement pallets of products through a network of guide paths between the workstations. Such flows following production routes are treated as multimodal processes, i.e. sequences of alternating transportation and machining operations. The problems arising concerning material transportation routing and scheduling belong to NP-hard ones. Since the steady state of production flows treated as multimodal processes has periodic character, hence servicing them AGV-served transportation processes (usually executed along loop-like routes) encompass also cyclic behavior.

Many models and methods have been proposed to solve the cyclic scheduling problem [6]. Among them, the mathematical programming approach (usually IP and
MIP), max-plus algebra [8], constraint logic programming [2], [10] evolutionary algo-
rithms and Petri nets [1] frameworks belong to the most frequently used. A majority
of them are oriented towards finding a minimal cycle or maximal throughput while
assuming deadlock-free processes flow.

In that context, our main contribution is to propose a new declarative modeling
based framework enabled to evaluate the cyclic steady state of a given system of con-
current cyclic processes as well as supported by them multimodal cyclic processes.
The following questions are of main interest: Does the assumed system behavior can
be achieved under the given system’s structure constraints? Does the assumed multi-
modal processes cyclic steady state is reachable from another one?

2 MULTIMODAL PROCESSES

Let us consider the above mentioned questions on in the context of Automated Guid-
ed Vehicles (AGVs) periodically circulating along cyclic routes (see Fig. 1b) that can
be seen as a network of loosely coupled material transportation/handling subsystem
modeled in terms of Systems of Cyclic Concurrent Processes (SCCPs) shown in Fig.
1a.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Illustration of the SCCP composed of four processes a) while modeling AGVs b).</figcaption></figure>

Four local *cyclic processes* [2] are considered: $P_1, P_2, P_3, P_4$ and *two multimodal processes* [3] (executed along the parts of local cyclic processes) $mP_1, mP_2$, respectively. $P_1, P_2$ contain two sub-processes $P_1 = \{P_1^1, P_1^2\}, P_2 = \{P_2^1, P_2^2\}$ representing AGVs moving along the same route. The AGVs are used to transport workpieces along transportation routes followed by $mP_1, mP_2$ processes, respectively (Fig 1. b).

**2.1 Declarative modeling**

The following notations are used [2]:
* $p_i^k = (p_{i,1}^k, p_{i,2}^k, ..., p_{i,lr(i)}^k)$ specifies the route of the local process's stream $P_i^k$ (k-th stream of the i-th local process $P_i$), and its components define the resources used in course of process operations execution, where: $p_{i,j}^k \in R$ (the set of resources: $R = \{R_1, R_2, ..., R_m\}$) - denotes the resource used by the k-th stream of i-th local process in the j-th operation; in the rest of the paper the j-th operation executed on resource $p_{i,j}^k$ in the stream $P_i^k$ will be denoted by $o_{i,j}^k$; $lr(i)$ - denotes a length of cyclic process route. $t_i^k = (t_{i,1}^k, t_{i,2}^k, ..., t_{i,lr(i)}^k)$ specifies the process operation times, where $t_{i,j}^k$ denotes the time of execution of operation $o_{i,j}^k$.

* $mp_i = (mpr_j(a_j, b_j), mpr_l(a_l, b_l), ..., mpr_h(a_h, b_h))$ specifies the route of the multimodal process $mP_i$, where: $mpr_j(a, b) = (crd_a p_j^k, crd_{a+1} p_j^k, ..., crd_b p_j^k)$, $crd_i D = d_i$, for $D = (d_1, d_2, ..., d_i, ..., d_w)$, $\forall a \in \{1, 2, ..., lr(i)\}$, $\forall j \in \{1, 2, ..., n\}$, $crd_a p_j \in R$. The transportation route $mp_i$ is a sequence of sub-sequences of local cyclic process routes. For example, a route of the process $mP_2$ (Fig. 1a) is following: $mp_2 = (R_3, R_4, R_5, R_6, R_1, R_8, R_{19}, R_{20}, R_{15}, R_{16}, R_{17})$.

* $\Theta = \{\sigma_1, \sigma_2, ..., \sigma_m\}$ is the set of the priority dispatching rules, where $\sigma_i = (s_{i,1}, ..., s_{i,lp(i)})$ is the sequence components of which determine an order in which the processes can be executed on the resource $R_i, s_{i,j} \in P$.

In that context a SCCP can be defined as a pair [2]:

$$SC = (SC_l, SC_m), \qquad (1)$$

where:

$$\begin{align*} SC_l &= (R, P, \Pi, T, \Theta) - \text{characterizes the SCCP structure, i.e.} \\ R &= \{R_1, R_2, ..., R_m\} - \text{the set of resources (e.g. the transportation sectors),} \\ P &= \{P_1^1, ..., P_1^a, ..., P_n^1, ..., P_n^z\} - \text{the set of local processes (e.g. AGVs),} \\ \Pi &= \{p_1, p_2, ..., p_n\} - \text{the set of local process routes (e.g. routes of AGVs),} \\ T &= \{T_1, ..., T_n\} - \text{the set of local process operations times,} \\ \Theta &= \{\sigma_1, \sigma_2, ..., \sigma_m\} - \text{the set of dispatching priority rules.} \end{align*}$$

$$\begin{align*} SC_m &= (MP, M\Pi) - \text{characterizes the SCCP behavior, i.e.} \\ MP &= \{mP_1, mP_2, ..., mP_u\} - \text{the set of multimodal processes, (workpieces),} \\ M\Pi &= \{mp_1, mp_2, ..., mp_u\} - \text{the set of multimodal process routes (transportation routes of materials).} \end{align*}$$

The main question concerns SCCP cyclic behavior and a way this behavior depends on direction of local transportation routes $\Pi$, the priority rules $\Theta$, and a set of initial states, i.e., an initial allocation of processes to the system resources.

## 2.2 Cyclic steady states space

Consider the following SCCPs state definition describing both the local and multimodal processes allocation:

$$S^k = (Sl^r, MA^k), \qquad (2)$$
where:

* $Sl^r$ – is the state of local processes, corresponding to $S^k$,

$$ Sl^r = (A^r, Z^r, Q^r), \qquad (3) $$

where: $A^r = (a_1^r, a_2^r, ..., a_m^r)$ – the processes allocation in the r-th state, $a_i^r \in P \cup \{\Delta\}$, $a_i = P_j^k$ – the i-th resource $R_i$ is occupied by the local stream $P_j^k$, and $a_i^r = \Delta$ – the i-th resource $R_i$ is unoccupied.

$Z^r = (z_1^r, z_2^r, ..., z_m^r)$ – the sequence of semaphores corresponding to the r-th state, $z_i^r \in P$ – means the name of the stream (specified in the i-th dispatching rule $\sigma_i$, allocated to the i-th resource) allowed to occupy the i-th resource; for instance $z_i^r = P_j^k$ means that at the moment stream $P_j^k$ is allowed to occupy the i-th resource.

$Q^r = (q_1^r, q_2^r, ..., q_m^r)$ – the sequence of semaphore indices, corresponding to the r-th state, $q_i^r$ determines the position of the semaphore $z_i^r$ in the priority dispatching rule $\sigma_i$, $z_i^r = crd(q_i^r)\sigma_i$, $q_i^r \in \mathbb{N}$. $MA^k$ – the sequence of multimodal processes allocation: $MA^k = (mA_1^k, ..., mA_u^k)$, $mA_i^k$ – allocation of the process $mP_i$, i.e.:

$$ mA_i^k = (ma_{i,1}^k, ma_{i,2}^k, ..., ma_{i,m}^k), \qquad (4) $$

where: $m$ – is a number of resources $R$, $ma_{i,j}^k \in \{mP_i, \Delta\}$, $ma_{i,j}^k = mP_i$ means, the j-th resource $R_j$ is occupied by the i-th multimodal process $P_i$, and $ma_{i,j}^k = \Delta$ – the i-th resource $R_j$ is released by the i-th multimodal process $P_i$.

The introduced concept of the k-th state $S^k$ is enabled to create a space $\mathbb{S}$ of feasible states [2]. In this kind of space $\mathbb{S}$ two kinds of behaviors can be considered: a **cyclic steady state** and a **deadlock state** [2].

The set $mSc^* = \{S^{k_1}, S^{k_2}, S^{k_3}, ..., S^{k_v}\}$, $mSc^* \subset \mathbb{S}$ is called a **reachability state space of multimodal processes** generated by an initial state $S^{k_1} \in \mathbb{S}$, if the following condition holds:

$$ S^{k_1} \xrightarrow{i-1} S^{k_i} \xrightarrow{v-i-1} S^{k_v} \rightarrow S^{k_i} \qquad (5) $$

where: $S^a \xrightarrow{i} S^b$ – the next state transition defined in [2], $S^{k_1} \xrightarrow{i} S^{k_{i+1}} \equiv S^{k_1} \rightarrow S^{k_2} \rightarrow S^{k_3} \rightarrow \dots \rightarrow S^{k_{i+1}}$ and $S^{k_i} \rightarrow S^{k_j}$ means transitions linking two feasible states $S^{k_i}, S^{k_j}$.

The set $mSc = \{S^{k_i}, S^{k_{i+1}}, ..., S^{k_v}\}$, $mSc \subseteq mSc^*$ is called a **cyclic steady state of multimodal processes** (i.e., the cyclic steady state of a SCCP) with the period $Tm = \|mSc\|$, $Tm > 1$. In other words, a **cyclic steady state** contains such a set of states in which starting from any distinguished state it is possible to reach the rest of states and finally reach this distinguished state again $S^{k_i} \xrightarrow{Tm} S^{k_i}$.

The cyclic steady state $Sc$ specified by the period $Tc$ of local processes execution is defined in the similar way. Graphically, the cyclic steady states $Sc$ and $mSc$ are described by cyclic and spiral digraphs, respectively. Two cyclic steady states of SCCP
from Fig. 1 a) are presented in Fig. 2. Moreover, since an initial state $S^{k_1} \in \mathbb{S}$ leads either to $mSc$ or to a deadlock state $S^*$, i.e. $S^{k_1} \xrightarrow{i-1} S^{k_i} \xrightarrow{v-i-1} S^{k_v} \rightarrow S^*$, multimodal processes also may reach a **deadlock state**.

## 2.3 Problem statement

Consider a SCCP specified (due to (1)) by the given set $R$ of resources, dispatching rules $\theta$, local $\Pi$, and multimodal processes routes $M\Pi$ as well. Usually the main question concerns SCCP periodicity, i.e. Does the cyclic execution of local processes exist? Response to the above question requires answers to more detailed questions, for instance: What is the admissible initial allocation of processes (i.e. the possible AGVs dockings)? What are dispatching rules $\theta$ guaranteeing a given SCCP periodicity (in local/multimodal sense)? The problems stated above have been studied in [2-4], [10]. In that context, a new problem regarding possible switching among cyclic steady states can be seen as their obvious consequence. Therefore, the newly arising questions are: Is it possible to reschedule cyclic schedules as to “jump” from one cyclic steady state to another? Is it possible to “jump” directly or indirectly? What are the control rules allowing one to do it? These kind of questions are of crucial importance for manufacturing and transportation systems aimed at short-run production shifts and/or the itinerary planning of passengers (e.g. in a sub-way network).

In terms of introduced notations ($\mathbb{S}$, $Sc$, $mSc$) the above questions boil down to the following ones:

*Does there exist a nonempty space $MSC$ of local ($Sc$) and multimodal ($mSc$) processes cyclic steady states?*

*Let $mSc_1, mSc_2 \in MSC$. Is the state $mSc_2 \in MSC$ reachable from $mSc_1 \in MSC$?*

## 2.4 Repetitive processes scheduling

Searching for response to the first of above stated questions, let us note that a possible cyclic steady state of multimodal processes formulated in terms of CSP can be stated as the following constraints satisfaction problem [2], [3]:

$$CS(SC) = (\{(X, T_c, mX, Tm), \{D_X, D_{T_c}, D_{mX}, D_{Tm}\}\}, C) \quad (6)$$

where: $X, T_c, mX, Tm$ – the decision variables, where $T_c$ and $Tm$ are local and multimodal cycles (periods); $X, mX$ – sequences of operations beginning in local, and multimodal processes, respectively, $D_X, D_{mX}, D_{T_c}, D_{Tm}$ – domains of variables $X, T_c, mX, Tm, C$ – constraints determining the relationship among local and multimodal processes, i.e. constraints linking $X, T_c, mX, Tm$. The detailed specification of constraints considered is available in [2], [4].

## 2.5 Cyclic processes reachability

Cyclic steady states of multimodal $mSc_i$ and local $Sc_i$ processes are solutions to the problem (6). Considering $mSc_1, mSc_2 \in MSC$ and their $mSc_1^*, mSc_2^*$ the following property is hold:
**Property:** The indirect switching between $mSc_1$ and $mSc_2$ is enabled if two states: $S^a \in mSc_1$ and $S^b \in mSc_2$ possessing a common shared allocation $A^x$ there exist.

The states $S^a, S^b$ should not necessarily belong to $mSc_1$ and $mSc_2$. One of them may belong either to a reachability state space $mSc_1^*$ or to $mSc_2^*$. For example, if exist two states $S^a = (Sl^a, MA^a) \in mSc_1$ and $S^b = (Sl^b, MA^b) \in mSc_2^*$, where $Sl^a = (A^x, Z^a, Q^a)$ and $Sl^b = (A^x, Z^b, Q^b)$ then replacing at the allocation $A^x$ the semaphores $Z^a$ and indices $Q^a$ by $Z^b, Q^b$ results in switching from $Sl^a$ to $Sl^b$ ($S^a$ to $S^b$), and consequently in switching from $mSc_1$ to $mSc_2$. That implies the possible indirectly switching between cyclic multimodal processes exist. The cyclic steady states $mSc_1$ and $mSc_2$ are mutually reachable only if they possess the states sharing the same allocations $A^x$. Therefore, the reachability problem (the second of considered questions) of the cyclic steady states space, e.g. regarding of switching between two states $mSc_1 \subseteq mSc_1^*$ and $mSc_2 \subseteq mSc_2^*$, is concluded in the question: Does there exist two states $S^a \in mSc_1$ and $S^b \subseteq mSc_2^*$ ($mSl^a \in mSc_1^*$ and $mSl^b \subseteq mSc_2$) sharing the same allocation $A^x$ of local cyclic processes?

## 3 Illustrative example

Given the SCCP see Fig. 1. The periods $Tc$ of the cyclic processes steady states $Sc_1$ and $Sc_2$ (local processes behaviors) obtained from the $CS$ (5) the solution while implemented in OzMozart platform (in less than 1 s due to Intel Core Duo 3.00 GHz, 4.00 GB RAM computer) are equal to 18 and 11 t.u., respectively. In turn the periods $Tm$ of the cyclic multimodal processes steady states $mSc_1$ and $mSc_2$ are equal to 55 and 33 respectively.

The obtained cyclic steady states space is shown in Fig 2. The local states are distinguished by "O", while multimodal by "O". In case of multimodal processes $mSc_1$ the completion time for each route is the same and equals to 30 u.t. (see Fig 3). However, in case of $mSc_2$ the completion time for the route $mp_1$ equals to 22 u.t, and 27u.t. for the $mp_2$ (see Fig. 3). That means the longer cycle of the $mSc_1$ implies the longer multimodal processes completion time. So, for a given SCCP the following question can be stated: Does the steady state $mSc_2$ is reachable from $mSc_1$?

Due to the property provided the response is positive, however only if there exist states $S^a \in mSc_1$ and $S^b \in mSc_2^*$ possessing a common shared allocation $A^x$. The $mSc_2$ is reachable from $mSc_1$ in the local state $Sl^{11}$ sharing the common allocation with $Sl^{29}$. The states $S^{29}$ and $S^{30}$ follow the multimodal states $Sl^{11}, Sl^{29}$ that can be mutually reachable from each other. Switching from state $Sl^{11}$ to $Sl^{29}$ can be seen as result of change either of semaphores (from $Z^{29}$ to $Z^{30}$) and/or indices (from $Q^{29}$ to $Q^{30}$). The switching assumes the same processes allocation – that means (in terms of AGVS) the same AGVs allocations.

The considered rescheduling from $mSc_1$ to $mSc_2$ employing of switching $S^{29}$ to $S^{30}$ is distinguished by the green line in Fig. 2. Another illustration of such rescheduling provides the Gantt's chart from Fig. 3.

Note that in the considered case the rescheduling does not disturb execution of multimodal processes.
<figure><img src="image_3.png" /><figcaption>Fig. 2. The cyclic steady states spaces of SCCP from Fig. 1</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Gantt's chart illustrating the way the cyclic steady state $mSc_2$ can be reachable from $mSc_1$.</figcaption></figure>
# 4. Concluding remarks

Structural constraints limiting AGVS behavior imply two fundamental problems: Does there exist a set of dispatching rules subject to AGVS's structure constraints guaranteeing solution to a CSP representation of the cyclic scheduling problem? What set of dispatching rules subject to assumed cyclic behavior of AGVS guarantees solution to a CSP representation of the cyclic scheduling problem?

In terms of the second question the paper's contribution is the property providing sufficient condition guaranteeing local and multimodal cyclic processes rescheduling. Therefore, the developed conditions can be treated as the new rules enlarging the above mentioned set of dispatching rules. Moreover, the provided conditions complete the rules enabling direct switching between cyclic behaviors [3], [4] for the new rules allowing one to reschedule cyclic behaviors indirectly, i.e. through a set of so called transient states (not belonging to rescheduled cyclic steady states).

# REFERENCES

1. Alpan G., Jafari M.A., Dynamic analysis of timed Petri nets: a case of two processes and a shared resource. IEEE Trans. on Robotics and Automation 1997, Vol.13, No.3: 338-346

2. Bocewicz G., Banaszak Z., Declarative approach to cyclic scheduling of multimodal processes. In: EcoProduction and Logistics, Golińska P., (Eds.), Vol. 1, Springer-Verlag, 2013, 203-235

3. Bocewicz G., Banaszak Z., Declarative approach to cyclic steady states space refinement: periodic processes scheduling. In: International Journal of Advanced Manufacturing Technology, International Journal of Advanced Manufacturing Technology, Springer-Verlag, 2012, (in print)

4. Bocewicz G., Wójcik R., Banaszak Z., Cyclic Steady State Refinement. In: International Symposium on Distributed Computing and Artificial Intelligence, series: Advances in Intelligent and Soft Computing, Abraham A., Corchado J.M., Rodríguez González S., de Paz Santana J.F. (Eds.), Vol. 91, Springer-Verlag, 2011, 191-198

5. Fournier, O., Lopez, P., Lan Sun Luk, J.-D., Cyclic scheduling following the social behavior of ant colonies. In. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2002, 450-454

6. Levner E., Kats V., Alcaide D. Pablo L., T.C.E. Cheng, Complexity of cyclic scheduling problems: A state-of-the-art survey. Computers and Industrial Engineering, Vol. 59, Issue 2, 2010, 352-361

7. Liebchen, C., Möhring, R.H., A case study in periodic timetabling. In: Electronic Notes in Theoretical Computer Science, Vol. 66 (6), 2002, 21-34

8. Polak M., Majdzik P., Banaszak Z., Wójcik R., The performance evaluation tool for automated prototyping of concurrent cyclic processes. Fundamenta Informaticae. In: ISO Press, Editor-in-Chief, A. Skowron, Vol. 60, No.1-4, 2004, 269-289

9. Smart Nigiel P., The Algorithmic Resolution of Diophantine Equations. London Mathematical Society Student Text, 41. Cambridge University Press, Cambridge, 1998

10. Wójcik R., Constraint programming approach to designing conflict-free schedules for repetitive manufacturing processes. Digital enterprise technology. Perspectives and future challenges. Ed. by Pedro F. Cunha, Paul G. Maropoulos, Springer, 2007, 267-274