Complex Scheduling of Measurement and Calculation Systems Functioning Boris Sokolova, Valerii Zakharova, Aleksey Krylova a St. Petersburg Federal Research Center of the Russian Academy of Sciences (SPC RAS), 39, 14th line V.O., St.Petersburg, 199178, Russia Abstract The article suggests a polymodel description of cyber-physical systems (CFS) functioning, that represent multifunctional hardware and software complexes aimed at reception (transmission), storage, processing and forming of controlling actions both for the service objects (SO), conducting a given set of target tasks that are not included into CFS, as well as at ensuring their own reliable operation. Within the subject field, related to scientific device engineering, these models and relevant algorithms applying them, have a big scientific and practical value, as due to optimization of the measuring and computing operations (MCO), they allow to generally increase efficiency of using precise instrumental complexes in the specified environmental conditions. The developed polymodel description is based on the original dynamic interpretation of relevant processes. Keywords Cyber-physical systems, measuring and computing operations scheduling, dynamic models, optimal software control, software tools. “Smart and Safe Cities”, “smart” defense- 1. Introduction relevant objects etc., such systems can ensure implementation of technologies for controlled 1 self-organization within traffic management Currently various classes of cyber- on the city streets by means of analyzing data physical systems (CPS) are becoming the on status and driving direction, received from major component of digital production and vehicles; coordinated functioning of digital economics in general; these systems production equipment for effective involve measuring, telecommuncational and manufacturing of small sets of various items, control subsystems. [1,2]. Hereafter CPS is as well as electricity generation by providing referred to a centralized and/or distributed workload optimization of thermal electric hardware and software system, implementing power stations, nuclear power plants, physical and infocommunicational procedures hydroelectric power stations, etc. of processing, accumulation, storage, search, In this case the CPS measurement and protection, dissemination and usage of data calculation subsystems can be considered as and information, as well as interacting with variants of intellectual self-managed objects of the real world through physical measurement and calculation systems with a processes. number of specific features. In the first Based on the CPS projects of “Smart instance these features include the following Manufacturing”, “Smart Houses”, “Smart [3]: the number of measurement channels Energy”, “Smart Transport”, “Smart Life within one CPS can involve from tens to Safety System”, “Smart Healthcare System”, hundreds of units even in the upcoming years; 1 measurement channels can include sensors of Intelligent Transport Systems. Transport Security - 2021, May 14, St. Petersburg, Russia. various values, both scalar and tensor, EMAIL: sokolov_boris@inbox.ru (B. Sokolov); whereby in the territorial aspect the sensors Valeriov@yandex.ru (V. Zakharov); kralex98@yandex.ru can be placed remotely from each other; (A. Krylov). ORCID: 0000-0002-2295-7570 (B. Sokolov); 0000-0002-2086- measurement information is transmitted over (V. Zakharov); 0000-0003-0087-857X (A. Krylov). long distances through wire and wireless ©� 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). communication channels. CEUR Workshop Proceedings (CEUR-WS.org) Measurement information processing can implementing MCO (which are a subset of OI) be implemented by means of various can be formulated as follows: it is required to computational technologies, including cloud find such an admissible control programme for technologies, at the same time the processing information-computational operations and must be implemented close to the real time CPS (their functioning scheduling), so that scale [4]. CPS control subsystems are within its implementation all the operations, characterized by similar features. that are a part of relevant technological cycles Creation of economically effective CPS is of SO control, would be conducted timely and possible only in case the data, information and in the full scale, and the quality of supporting knowledge, is characterized by informational support to the SO would meet high confidence, received swiftly and the all the specified requirements. At the same operational costs are sufficiently small. Due to time, if there are several admissible limited scope of the article let us consider only programmes for CPS control received, it is the issue of developing the MCO scheduling required to select the best possible plan, as the most important and time- (appropriate) programme (comprehensive consuming stage of the complex scheduling on plan) based on the accepted optimality CPS functioning [5, 6]. criterion [10, 11]. 2. Scheduling problem description 3. Dynamic models for CPS fucntioning scheduling Let us assume that there is a set of service objects (SO): =  {A A  , i ∈ N}, forming part of Formalization of the scheduling task, as it i some SO group and aimed at solving the joint was described in the introduction, will be set target task (i.e., monitoring of eco- implemented, applying the dynamic economic objects condition). To ensure SO interpretation of the process on technical proper functioning it is required to operations realization, suggested by the permanently conduct evaluation and correction authors. Based on the problem description of of navigational data on board of each SO. This CPS scheduling, let us introduce the following task is implemented by CPS [2, 9]: that models for programme control. include hardware and software complexes, The dynamic model for programme control which solve tasks on reception (transmission), of interaction operations (including the storage, processing and forming of controlling computing operations) in CPS (model Мо). actions both for the service objects, that are  m M o = u ( o ) (t ) | xi(γo ) = ∑ εij (t ) ⋅ ui(γo j) ; xi(γo ) (t0 ) =0; not included into CPS, and at ensuring their  j =1 si own reliable operation. m xi(γo ) (t f ) ai(γo ) ; ∑∑ ui(γo j) ≤ c (jo,1) ; = Let us introduce a set of CPS: =i 1 γ= 1  B= {B j , i ∈ M }, M ={1,..., m }. Herewith, due to m sj ∑∑ u ≤ c (o ) iγ j ( o ,2) i ; ui(γo j) (t ) ∈ {0,1}; (1) availability of unitized hardware and software j= 1 γ= 1 tools in order to provide informational   ui(γo j)  ∑ (ai(αo ) − xi(αo ) ) + ∏ (ai(βo ) − xi(βo ) )  = 0; interaction on SO and CPS, in case relevant  α∈Γ  iγ 1 β ∈Γiγ 2  information is available, each of the listed = i, j 1,..., m; i= ≠ j; γ 1,...,si } , elements of SO and CPS is capable to a certain with xi(γo ) — the variable, characterizing the extent conduct functions of any other element, based on the emerging situation. state of IO implementation ( Dγ(i ) , Dα(i ) , Dβ(i ) ); To ensure convenience of further aγ( o ) , ai(αo ) , ai(βo ) — the specified volumes of representation we introduce the generalized set of interacting objects (IO) operations implementation; ui(γo )j (t ) — control =B { Bl , l , i, j ∈ = M N = M {1,..., m}} . Let us  action; ui(γo )j (t ) = 1 , if operation Dγ(i ) is also review a set of operations for interaction implemented, and in the opposite case (OI) =D (i ) { Dγ(i) , γ ∈ Φ}= , Φ {1,..., si }. ui(γo )j (t ) = 0 ; Γi γ1 , Γi γ 2 — a set of numbers of interaction operations, conducted with object All considered, at the informative level the Bi , immediately preceding and technologically task on scheduling of CPS functioning for related to operation Dγ(i ) applying logic difference of the model (2) from the ones operations «AND», «OR» respectively; previously proposed is that the operations on c (jo ,1) , ci( o ,2) — are defined constants, CPS state parameters measurement, through restrictions over control actions ui(γe )j are characterizing the hardware restrictions, , related to CPS functioning in general; εij (t ) — directly connected to MCO, implemented by the known matrix time function, whereby the CPS, specified in the model Мо. This allows to spatitemporal restrictions are set, related to research the task on scheduling MCO procedures of data collecting, transmitting and interaction of objects Bi (or Bk ) with B j , this processing, and the tasks on scheduling function receives the value 1, if Bi gets into measurements of the controlled objects the defined zone of interaction B j ; 0 — in the parameters from unified system positions. opposite case. Quality evaluation of CPS MCO The dynamic model for controlling programme control processes (or, in other interaction operations (including computation words, quality of MCO operational operations) in CPS (model Мe). scheduling) can be conducted using various =Me {= (e) u (t ) | x (g) F (t )x ; т i (g) i (e) (g) i objective functions. Let us introduce some of them: = (i ) y (t ) d (t )x j j i +ξ ; j 1 m si tf m m d jd т (2) =J1( o ) ∑∑ {[ai(γo ) − xi(γo ) (t f )]2 + ∑ ∫ ηiγ (τ)ui(γo )j (τ)d τ}, i ≠ j; (3) − Z i Fi − Fi т Z i − ∑ ∑ ui(γe )j Zi = 2 =i 1 γ= 1 j ; =j 1 t0 j= 1 γ∈Γ  i σ 2   j J 2( e ) = bγT K i (t f )bγ ; } i ≠ j; i, j ∈ M ; 0 ≤ ui(γe )j ≤ c (jeγ) ui(γo )j , tf (4) m m ∑∑ ∑ ∫ u γ (τ )dτ , j ≠ i, (5) (g) with x i — state vector of OS Bi ; Fi(t) — is =J 3( e ) (e) i j =i 1 =j 1 γ∈D (i ) t0 the specified matrix, characterizing the dynamic of variable change (computed with ηiγ (τ) — known monotone functions of parameters), describing OS state (i.e., their time, that are selected taking into spatial position or aircraft systems state§); ξ(je ) consideration the given scheduled time frames — uncorrelated errors of SO parameters of the start (finish) of implementing OS of measurements, that are conducted by CPS MCO with CPS Bi . The indicator (3) is technical means B j ; it is supposed that introduced in case it is necessary to evaluate measurement errors comply with the normal depth of boundary conditions fulfillment, as distributive law with zero mathematical well as the value of total fine for not expectation and dispersion equal to σ2j ; implementing the operations specified scheduled time frames. For OS, where we Dγ(i ) ∈ D (i ) ; ui(γe )j (t ) — control action, defining consider instrumental complexes, aimed at intensity of SO measuring parameters y (ji ) (t ) solving tasks on monitoring specified (i.e. distance to SO, temperature and humidity environmental objects (SEO) state, the aboard SO), that are conducted in the remote operations, related to evaluation of their mode with technical means of CPS B j ; ci(γe ) — position, that therefore allow to define SEO position, have the special significance. specified values, characterizing technological Thereby the value of quality indicator (4) capabilities of means B j while implementing characterizes the determination accuracy of χ operation Dγ(i ) ; Z i — matrix, reciprocal to –й component of vector xi( g ) ( correlation matrix K i (t ) of errors in evaluating  bχ = 0 0...1...0 0 — T specified intermediate state vector OS Bi ; Γi — a set of interaction vector, which defines the required element operations, conducted by CPS with OS Bi ; with number χ in the correlation matrix K i (t ) d j (t ) — given vector, that defines ). Objective function of type (5) allows to specifications of measuring tool equation provide quantitative evaluation for CPS technical implementation of CPS B j ; K i 0 — resources consumption while implementing value K i at the start time t = t0 ; σ2γ i — operations Dγ(i ) , related to OS state changes. specified determination accuracy χ -й of the Further, let us provide formal problem statement on scheduling MCO, implemented state vector component xi( g ) (t ) OS. The major by CPS. It is required to find such admissible control, that answers the required limitations and transfers the dynamic system from the specified initial state into the specified final state. In case there are several such control actions (complex plans), it is required to select the best possible (optimal) among them, ensuring that components of the generalized vector take extreme values. Previously the works [12,13] demonstrated, how it is possible to narrow down the task on scheduling operations and distributing resources in complex technical objects to two- point boundary value problem, applying Boltyansky’s method of local sections. In this case the task on MCO scheduling is Figure 1: The results on heuristic and optimal formulated as task on searching for optimal scheduling of MCO, implemented by CPS programme control, that ensures required determination accuracy of CPS and OS Application of this approach allows to position within minimum time frames (or with reduce the amount of unprocessed minimum power consumption from MCO informational flows by 20%; eliminate implementation) [14]. Traditionally, the tasks unbalanced resources consumption; reduce of this class (tasks of scheduling theory) are interruptions of scheduled time in operation solved applying the method of mathematical implementation by 17%; increase the programming [5,11,15]. The suggested usage generalized quality indicator by 19%. of methods for theory of optimal control in Moreover, additional researches of order to solve tasks of the scheduling theory processes on implementing measuring allows to improve the quality of scheduling operations, related to evaluation of various results (including increase of efficiency on factors influence on the mentioned factors, plans development, reduction in energy were held. The graphs (Fig. 2, Fig. 3) show, consumption within its implementation, etc.) that for each OS with a new interaction session [5, 16]. with CPS the accuracy of measurement of its position parameters increases. 4. Results analysis on solving scheduling of measuring and computing operations in CPS The search for a MCO complex plan is implemented in two stages. At the first stage in order to initialize the generalized procedure for measuring and computing operations optimization there was an admissible heuristic plan synthesized. In order to implement it the well-known FIFO algorithm (“first in, first out”) was used. At the second stage the multi- Figure 2: The graph of coordinate measurement step procedure for solving the two-point errors change, depending on the service session for boundary value problem was conducted, to various OS which the initial nonclassical task on calculus of variations was narrowed. The results of two stages implementation are shown in Fig. 1. Within the second group of experiments the parameters of measuring tool disperison were sequentially reduced by half (Fig. 4). The graph shows that the influence of measuring tool dispersion parameters in a lesser extent affects the results of measurements optimization. Figure 3: The graphs for coordinate measuring errors change, depending on the interaction session for a selected OS In order to evaluate the influence of changing various parameters on measurement accuracy 2 groups of experiments were conducted, within which the coefficients, that are referred to errors cross-correlation matrix Figure 5: Graph of the conducted experiments and measuring instrument dispersion were results with change in CPS measuring tool changed. dispersion parameters In the first group experiments were In all the conducted experiments identical sequentially held with changing coefficients, consistency of measurement quality included into correlation errors matrix. In each improvement with each new session of OS of the experiments the coefficients of errors interaction with CPS is observed. correlations were sequentially reduced over all parameters. The experiments results are shown 5. Conclusion in Fig. 4. The article provides a polymodel description and results of solving task on planning MCO of CPS. The main features and differences between the suggested models are that within dynamic interpretation of MCO, included into CPS technological cycle, processes implementation, the dimension of the solved scheduling tasks and strength of association in scheduling algorithm are notably reduced. This dimension is defined within solving scheduling task at each time point by a number Figure 4: Graphs of coordinate measurement errors of independent tracks in the general network change, depending on the interaction session for a graph, implemented by CPS, by current selected OS spatiotemporal, technical, technological The graph (Fig. 4.) shows, that reduction of restrictions. coefficients in the errors correlation matrix The studies on the developed models leads to improvements in the measurement features and characteristics showed, that by quality. means of CPS operation rational (optimal) The results show, that after optimization scheduling, firstly, the general capacity of CPS process the gained amount of measuring increases and, secondly, CPS resource information is received within shorter period consumption for MCO implementation of time. It should be also mentioned that, reduces, and as well time lags in CPS control provided there are the largest values in the paths reduce, thirdly, there is a reduction of correlation matrix of measuring tool errors, the peak informational loads within sudden largest improvement in measuring quality is changes of CPS structure. Moreover, based on observed as a result of optimization. dynamic description of CPS functioning processes, it is possible to explicitly connect [8] V. Kupriyanovsky, D. Namiot, S. Sinyagov, its elements and subsystems control Cyber-phisical systems as a base for digital technology with results of target application of economy. International Journal of Open instrument complexes, implementing data on Information Technologies (2016) 18-24. [9] W. Shijie, Z. Yingfeng, Z. A credit-based SEO reception, processing and analysis, as dynamical evaluation method for the smart well as with characteristics of CPS hardware configuration of manufacturing services under and software complexes. MCO complex Industrial Internet of Things. J Intell Manuf scheduling offers interesting prospects on 32, (2021) 1091–1115. forming justified requirements to CPS characteristics. In [17] information is provided [10] V. V. Zakharov, Dynamic interpretation of about multiple ways to apply the suggested formal description and solution of the approach in practice in order to solve tasks of problem of complex object modernization. scheduling theory, emerging in various subject Journal of Instrument Engineering. (2019) fields (space technology, shipbuilding, state 914-920. doi: 10.17586/0021-3454-2019-62- 10-914-920 administration, etc.). [11] R. Csalodi, Z. Süle, S. Jaskó, T. Holczinger, J. Abonyi, Industry 4.0-Driven Development of 6. Acknowledgements Optimization Algorithms: A Systematic Overview. Complexity, (2021) 1-22. The research described in this paper is [12] L.S. Pontryagin, V.G. Boltyanskiy, R.V. partially supported by the Russian Foundation Gamkrelidze, E.F. Mishchenko, The Mathematical Theory of Optimal Processes. for Basic Research (19–08–00989, 20-08- Oxford. Pergamon Press (1964). 01046), state research 0073–2019–0004. [13] V. N. Kalinin, B. V. Sokolov, A dynamic model and an optimal scheduling algorithm References for activities with bans of interrupts. Automation and Remote Control (1987) 88– [1] A. A. Teilans, A. V. Romanovs, Y. A. 94. Merkuryev, P. P. Dorogovs, A. Y. Kleins, and [14] E.B. Lee, L. Markus. Foundations of optimal S. A. Potryasaev, Assessment of Cyber control theory, 1967. Physical System Risks with Domain Specific [15] V.S. Tanayev, V.V. Shkurba, Introduction to Modelling and Simulation, SPIIRAS Scheduling Theory, 1975. Proceedings (2018) 115-139. [16] M.Yu. Okhtilev, B.V. Sokolov, R.M. doi:10.15622/sp.59.5 Yusupov. Intellektual'nye tekhnologii [2] W. Wolf, Cyber-physical Systems. Computer, monitoringa i upravleniya strukturnoy (2009) 88-89. doi: 10.1109/MC.2009.81. dinamikoy slozhnykh tekhnicheskikh [3] D. Ivanov, B.V. Sokolov, A. Dolgui. ob"ektov (Intellectual Technologies of Introduction to Scheduling in Industry 4.0 and Monitoring and Management of Structural Cloud Manufacturing Systems. In: Sokolov Dynamics of Complex Technical objects) B., Ivanov D., Dolgui A. (eds) Scheduling in (2006). Industry 4.0 and Cloud Manufacturing. [17] Laboratory of Information Technologies in International Series in Operations Research & System Analysis and Modeling, Management Science, (2020). http://www.litsam.ru, last accessed https://doi.org/10.1007/978-3-030-43177-8_1 2021/06/06. [4] Li Da Xu, Eric L. Xu & Ling Li Industry 4.0: state of the art and future trends, International Journal of Production Research (2018) 2941- 2962. doi:10.1080/00207543.2018.1444806 [5] D. F. Rossit, F. M. Tohmé, M. Frutos. Industry 4.0: Smart Scheduling, International Journal of Production Research, 57(12), (2019) 3802-3813. [6] R. M. Yusupov, A. A. Musae. Efficiency of Information Systems and Technologies: Features of Estimation. SPIIRAS Proceedings. 2, (2017) 5-34. [7] R.L. Ackoff, The art of problem solving, 1978.