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

HAL
open science

# Structure Dynamics Control-Based Service Scheduling in Collaborative Cyber-Physical Supply Networks

Dmitry Ivanov, Boris Sokolov

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

## To cite this version:

Dmitry Ivanov, Boris Sokolov. Structure Dynamics Control-Based Service Scheduling in Collaborative Cyber-Physical Supply Networks. 13th Working Confeence on Virtual Enterpries (PROVE), Oct 2012, Bournemouth, United Kingdom. pp.280-288, 10.1007/978-3-642-32775-9_29. hal-01520468

HAL Id: hal-01520468

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

Submitted on 10 May 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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Structure Dynamics Control-based Service Scheduling
in Collaborative Cyber-physical Supply Networks

Dmitry Ivanov<fnref n="1" />, and Boris Sokolov<fnref n="2" />

Divanov@hwr-berlin.de

**Abstract.** An original model for dynamic scheduling of services in collaborative cyber-physical supply networks is stated and solved with the help of structure dynamics control approach. The proposed service-oriented description makes it possible simultaneously to (i) schedule information services according to business process execution and (ii) plan costs of information resources.

**Keywords:** Supply network, collaborative cyber-physical system, services, scheduling, reconfiguration, structure dynamics control, optimal control.

## 1 Introduction

The impact of information technologies (IT) on the material processes in collaborative value-adding networks in general and supply networks (SN) in particular becomes more and more crucial [1], [2]. Recent research indicated that an aligning of business processes and information systems (IS) may potentially provide new quality of decision-making support and an increased SN performance [3], [4], [5]. Most of the new IT share attributes of intelligence. Examples include data mining, cloud computing, physical internet, pattern recognition, knowledge discovery, to name a few. That is why it becomes a timely and crucial topic to consider SNs as *collaborative cyber-physical systems*. Such SNs are common not only in manufacturing but also in different cyber-physical systems, e.g., in networks of emergency response units, energy supply, city traffic control, and security control systems.

Cyber-physical systems incorporate elements from both information and material (physical) subsystems and processes which are integrated and decisions in them are cohesive [6]. Elements of physical processes are supported by information services. Cyber-physical systems are characterized by decentralization and autonomous behavior of their elements. In addition, such systems evolve through adaptation and reconfiguration of their structures, i.e. through *structure dynamics* [7], [8].

In these settings, two questions may be raised: (1) what is the optimal volume of information services needed to ensure operation of physical systems and (2) how these services shall be scheduled at the planning stage and adapted in dynamics at the execution control stage. It can be observed that current concepts and models for SN integration do not provide adequate decision support from intelligent information and

<footnote n="1">¹ Berlin School of Economics and Law, 10825 Berlin, Germany</footnote>

<footnote n="2">² St. Petersburg Institute of Informatics and Automation RAS</footnote>
product technologies; we regard this shortcoming as an opportunity for research and development, which could significantly improve the practice of SN management. On one hand, aligning of new intelligent elements of IT infrastructures, i.e., the information services, with real material flows can be achieved. On the other hand, investments into information resources can be estimated regarding real execution dynamics.

This paper faces these two decision domains on the basis of structure dynamics control (SDC) approach [7]. Conventionally, the above-described two problems have been solved step-by-step. With the help of SDC, a special dynamic representation of multi-structural networks is proposed where such problems can be solved simultaneously. In addition, due to the increasing role of information services in different forms, e.g., cloud computing, the service-based approaches to integrated planning and scheduling of both material and information flows in collaborative networks are needed [9], [10]. Such integration is also to prevent failures of IT-enabled SNs [11].

Although recent research has extensively dealt with SN scheduling ([12], [13], [14] and IT scheduling (see, e.g., works on scheduling telecommunications) in isolation, the integrated scheduling of both material and information flows still represents a research gap. In this paper, the problem of dynamic scheduling of services in SNs as cyber-physical systems is stated and solved with the help of SDC approach. In addition, specific research contributions are the considerations of IT reconfiguration in a real execution stage and monetary estimation of investments into IT.

## 2 Research Methodology

Both material and information flows are subject to structural changes. SDC approach is multi-disciplinary and reaches beyond the classical borders of control theory and mathematical optimization [15]. It is based on a combined application of optimal program control (OPC) theory and mathematical programming (MP), and extents their classical borders by their mutual integration and by decentralization of system description with help of active modelling objects (AMO). With the help of AMO, ideas of incorporating control policies into agent-based architectures can be addressed [16]. SDC approach has been previously applied to telecommunication networks, aerospace, and supply chains [7], [13], [15].

The SDC-based models are based on the dynamic interpretation of planning in accordance with the natural logic of time where the decisions on SN planning are taken for certain intervals of structural constancy and regarding problems of significantly smaller dimensionality. For each interval, a static optimization problem of a smaller dimensionality can be solved with the help of MP. The transitions between the intervals are modelled in the dynamic OPC model. As the SDC is based on control theory, it is a convenient approach to describe intangible services due to abstract nature of state variables which can be interpreted as abstract service volumes. The study [13] has proposed an original model to represent SN schedules as OPC. In this paper, this model is extended to service scheduling.
# 3 Problem Statement

The problem is to find a joint schedule taking into account the IS modernization, i.e., four schedules should be generated in a coordinated manner, i.e.,

* an OPC (schedule) for the material supply processes in the SN (model M1),

* an OPC (schedule) for information services (model M2),

* an OPC (schedule) for the information resources (IR) (model M3), and

* an OPC (schedule) for the IS modernization (model M4).

Goals are measured by the job's delivery times to customers and the volume of the delivered jobs. Jobs are to be scheduled subject to maximal customer service level, minimal backlogs, minimal idle time of services, and minimal costs of IT (including, fixed, operation, and idle cost). Customer service level is measured by a function of the times when the jobs are delivered to the customers. A simple example of the interrelations among business processes, services, functions, and IRs is presented in Fig. 2.

<figure><img src="image_4.png" /><figcaption>Fig. 2. Interrelations among business processes, service, functions, and IRs</figcaption></figure>

## General assumptions and parameters

* Consider jobs $A = \{A_v; v = 1,...,n\}$ in business processes. The jobs are independent and are not available for processing at time zero. Each of the jobs has a release date that is known in advance through the SN coordination.

* Each of the jobs $A_v$ is composed of the operations $D^{(v)} = \{D_i^{(v)}; i = 1,...,k_v\}$.

* Precedence constraints exist, i.e. the operations are logically arranged in jobs.

* $a_i$ is the planned processing volume of the operation $D_i^{(v)}$.

* The execution of operations $D^{(v)}$ is realized by different IR $B_r^{(v,i)}$.

* Denote $B_r^{(v,i)} = \{B_r^{(v,i)}; r = 1,...,\rho_v\}$ as a set of IRs in an IS.

* IRs have unequal rates which may also differ for various operations and therefore influence the processing time. Denote $e_r^{(i)}, V_r^{(i)}, \Phi_r^{(i)}$ as maximal processing intensities.
sity of the operation $D_l^{(v)}$ at the IR $B_r^{(v,j)}$, maximal capacity of the IR $B_r^{(v,j)}$, and maximal productivity of the IR $B_r^{(v,j)}$ before the reconfiguration correspondingly; $\bar{e}_r^{(i)}$, $\bar{V}_r^{(i)}$, $\bar{\Phi}_r^{(i)}$ are given variables characterizing the same domains but after the modernization.

* Let $t$ be current instant of time, $T = (t_0, t_f]$ the scheduling horizon, and $t_0, t_f$ the start (end) instant of time for the scheduling horizon respectively.

* Denote $\varepsilon(t)$ as an element of the matrix of time-spatial constraints ($\varepsilon(t) = 1$, if $t_0^k < t \le t_f^k$, $\varepsilon(t) = 0$ otherwise), where $k$ are the numbers of time windows available for operations' execution (e.g., subject to maintenance).

* Denote $S^{(v)} = \{S_l^{(v)}; l = 1, \dots, d_j\}$ as a set of IT services to execute operations $D_l^{(v)}$.

* Denote $F^{(v,l)} = \{F_\chi^{(v,l)}; \chi = 1, \dots, S_l\}$ as a set of functions of IR to implement the service $S_l^{(v)}$, i.e., each service is may be composed of functions $F_\chi^{(v,l)}$ from different IR and is characterized by availability time windows subject to the function $\varepsilon(t)$, productivity, i.e., the processed volume of operations at an instant of time, and costs (fixed cost $c_{il}^{(v,1)}(t)$ and operation cost $c_{il}^{(v,2)}(t)$).

* Denote $g_l^{(v)}$ as a number of operations $D_l^{(v)}$ which may be served by a service $S_l^{(v)}$.

* Denote $h_i^{(v)}$ as a given number of services $S_l^{(v)}$ which may be simultaneously used by execution the operation $D_i^{(v)}$.

* Denote $D_l^{(v,i)} = \{D_{<l,\chi>}^{(v,i)}; l = 1, \dots, d_j, \chi = 1, \dots, S_l\}$ as operations of IR (e.g., information processing, storage, transmission, and protection).

* Denote $D_r^{(p,i)} = \{D_{<r,k>}^{(p,i)}; k = 1, \dots, \pi_i^{(r)}\}$ as operations in the given jobs for planned reconfiguration (modernization) of the IR $B_r^{(v,i)}$.

* Denote $V_\chi^{(v)}$ as the online storage capacity of the IR $B_r^{(v,i)}$ to execute the operation $D_{<l,\chi>}^{(v,i)}$ and $\delta_{\chi r}^{(v,i)}(\tau)$ as a quality function to estimate the execution results.

* Denote $c_{\chi r}^{(l,1)}(\tau)$, $c_{\chi r}^{(l,2)}(\tau)$ as given time functions of fixed and operation cost of an IR $B_r^{(v,i)}$ used for the operation $D_{<l,\chi>}^{(v,i)}$ by realization of the function $F_\chi^{(v,l)}$.

* Setup times are independent and included in the processing time.

* Denote $\eta_{il}^{(v)}(t)$ as a given time function which characterizes the costs of idle time of services for the operation $D_i^{(v)}$;

* $y_{il}^{(v)}$ denotes the value of current idle cost due to a backlog in the operation $D_i^{(v)}$ caused by unavailability of the service $S_l^{(v)}$.

In order to describe the execution of operations, let us introduce the state variables: $x_{il}^{(v)}(t)$ to characterize the execution of the $D_i^{(v)}$ with the use of the service $S_l^{(v)}$, $x_{il}^{(v,1)}(t)$ is an auxiliary variable characterizing the current state of the operation
$D_i^{(v)}$. Its value is numerically equal to the time interval that has elapsed since the beginning of the scheduling interval and the execution start of the operation $D_i^{(v)}$;

$x_{il}^{(v,2)}(t)$ is an auxiliary variable characterizing the current state of the processing operation. Its value is numerically equal to the time interval that has elapsed since the end of the execution of the operation $D_i^{(v)}$ and the end of the scheduling interval;

$x_r^{(v,l)}$ is an auxiliary variable characterizing the employment time of the IR $B_r^{(v,j)}$;

$x_\chi^{(v,j)}$ which characterizes the execution of the operation $D_{\langle \cdot, \cdot \rangle}^{(v,j)}$;

$x_{rS_l}^{(v,l)}(t)$ is an auxiliary variable characterizing the current state of the information processing operation. Its value is numerically equal to the time interval that has elapsed since the end of the execution of the operation $D_{\langle \cdot, \cdot \rangle}^{(v,j)}$ and the instant of time $t$.

*Decision variables and goals*

$u_{il}^{(v)}(t)$ is a control that is equal to 1 if the operation $D_i^{(v)}$ is assigned to the service $S_l^{(v)}$ at the moment $t$; otherwise $u_{il}^{(v)}(t) = 0$.

$\vartheta_{il}^{(v,1)}(t)$ and $\vartheta_{il}^{(v,2)}(t)$ are auxiliary control variables that are equal to 1 if the operation $D_i^{(v)}$ has not been executed and is equal 0 otherwise.

$w_{\chi r}^{(v,l)}$ is a control that is equal to 1 if the operation $D_{\langle \cdot, \cdot \rangle}^{(v,j)}$ is assigned to the IR $B_r^{(v,j)}$ and is equal 0 otherwise;

$\omega_{S_l}^{(v,l)}(t)$ is auxiliary control that is equal to 1 if all the operations $D_{\langle \cdot, \cdot \rangle}^{(v,j)}$ in the function $F_\chi^{(v,l)}$ are completed and is equal 0 otherwise;

$\vartheta_r^{(p,2)}(t)$ is auxiliary control that is equal to 1 if the reconfiguration from old parameters $e_r^{(i)}, V_r^{(i)}, \Phi_r^{(i)}$ to new ones $\tilde{e}_r^{(i)}, \tilde{V}_r^{(i)}, \tilde{\Phi}_r^{(i)}$ is completed and is 0 otherwise.

# 4 Mathematical Model

The SN is modelled as a networked controlled system described through a dynamic interpretation of the operations' execution. Control models (M1-M2) are first used to assign and sequence services to business operations. Then M2-M3 are employed to assign and schedule services to IRs. Finally, M3-M4 are launched to schedule IT modernization (reconfiguration) in compliance with the results of M1-M2. The basic interaction of these models is that after the solving the conjunctive system for M1, the found control variables are used in the constraints of the conjunctive system for M2. Analogously, M2, M3, and M4 are interconnected. In solving the main systems, the interaction of the models is organized in the reverse way, from M4 to M1. Note that in the calculation procedure, the models M1-M4 will be solved simultaneously, i.e., the supply, service, IR, and modernization scheduling will be integrated. Because of the limited size of this paper, we shortly introduce the models M2; it can be easily extrapolated on models M3-M4.
The model of execution dynamics of operations $D_i^{(v)}$ can be expressed as (1)-(3):

$$ \frac{dx_i^{(v,l)}}{dt} = \varepsilon_{il}(t) \cdot u_{il}^{(v)}(t) \quad (1) $$

$$ \frac{dy_{il}^{(v)}}{dt} = \eta_{il}(t)[1 - \vartheta_{il}^{(v,1)} - u_{il}^{(v)} - \vartheta_{il}^{(v,2)}] \quad (2) $$

$$ \frac{dx_{il}^{(v,1)}}{dt} = \vartheta_{il}^{(v,1)}; \quad \frac{dx_{il}^{(v,2)}}{dt} = \vartheta_{il}^{(v,2)} \quad (3) $$

Eq. (1) describes operation's execution. Eq. (2) represents idle time in the business process caused by unavailability of the service $S_i^{(v)}$. Eq. (3) represents the dynamics of operation's execution according to precedence constraints.

The control actions are constrained as follows:

$$ \sum_{i=1}^{k_i} u_{il}^{(v)}(t) \le g_l^{(v)}; \forall l; \sum_{l=1}^{d_j} u_{il}^{(v)}(t) \le h_i^{(v)}; \forall i \quad (4) $$

$$ \sum_{l=1}^{d_j} u_{il}^{(v)} \left[ \sum_{\alpha \in \Gamma_{v1}} (a_{\alpha}^{(v,l)} - x_{\alpha}^{(v,l)}) + \prod_{\beta \in \Gamma_{v2}} (a_{\beta}^{(v,l)} - x_{\beta}^{(v,l)}) \right] = 0; \forall v \quad (5) $$

$$ \vartheta_{il}^{(v,1)} \cdot x_{il}^{(v,l)} = 0; \quad \vartheta_{il}^{(v,2)} (a_{il}^{(v,l)} - x_{il}^{(v,l)}) = 0; \forall i; \forall l \quad (6) $$

$$ u_{il}^{(v)}(t) \in \{0,1\}; \quad \vartheta_{il}^{(v)}(t) \in \{0,1\} \quad (7) $$

Constraints (4) are assignment problem constraints. Constraints (5) determine the precedence relations. Constraints (6) interconnect main and auxiliary controls. Equation (7) constraints control to be Boolean variables.

The end conditions are defined as follows:

$$ t = t_0^{(j)} : x_i^{(v)}(t_0^{(j)}) = y_{il}^{(v)}(t_0^{(j)}) = x_{il}^{(v)}(t_0^{(j)}) = 0 \quad (8) $$

$$ t = t_f^{(j)} : x_i^{(v)}(t_f^{(j)}) = a_i^{(v)}; \quad y_i^{(v)}(t_f^{(j)}); \quad x_i^{(v)}(t_f^{(j)}) \in \mathbf{R}^1 \quad (9) $$

Eqs. (8) and (9) define initial and end values of the variables $x_i^{(v)}(t)$, $y_{il}^{(v)}(t)$, $x_{il}^{(v)}(t)$ at the moments $t_0^{(j)}$ and $t_f^{(j)}$.

The goals are defined as follows:

$$ \min J_1^{(v)} = \sum_{i=1}^{k_v} \sum_{l=1}^{d_j} y_{il}^{(v)}(t_f^{(j)}) \quad (10) $$
$$ \max J_2 = \sum_{i=1}^{k_v} \sum_{l=1}^{d_l} \frac{1}{x_{il}^{(v,2)}(t_f^{(j)})} \int_{t_0^{(j)}}^{t_f^{(j)}} \vartheta_{il}^{(v,2)}(\tau) d\tau \quad (11) $$

$$ \min J_3 = \sum_{i=1}^{k_v} \sum_{l=1}^{d_l} \int_{t_0^{(j)}}^{t_f^{(j)}} [c_{il}^{(v,1)}(\tau) + c_{il}^{(v,2)}(\tau)] \cdot u_{il}^{(v)}(\tau) d\tau \quad (12) $$

Eq. (10) minimizes idle time of services. Eq. (11) estimates the service level by the volume of completed jobs. Eq. (12) minimizes total service costs.

The models M3 and M4 are constructed analogously. They also contain some additional elements, e.g., control actions are constrained by information processing intensities. In addition, perturbations impacts $0 \le \xi_r^{(j,1)}(t) \le 1$ are introduced in the constraint system to take into account uncertainty of real execution and to estimate schedule robustness on the basis of attainable sets [18].

# 5 Discussion of Results and Conclusions

New intelligent information services result from decentralized IT infrastructures. This forces changes in decision support systems for SN which may become cyber-physical systems. If so, a new challenge of joint scheduling the material flows and information services will be faced in practice in next years. In addition to the existing models on the scheduling of material processes in SNs, this study has added models for integrated service, IR, and IS modernization scheduling. The coordinated usage of these models allows dynamic scheduling of services integrated with material and IR scheduling taking into account possible IS reconfiguration in a planned (i.e., the modernization) and perturbation-driven (i.e., adaptation) modes. This study is among first to explicitly formulate and solve in a dynamic manner the stated service scheduling problem. The proposed service-oriented concept allows explicitly incorporate material and information processes in the SN and take into account modern trends of decentralized information services, e.g., cloud computing. In doing so, this study contributes to consideration of SNs as collaborative cyber-physical systems.

With the help of SDC, problems of network design and scheduling can be solved simultaneously. In addition to the service scheduling and interconnecting each service with ISs needed for its realization, the proposed approach makes it possible simultaneously to (i) determine the volume of information services needed for physical supply processes (Eqs. (10) and (11)) and (ii) determine this volume in monetary form (Eq. (12)). In addition, the models M3-M4 allow taking into account IS dynamics and reconfiguration.

The proposed models and algorithms have been validated in a developed prototype based on C++ and XML. The OPC calculation is based on the Hamiltonian function. In integrating the main and the conjunctive equation systems, the values of variables in both of the systems can be obtained at each point of time. The maximum principle guarantees that the optimal solutions (i.e., the solution with maximal values) of the instantaneous problems (i.e., at each point of time) give the optimal solution to the
overall problem. For these sub-problems, optimal solutions can be found, e.g., with the help of MP. Then these solutions are linked into an OPC. The optimality properties have been proved theoretically and experimentally.

Further analysis may include an explicit incorporation of AMO into scheduling model, and a detailed representation of models M3-M4. This paper can also be extended in future by application to concrete case-studies. The proposed models are implemented in software prototype where numerical experiments have already been performed to validate hybrid scheduling algorithms on the basis of OPC and MP. In future, IR modernization and adaptation can be further investigated with the developed models and algorithms.

## References

1. Camarinha-Matos, L.M., Macedo, P. A conceptual model of value systems in collaborative networks. J Int Man, 21 (3), 287-299 (2010).

2. Lee, J., Udatta S., Palekar, Qualls, W.. Supply chain efficiency and security: Coordination for collaborative investment in technology. Eur J Oper Res, 210 568-578 (2011).

3. Dedrick, J., Xu, S., Zhu, K. How does information technology shape supply-chain structure? Evidence on the number of suppliers. J Man Inf Sys, 25 (2), pp. 41-72 (2008).

4. Camarinha-Matos, L.M. Collaborative networked organizations: Status and trends in manufacturing. Annual Rev Control 33 (2), 199-208 (2009).

5. Jain, V., Wadhwa, S., Deshmukh, S.G. Revisiting information systems to support a dynamic supply chain: Issues and perspectives. Prod Plan Control 20 (1), 17-29 (2009).

6. Zhuge, H. Semantic linking through spaces for cyber-physical-socio intelligence: A methodology". Artif Intell, 175 (5-6), 988-1019 (2011).

7. Ivanov D, Sokolov B, Kaeschel J. A multi-structural framework for adaptive supply chain planning and operations with structure dynamics considerations. Eur J Oper Res 200, 409-420 (2010).

8. Dekkers, R., Luttervelt, C. A. v. Industrial networks: capturing changeability? Int J Net Virt Org, 3(1), pp. 1-24 (2006).

9. Bardhan, I.R., Demirkan, H., Kannan, P.K., Kauffman, R., Sougstad, R. An interdisciplinary perspective on IT services management and service science. J Man Inf Syst, 26 (4), 13-64.

10. Li, Q., Zhou, J., Peng, Q.-R., Li, C.-Q., Wang, C., Wu, J., Shao, B.-E. Business processes oriented heterogeneous systems integration platform for networked enterprises. Comput Ind 61 (2), 127-144 (2010).

11. Soroor, J., Tarokh, M.J., Keshtgary, M. Preventing failure in IT-enabled systems for supply chain management. Int J Prod Res, 47 (23), 6543-6557 (2009).

12. Chen, Z.-L. Integrated Production and Outbound Distribution Scheduling: Review and Extensions. Oper Res, 58(1). 130-148 (2009).

13. Ivanov, D., Sokolov, B. Dynamic supply chain scheduling. J Sched, 15(2), 201-216 (2012).

14. Giard, V., Mendy, G. Scheduling coordination in a supply chain using advance demand information. Prod Plan Control 19 (7), 655-667 (2008).

15. Ivanov, D., Sokolov, B. (2010), Adaptive supply chain Management, Springer, London.

16. Seok, H., Nof, S.Y., Filip, F.G. Sustainability decision support system based on collaborative control theory. Ann Rev Control, 36(1), 85-100 (2012).

17. Surana, A., Kumara, S., Greaves, M., Raghavan, U.N. Supply-chain networks: a complex adaptive systems perspective. Int J Prod Res, 43(20), 4235-4265 (2005).

18. Ivanov, D., Dolgui, A., Sokolov, B. On applicability of optimal control theory to adaptive supply chain planning and scheduling. Ann Rev Control, 36(1), 73-84 (2012).