# An Optimal Scheduling Method for Data Resources of Production Process Based on Multicommunity Collaborative Search Algorithm

Authors: Yanlei Yin; Lihua Wang; Jun Tang; Wanda Zhang; Hongwei Niu
Journal: Journal of Sensors
 (2022)

---

## Abstract

Aiming at the problem of low response speed and unbalanced distribution of data resources of production process (DRPP) for the distributed workshop production environment, an optimization scheduling method of DRPP based on a multicommunity cooperative search algorithm is proposed. A heuristic data resource service scheduling framework including a load manager and dynamic scheduling engine is first built to deal with the uncertainty of data resource service response and the imbalance of resource allocation; a core scheduling optimization mathematical model with the objectives: resource service efficiency, reduced response time, and load balancing, is established. Then, a multicommunity cooperative search algorithm for the scheduling model is presented, and the mapping relationship between the particle position vector and resource allocation is established via binary coding. Thus, the optimization algorithm is mapped to discrete data space, and the multicommunity bidirectional driving evolutionary mechanism is used to realize the cooperative and interactive search between common and model community, which enhances the adaptability of the algorithm to dynamic random scheduling tasks. Finally, the effectiveness of the proposed method is verified by an example of multiprocess quality prediction service scheduling in silk production process, which provides an effective means for solving the complex scheduling problem of production process data.


---

## Body

## 1. Introduction

The intelligent workshop integrates modern sensing technology, network technology, automation technology, and other advanced technologies, and a large number of intelligent equipment such as sensors and data acquisition devices have been put into use in the workshop [1–3]. And thus, the production workshop has become the collection center of information flow, material flow, and control flow. In the process of product production, a large amount of production, environment, status, and equipment operation data are generated at an unprecedented speed, thus forming workshop big data, which presents the new characteristics of multitask, cross-process, heterogeneous, and polymorphic. However, data has no subjective initiative. To realize the real-time perception and prediction of the production process, we must first realize the scheduling and optimization of “data,” that is, the scheduling and optimization of production process data. It is noted that the traditional manufacturing mode, data of information flow, material flow, and control flow are still isolated from each other in each stage of production execution, and it is difficult to form a joint force due to the lack of effective data resource scheduling mechanism, which restricts the further improvement of production efficiency and system intelligence level [4]. Therefore, the research on on-demand scheduling of workshop data resources is one of the core problems of intelligent manufacturing in production workshop.Recently, most scholars at home and abroad focus on the methods and algorithms of workshop data collection, analysis and mining, such as machine vision preprocessing algorithm [5], neural network prediction algorithm [6, 7], intelligent decision algorithm [8], and multiobjective optimization algorithm [9]. However, the data have no subjective initiative; the data-based analysis and processing algorithm can not actively serve the business needs such as perception, decision-making, and execution of the production process; and the current research has not comprehensively considered the coupling and impact among demand, service, resources, and energy efficiency in the production process.However, the research of domestic and foreign scholars on workshop process production scheduling and collaborative job scheduling has a good reference for the development of this work. Considering workshop process and production scheduling, literature [10] based on the dependence of the production planning, and scheduling problem of continuous production line on timing, a repair and optimization solution is proposed to solve the problem of energy efficiency in the production process. For the scheduling problem of complex products in multiworkshop production, literature [11] studies the characteristics of BOM structure and process route of complex products. Based on the construction of multilevel process network diagram, an improved particle swarm optimization algorithm is used to ensure the effectiveness of the algorithm search path. Literature [12] considers the problems of process connection and blocking of prefabricated parts in the process of workshop assembly line operation and establishes a scheduling model to minimize the total penalty cost of advance and delay, which improves the production efficiency of Prefabrication Yard. Literature [13] uses a machine learning method to assign jobs based on the priority rules of the decision tree as the scheduling method, which shows good performance in the case scenario with completion goal and total delay goal. Considering from workshop production collaborative job scheduling, Literature [14] estimates the process processing time in the production process through machine learning and uses the estimated processing time to schedule and optimize parallel machines, which reduces the maximum completion time by about 30% on average. Aiming at the optimal comprehensive production and transportation plan of a group of parallel batch machines, literature [15] constructs a 0-1 mixed integer programming model, solves the model, and completes the comprehensive scheduling through an improved genetic algorithm, which reduces the transportation cost. The above research provides an idea for this paper to realize on-demand scheduling data resources for production process.On the other hand, it should be noted that the workshop production process involves multiprocess cross-production line business collaboration and business requirements. In the process of data resource scheduling, we should not only consider the association and cooperation relationship between different production tasks but also consider the transmission time of data resources between different production tasks, in particular, the uncertainty of concurrent service access affecting demand response, and the impact of these dynamic and uncertain factors on the balance of data resource allocation [16–18].This paper is concerned with production-oriented data resources scheduling, thus transforming DRPP into a service, and finally into economic benefits. Consequently, this study is to integrate the load manager and dynamic task scheduling engine, and combine them with scheduling processes to form a scheduling scheme, so as to provide intelligent support for production process. Following this idea, this paper is organized as follows: the heuristic data resource service scheduling framework is constructed in Section1. The problem to be studied and the scheduling mathematical model are proposed in Section 2. Section 3 is devoted to establish the asynchronous parallel scheduling strategy and optimization method, simulation results are given in Section 4, and conclusions are made in Section 5.


## 2. DRPP Scheduling Process Analysis

According to the execution status of the DRPP in the scheduling center, the data in the resource pool are mobilized to form the optimal execution scheme of tasks. DRPP scheduling is one of the key links in the production decision process. Figure1 presents a framework of DRPP scheduling that includes decomposition of business requirements, service task analysis, dynamic scheduling of DRPP, load monitoring, and service task execution. Firstly, during production operation, different processes send requests to the scheduling center according to task execution requirements. By queuing, merging, and analyzing the service requirements, the task analyzer degrades the vague and miscellaneous service tasks to form a set of low-granularity service tasks that can be directly served by DRPP. Secondly, the dynamic scheduler preliminarily matches the DRPP according to the task request and then matches the execution task characteristics with the static and real-time attributes of the DRPP to obtain the DRPP set that meets the current production business requirements. The load supervisor of the scheduling center dynamically adjusts the DRPP by monitoring the operation and load of the DRPP in the business process and solves the service interruption caused by uncertain events to ensure the accomplishment of the service process. Finally, the DRPP scheduling engine uses the integrated intelligent optimization algorithm to combine and match the state information of the DRPP and the real-time information of the service task to form the optimal resource service allocation scheme and submits it to the center for execution, so as to complete the scheduling process of the resource service.Figure 1
Scheduling process of DRPP.Throughout the entire scheduling process, multiservice tasks are executed interactively, and there is a complex relationship between tasks. With the dynamic growth of production business scale, the response time of service tasks must be considered. Additionally, a large number of dynamic and uncertain factors will seriously affect the ability and effectiveness of DRPP service scheduling. The traditional resource scheduling method has low search efficiency and accuracy, which can easily lead to the problems of low response speed and the uneven distribution of resources in the service process. It is difficult to adapt to the allocation of STRs on demand. Therefore, this paper considers improving service efficiency while solving the problem of the unreasonable allocation of DRPP caused by the uncertainty of service response and the unbalanced load of nodes.


## 3. The Multiobjective Optimal Scheduling Model of DRPP

### 3.1. The Response Uncertainty Modeling

The invocation relationship of DRPP in the business process is complex, especially when a data resource service is invoked by multiple business processes, and these business processes run simultaneously; there will be concurrent access. In different service scenarios, there are some fluctuations and uncertainties in the access frequency, concurrency probability, and response time of users in the entity industry. There are certain fluctuations and uncertainties in the access frequency, concurrency probability, and response time of different business links in the production process, such as sequence, selection, parallelism, and the cycle of business processes [19, 20]. Therefore, the uncertainty of the service response of DRPP can be described by service access frequency.In the following formula,k represents the number of service tasks. l represents the total DRPP resources. p represents the process of any service tasks. θ represents the probability of performing service task i. μ represents the probability of invoking DRPP j for the service task i. ε represents the probability of a service business being accessed. γ represents the probability of any process branch being selected.Assuming that there arej DRPP for I subtasks to call when the scheduling center performs a certain service task, and these subtasks are completed on a specific node according to the service process; then, the probability that the process of the service task is executed is
(1)ε=∑j=1l∑i=1kθμ1≤i≤I1≤j≤J.When multiservice tasks are executed interactively, concurrent access often occurs in service invocation. Accomplishing a task involves invoking multiple resource service processes. When there is a selection structure in the process and a process branch covers concurrent access services, the probability of concurrent access to services is as follows:(2)Ρca=∑p=1pεγ1≤p≤L.When all the selected branches in the service process cover the current concurrent access service, the probability of concurrent access to the services is(3)Ρca=∑p=1pε1≤p≤L.


### 3.2. The Modeling of Unbalanced Resource Allocation

Suppose a service taskΩ=t1,t2,⋯,tn needs to call k subtasks to complete, the total number of the DRPP that can provide services is l. These subtasks are completed in different tasks node according to the service process and resource requirements. The expected completion time of task ti invoking technology resource rj is defined as
(4)Tij=ILiESj,where ILi is the total instruction length of service task ti and ESj is the execution speed that the DRPP rj are distributed invocation.The average load ofk different service tasks scheduling l DRPP is defined as the quotient between the total instruction length of k service tasks and the total execution speed of l data resources distributed scheduling, i.e., the completion time of the total service task is
(5)Tt=∑i=1kILi∑j=1lESj.For the above scheduling scheme, the load balancing of service resources invoked can be defined as(6)σ=l‐1∑j=1lTtj−Tt2,where Ttj represents the completion time of the service task j. Obviously, a smaller σ indicates a more balanced task load service scheduling.


### 3.3. The Multiobjective Optimal Scheduling Model

Considering the DRPP response and the unbalance of resource allocation, this paper established a multiobjective optimal scheduling mathematical model including the service efficiency, response time, and load balance of resource invocation.In the production process, ifeji represents the state of service node i performing subtask j, N represents the subtasks, and M represents the total number of DRPP provided by service tasks; then, the state set of resource services is E=ejiM×N, 1≤i≤M,1≤j≤N. The set of service efficiency is Se=sejiM×N,1≤i≤M,1≤j≤N, the response frequency set is Rt=rtjiM×N,1≤i≤M,1≤j≤N, and the load balancing set is δ=σjiM×N1≤i≤M,1≤j≤N. In these equations, seji is the service efficiency of service node i executing scheduling task j, rtji is the response time of executing resource scheduling task j for service node i, and σji is the service efficiency load balancing of resource scheduling task j for service node i. The service status of any resource service node executing a task can then be expressed as
(7)eji=seji,rtji,σji.The set of DRPP mapped byN service tasks is X=x1,x2,⋯,xN, where x is a DRPP invoked for a service subtask. Thus, the mathematical model of multiobjective optimal scheduling considering the uncertainty of service response and the imbalance of resource allocation is as follows:
(8)minFx=X,E=Sex,Rtx,δx,s.t.xj∈Randx≤M,seji≥semin,0≤rtji≤rtmax,0≤σji≤σmax,where semin is the minimum service efficiency value in line with business requirements, rtmin is the maximum service response time that a DRPP node can take, and σmax is the highest load balancing of a DRPP node.Set the weights of the service efficiency, load balancing, and response frequency of user requesting DRPP asωSe, ωRt, and ωδ, respectively, and ωSe+ωRt+ωδ=1.The optimal scheduling model of DRPP considering the target weight of user demand is as follows:(9)Fx=ωSeSeX+ωRtRtX+ωδδX.


## 3.1. The Response Uncertainty Modeling

The invocation relationship of DRPP in the business process is complex, especially when a data resource service is invoked by multiple business processes, and these business processes run simultaneously; there will be concurrent access. In different service scenarios, there are some fluctuations and uncertainties in the access frequency, concurrency probability, and response time of users in the entity industry. There are certain fluctuations and uncertainties in the access frequency, concurrency probability, and response time of different business links in the production process, such as sequence, selection, parallelism, and the cycle of business processes [19, 20]. Therefore, the uncertainty of the service response of DRPP can be described by service access frequency.In the following formula,k represents the number of service tasks. l represents the total DRPP resources. p represents the process of any service tasks. θ represents the probability of performing service task i. μ represents the probability of invoking DRPP j for the service task i. ε represents the probability of a service business being accessed. γ represents the probability of any process branch being selected.Assuming that there arej DRPP for I subtasks to call when the scheduling center performs a certain service task, and these subtasks are completed on a specific node according to the service process; then, the probability that the process of the service task is executed is
(1)ε=∑j=1l∑i=1kθμ1≤i≤I1≤j≤J.When multiservice tasks are executed interactively, concurrent access often occurs in service invocation. Accomplishing a task involves invoking multiple resource service processes. When there is a selection structure in the process and a process branch covers concurrent access services, the probability of concurrent access to services is as follows:(2)Ρca=∑p=1pεγ1≤p≤L.When all the selected branches in the service process cover the current concurrent access service, the probability of concurrent access to the services is(3)Ρca=∑p=1pε1≤p≤L.


## 3.2. The Modeling of Unbalanced Resource Allocation

Suppose a service taskΩ=t1,t2,⋯,tn needs to call k subtasks to complete, the total number of the DRPP that can provide services is l. These subtasks are completed in different tasks node according to the service process and resource requirements. The expected completion time of task ti invoking technology resource rj is defined as
(4)Tij=ILiESj,where ILi is the total instruction length of service task ti and ESj is the execution speed that the DRPP rj are distributed invocation.The average load ofk different service tasks scheduling l DRPP is defined as the quotient between the total instruction length of k service tasks and the total execution speed of l data resources distributed scheduling, i.e., the completion time of the total service task is
(5)Tt=∑i=1kILi∑j=1lESj.For the above scheduling scheme, the load balancing of service resources invoked can be defined as(6)σ=l‐1∑j=1lTtj−Tt2,where Ttj represents the completion time of the service task j. Obviously, a smaller σ indicates a more balanced task load service scheduling.


## 3.3. The Multiobjective Optimal Scheduling Model

Considering the DRPP response and the unbalance of resource allocation, this paper established a multiobjective optimal scheduling mathematical model including the service efficiency, response time, and load balance of resource invocation.In the production process, ifeji represents the state of service node i performing subtask j, N represents the subtasks, and M represents the total number of DRPP provided by service tasks; then, the state set of resource services is E=ejiM×N, 1≤i≤M,1≤j≤N. The set of service efficiency is Se=sejiM×N,1≤i≤M,1≤j≤N, the response frequency set is Rt=rtjiM×N,1≤i≤M,1≤j≤N, and the load balancing set is δ=σjiM×N1≤i≤M,1≤j≤N. In these equations, seji is the service efficiency of service node i executing scheduling task j, rtji is the response time of executing resource scheduling task j for service node i, and σji is the service efficiency load balancing of resource scheduling task j for service node i. The service status of any resource service node executing a task can then be expressed as
(7)eji=seji,rtji,σji.The set of DRPP mapped byN service tasks is X=x1,x2,⋯,xN, where x is a DRPP invoked for a service subtask. Thus, the mathematical model of multiobjective optimal scheduling considering the uncertainty of service response and the imbalance of resource allocation is as follows:
(8)minFx=X,E=Sex,Rtx,δx,s.t.xj∈Randx≤M,seji≥semin,0≤rtji≤rtmax,0≤σji≤σmax,where semin is the minimum service efficiency value in line with business requirements, rtmin is the maximum service response time that a DRPP node can take, and σmax is the highest load balancing of a DRPP node.Set the weights of the service efficiency, load balancing, and response frequency of user requesting DRPP asωSe, ωRt, and ωδ, respectively, and ωSe+ωRt+ωδ=1.The optimal scheduling model of DRPP considering the target weight of user demand is as follows:(9)Fx=ωSeSeX+ωRtRtX+ωδδX.


## 4. The Optimal Scheduling Algorithms of DRPP Based on Multicommunity Collaborative Search

### 4.1. The Evolution Model of Multicommunity Cooperative Network

The basic particle swarm optimization (PSO) algorithm is a single-community optimization model with global optimal particles as its core, which cannot solve the mixed and changeable scheduling problem very well. If this model is extended to task-related multicommunity cooperative optimization, the evolutionary information interaction and association will be generated among these communities, and then, a multicommunity cooperation network (MCCN) with high adaptability to the task will be formed [21, 22]. From a mathematical point of view, a network can be regarded as a combination of a vertex set and edge set. To better describe MCCN and establish its evolution model, the following definitions are first provided.Definition 1.
The thresholdFT for community type determination is
(10)FT=∑i=1nFin,where Fi is the global optimal fitness of community i and n is the number of communities in the cooperative network.According to the thresholdFT of community type determination, the particle community in the collaboration network can be divided into the model community and common community. If Fi satisfies the criterion Fi≥FT, the community has a strong ability of local optimization, which can be divided into model communities and recorded as MCi. On the contrary, if Fi satisfies the criterion Fi<FT, the community has a strong ability of global exploration, so it can be divided into common communities and recorded as CCi.Definition 2.
Let the cooperative search activity among different communities be a binary groupC,R, where C=c1,c2,⋯cj,⋯cn1≤j≤n is the sequence of communities participating in the cooperative search activity and R:C×C is the interdependency among communities in the search process. ∀rs:ci,cj∈R,s=1,2,3 is called the cooperative relationship unit, where r1 represents the cooperative relationship between a model community and a common community, r2 is the cooperative relationship between any two model communities, and r3 is the cooperative relationship between any two common communities. The number of cooperative units among different communities in a cooperative relationship set is called the module of the cooperative relationship set, which is recorded as R.Generally, ifrsc1,c2=1, there is an edge between two cooperative communities, and the more cooperative relationship units, the greater the edge weight between two different nodes. If there is no cooperative relationship between different communities, then rsc1,c2=0.Definition 3.
Letωi,j=∑s=1Rrsc1,c2 be the cooperative weights among different communities in MCCN, where the cooperative weight between ci and cj is also called the edge weight of MCCN.To complete the comprehensive quantitative evaluation of community nodes, the evaluation indexes of the optimum valuegbesti of community nodes are introduced: collaboration distance Hi and responsivity ei.Definition 4.
Collaboration distance. The global optimal valueGbesti of the community i is, respectively, compared with the individual optimal position pbestj of the m particles, and the absolute value is obtained, that is to say, the cooperative distance of the global optimal value Gbseti is Hi=h1,h2,⋯,hm.Definition 5.
Responsivity. The thresholdD of the qualified distance is set. According to the formula evi=0,hi>D,1,hi<D,, the response value of the community particle to the optimal value gbesti of the node can be obtained by traversing the cooperative distance Hi, and then, the responsivity ei of the global optimal value Gbesti can be obtained by adding the response values in sequence.Definition 6.
Community node strength. In MCCN, the strength of the community nodes is defined assi(11)si=∑cj∈Ujωij+eiwhere ωij is the cooperative weight between the community node ci and cj, ei is the responsivity of the community node, and Ui is the neighborhood of the community node ci, and it satisfies
(12)Uicj∨s=1Rrsci,cj≠0.Generally, MCCN can be represented by its adjacency matrix asAGn×n=Bn×n. If En×1=e1,e2,⋯,en is the responsivity matrix of MCCN, then the node strength matrix is as follows: Sn×1=ω11AG11+ω12AG12+⋯ω1nAG1n+e1,ω21AG21+ω22AG22+⋯ω2nAG2n+e2,⋯,e1,ωn1AGn1+ωn2AGn2+⋯ω11AG11+en.Definition6 shows that the strength of community nodes not only takes into account the cooperative weights among the nodes of the community but also the optimization of the particles within the node itself. It is a comprehensive evaluation of the community’s local information and the ability of the community itself, which can better reflect the community’s ability to seek optimal guidance in the entire cooperative network.Therefore, MCCN can be represented by undirected weighted graphsGC,R,W,S. C=c1,c2,⋯,cn represents different types of cooperative community node set, R=r1c1,c2,r2c1,c2,⋯,rkc1,c2,⋯,rsc1,c2 represents cooperative relationship edge set, W=ω11,ω12,⋯ωij,⋯ωnn1≤i,j≤n is the cooperative edge weight set among, and S=s1,s2,⋯,sn is the strength set of community nodes, where si is the value of the i-th row of the node strength matrix, representing the attributes of community nodes to measure their search ability. By Definition 6, MCCN can be expressed by adjacent augmentation matrix M as follows: MG=B,En×n+1. The evolution model of the MCCN cooperative network is therefore
(13)Bn×n=Bi,jn×n=ω,∨s=1Rrsci,cj=1,rs∈R,0,∨s=1Rrsci,cj=0,ori=j,rs∈R.On this basis, the asynchronous parallel search strategy among different communities is formulated to reduce the communication between communities, and the efficient search is realized through the driving evolution mechanism to improve the optimization ability of the algorithm to the task scheduling. The rules of multi-population coevolution are as follows.Rule 1. Evolutionary rules within microbial communities. In the process of multicommunity coevolution, the particles in a single community can be iteratively optimized according to formula (13) for speed and location updating, and the global optimum value can be generated within the community.
(14)vidt+1=ω⋅vidt+c1⋅r1⋅Pidt−xidt+c2⋅r2⋅Pgdt−xidt,xidt+1=xidt+vidt+1,i=1,2,⋯,m,d=1,2,⋯,D,where t is the number of iterations of particle search, ω is the inertial weight, c1=c2=2 is the acceleration constant, and r1 and r2 are two random functions varying in the range of 0,1.Rule 2. Driving coevolution rules between communities.Rule 2.1.∀r1:CCi,MCj∈R, ∃gbesti=maxgbest1,gbest2,⋯,gbestm, Gbestj=minGbest1,Gbest2,⋯,Gbestn, and gbesti≥Gbestj. The common community is CC, and the model community is MC. The particulate CCi in CC enters MC, and the last community MCj in MC is eliminated. After introducing the model learning factor pn into the internal evolution rules of CC, the new iterative evolution formula is as follows:
(15)vidt+1=ω⋅vidt+c1⋅r1⋅Pidt−xidt+c2⋅r2Pgdt−xidt+c3Pndt−xidt,xidt+1=xidt+vidt+1,i=1,2,⋯,m,d=1,2,⋯,D,where Pnd=∑i=1nGbesti/n and c3 is a random function and satisfies the convergence constraints c1r1+c2r2+c3∈0,4.Rule 2.2.∀r2:MCi,MCj∈R, ∃ the community node strength SMCi satisfiesSMCi≥SMCj for any SMCj.⇒Global optimum value of model community: PG=Gbesti.Rule 2.3.∀r3:CCi,CCj∈R, ∃ the community node strength SCCi satisfies SCCi≥SCCj for any SCCj.⇒Global optimum value of common community: Pg=gbesti.


### 4.2. The Coding Strategy for Optimal Scheduling of DRPP

Particle swarm optimization (PSO) is a computational model for real continuous space, and it is difficult to solve the task scheduling problem in discrete space [23]. Therefore, the binary system is used to encode the speed and position of particles, and the mapping from the particle swarm optimization algorithm to discrete space, and from the particle search space to the optimal scheduling scheme, is realized by reconstructing the particle expression.In the above algorithm, ann row, n column matrix X:n×n is defined as the position vector matrix of particles. The rows represent the situation of providing STR when any service task is executed, the columns indicate the distribution of service tasks in the scheduling process, and any particle represents the potential solution of the scheduling problem. The coding of the particle position is as follows:
(16)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xn1xn2⋯xnn,where xij∈0,1, ∑j=1nxij=1.According to the coding scheme, each row of the location matrixX has one and only one element value is 1, which indicates that DRPP are allocated to service task R. Each DRPP can be invoked by multiple service tasks simultaneously, and the execution of any scheduling task cannot be interrupted.The defined speedV:n×n is shown in equation (16), which represents the basic exchange order of particle’s assignments to the execution of tasks.
(17)V=v11v12⋯v1nv21v22⋯v2n⋮⋮⋱⋮vn1vn2⋯vnn,vij∈0,1,vij+vji=0or1.The exchange operations of addition, subtraction, multiplication, and division in the algorithm are defined asΘ, θ, ⊗, and ⊕, respectively. The specific operation rules are as follows:
(1)
A⋅θ⋅B: represents ∃xij=vij⇒xij=vij=0 in position matrix A and velocity matrix B; on the contrary, it is 1; ∃xij=vij+n=1⇒vij+n=0(2)
AΘB: indicates ∃xij=vij⇒xij=vij=0 in position matrix A and velocity matrix B; the other elements are randomly chosen as 0 or 1(3)
ci⊗B: indicates whether the particle performs a Θ operation or not with matrix B according to the corresponding probability value of the random number ci(4)
A⊕B: represents ∀xia=1, xjb=1, ∃vij=1⇒xib=1, xja=1 in position matrix A and velocity matrix B. According to the above definition of switching operation rules, formula (10) can be updated as follows:(18)vidt+1=vidtΘc1⊗Pidt⋅θ⋅xidtΘc2⊗Pgdt⋅θ⋅xidt,xidt+1=xidt⊕vidt+1,i=1,2,⋯,m;d=1,2,⋯,DThe coding scheme is simple and feasible and thus meets the requirements of multiservice task scheduling of DRPP. It also clearly describes the mapping relationship between the particle population evolution space and the service task scheduling scheme, thus avoiding repeated searches in the process of particle evolution.


### 4.3. The Optimal Scheduling Algorithms of DRPP Based on Multicommunity Collaborative Search

Based on the multicommunity cooperative search algorithm and its coding scheme, the optimal scheduling process of multiservice tasks for distributed DRPP is shown in Figure2. The specific steps are as follows.Figure 2
Flow chart of scheduling optimization.Step 1. Initialization of population particles. According to the encoding strategy between the particle search space and the task scheduling scheme described in Section3.2, the initialization of n communities is carried out, and a random location (DRPP allocation scheme) and speed of population particles are given. The number of communities, the number of iterations of particles within the community members, and the acceleration coefficient of particles and the inertia weight coefficient are set.Step 2. Initialized population particles are evenly distributed into theq process to form a community of size intn/q. Residual particles are randomly allocated to the q process. The fitness of each particle in the q community is calculated according to the comprehensive optimization scheduling function constructed in Section 3.3.Step 3. Asynchronous parallel evolutionary computation is performed by running each community separately in theq process.Step 4. Calculate the fitness valuesFi of each community and divide all communities into either the model community or common community according to the threshold value.Step 5. According to the interactive evolution mechanism between different particle populations in Section3.1, the position and velocity of particles are updated according to formula (14), and the global optimal locations of the model and common communities are saved to the optimal storage area.Step 6. If all the particle populations satisfy the search termination condition, then the algorithm ends, the global optimal solution is obtained from the storage area, and the optimal scheduling scheme is output; otherwise, it will return to step 5.


## 4.1. The Evolution Model of Multicommunity Cooperative Network

The basic particle swarm optimization (PSO) algorithm is a single-community optimization model with global optimal particles as its core, which cannot solve the mixed and changeable scheduling problem very well. If this model is extended to task-related multicommunity cooperative optimization, the evolutionary information interaction and association will be generated among these communities, and then, a multicommunity cooperation network (MCCN) with high adaptability to the task will be formed [21, 22]. From a mathematical point of view, a network can be regarded as a combination of a vertex set and edge set. To better describe MCCN and establish its evolution model, the following definitions are first provided.Definition 1.
The thresholdFT for community type determination is
(10)FT=∑i=1nFin,where Fi is the global optimal fitness of community i and n is the number of communities in the cooperative network.According to the thresholdFT of community type determination, the particle community in the collaboration network can be divided into the model community and common community. If Fi satisfies the criterion Fi≥FT, the community has a strong ability of local optimization, which can be divided into model communities and recorded as MCi. On the contrary, if Fi satisfies the criterion Fi<FT, the community has a strong ability of global exploration, so it can be divided into common communities and recorded as CCi.Definition 2.
Let the cooperative search activity among different communities be a binary groupC,R, where C=c1,c2,⋯cj,⋯cn1≤j≤n is the sequence of communities participating in the cooperative search activity and R:C×C is the interdependency among communities in the search process. ∀rs:ci,cj∈R,s=1,2,3 is called the cooperative relationship unit, where r1 represents the cooperative relationship between a model community and a common community, r2 is the cooperative relationship between any two model communities, and r3 is the cooperative relationship between any two common communities. The number of cooperative units among different communities in a cooperative relationship set is called the module of the cooperative relationship set, which is recorded as R.Generally, ifrsc1,c2=1, there is an edge between two cooperative communities, and the more cooperative relationship units, the greater the edge weight between two different nodes. If there is no cooperative relationship between different communities, then rsc1,c2=0.Definition 3.
Letωi,j=∑s=1Rrsc1,c2 be the cooperative weights among different communities in MCCN, where the cooperative weight between ci and cj is also called the edge weight of MCCN.To complete the comprehensive quantitative evaluation of community nodes, the evaluation indexes of the optimum valuegbesti of community nodes are introduced: collaboration distance Hi and responsivity ei.Definition 4.
Collaboration distance. The global optimal valueGbesti of the community i is, respectively, compared with the individual optimal position pbestj of the m particles, and the absolute value is obtained, that is to say, the cooperative distance of the global optimal value Gbseti is Hi=h1,h2,⋯,hm.Definition 5.
Responsivity. The thresholdD of the qualified distance is set. According to the formula evi=0,hi>D,1,hi<D,, the response value of the community particle to the optimal value gbesti of the node can be obtained by traversing the cooperative distance Hi, and then, the responsivity ei of the global optimal value Gbesti can be obtained by adding the response values in sequence.Definition 6.
Community node strength. In MCCN, the strength of the community nodes is defined assi(11)si=∑cj∈Ujωij+eiwhere ωij is the cooperative weight between the community node ci and cj, ei is the responsivity of the community node, and Ui is the neighborhood of the community node ci, and it satisfies
(12)Uicj∨s=1Rrsci,cj≠0.Generally, MCCN can be represented by its adjacency matrix asAGn×n=Bn×n. If En×1=e1,e2,⋯,en is the responsivity matrix of MCCN, then the node strength matrix is as follows: Sn×1=ω11AG11+ω12AG12+⋯ω1nAG1n+e1,ω21AG21+ω22AG22+⋯ω2nAG2n+e2,⋯,e1,ωn1AGn1+ωn2AGn2+⋯ω11AG11+en.Definition6 shows that the strength of community nodes not only takes into account the cooperative weights among the nodes of the community but also the optimization of the particles within the node itself. It is a comprehensive evaluation of the community’s local information and the ability of the community itself, which can better reflect the community’s ability to seek optimal guidance in the entire cooperative network.Therefore, MCCN can be represented by undirected weighted graphsGC,R,W,S. C=c1,c2,⋯,cn represents different types of cooperative community node set, R=r1c1,c2,r2c1,c2,⋯,rkc1,c2,⋯,rsc1,c2 represents cooperative relationship edge set, W=ω11,ω12,⋯ωij,⋯ωnn1≤i,j≤n is the cooperative edge weight set among, and S=s1,s2,⋯,sn is the strength set of community nodes, where si is the value of the i-th row of the node strength matrix, representing the attributes of community nodes to measure their search ability. By Definition 6, MCCN can be expressed by adjacent augmentation matrix M as follows: MG=B,En×n+1. The evolution model of the MCCN cooperative network is therefore
(13)Bn×n=Bi,jn×n=ω,∨s=1Rrsci,cj=1,rs∈R,0,∨s=1Rrsci,cj=0,ori=j,rs∈R.On this basis, the asynchronous parallel search strategy among different communities is formulated to reduce the communication between communities, and the efficient search is realized through the driving evolution mechanism to improve the optimization ability of the algorithm to the task scheduling. The rules of multi-population coevolution are as follows.Rule 1. Evolutionary rules within microbial communities. In the process of multicommunity coevolution, the particles in a single community can be iteratively optimized according to formula (13) for speed and location updating, and the global optimum value can be generated within the community.
(14)vidt+1=ω⋅vidt+c1⋅r1⋅Pidt−xidt+c2⋅r2⋅Pgdt−xidt,xidt+1=xidt+vidt+1,i=1,2,⋯,m,d=1,2,⋯,D,where t is the number of iterations of particle search, ω is the inertial weight, c1=c2=2 is the acceleration constant, and r1 and r2 are two random functions varying in the range of 0,1.Rule 2. Driving coevolution rules between communities.Rule 2.1.∀r1:CCi,MCj∈R, ∃gbesti=maxgbest1,gbest2,⋯,gbestm, Gbestj=minGbest1,Gbest2,⋯,Gbestn, and gbesti≥Gbestj. The common community is CC, and the model community is MC. The particulate CCi in CC enters MC, and the last community MCj in MC is eliminated. After introducing the model learning factor pn into the internal evolution rules of CC, the new iterative evolution formula is as follows:
(15)vidt+1=ω⋅vidt+c1⋅r1⋅Pidt−xidt+c2⋅r2Pgdt−xidt+c3Pndt−xidt,xidt+1=xidt+vidt+1,i=1,2,⋯,m,d=1,2,⋯,D,where Pnd=∑i=1nGbesti/n and c3 is a random function and satisfies the convergence constraints c1r1+c2r2+c3∈0,4.Rule 2.2.∀r2:MCi,MCj∈R, ∃ the community node strength SMCi satisfiesSMCi≥SMCj for any SMCj.⇒Global optimum value of model community: PG=Gbesti.Rule 2.3.∀r3:CCi,CCj∈R, ∃ the community node strength SCCi satisfies SCCi≥SCCj for any SCCj.⇒Global optimum value of common community: Pg=gbesti.


## 4.2. The Coding Strategy for Optimal Scheduling of DRPP

Particle swarm optimization (PSO) is a computational model for real continuous space, and it is difficult to solve the task scheduling problem in discrete space [23]. Therefore, the binary system is used to encode the speed and position of particles, and the mapping from the particle swarm optimization algorithm to discrete space, and from the particle search space to the optimal scheduling scheme, is realized by reconstructing the particle expression.In the above algorithm, ann row, n column matrix X:n×n is defined as the position vector matrix of particles. The rows represent the situation of providing STR when any service task is executed, the columns indicate the distribution of service tasks in the scheduling process, and any particle represents the potential solution of the scheduling problem. The coding of the particle position is as follows:
(16)X=x11x12⋯x1nx21x22⋯x2n⋮⋮⋱⋮xn1xn2⋯xnn,where xij∈0,1, ∑j=1nxij=1.According to the coding scheme, each row of the location matrixX has one and only one element value is 1, which indicates that DRPP are allocated to service task R. Each DRPP can be invoked by multiple service tasks simultaneously, and the execution of any scheduling task cannot be interrupted.The defined speedV:n×n is shown in equation (16), which represents the basic exchange order of particle’s assignments to the execution of tasks.
(17)V=v11v12⋯v1nv21v22⋯v2n⋮⋮⋱⋮vn1vn2⋯vnn,vij∈0,1,vij+vji=0or1.The exchange operations of addition, subtraction, multiplication, and division in the algorithm are defined asΘ, θ, ⊗, and ⊕, respectively. The specific operation rules are as follows:
(1)
A⋅θ⋅B: represents ∃xij=vij⇒xij=vij=0 in position matrix A and velocity matrix B; on the contrary, it is 1; ∃xij=vij+n=1⇒vij+n=0(2)
AΘB: indicates ∃xij=vij⇒xij=vij=0 in position matrix A and velocity matrix B; the other elements are randomly chosen as 0 or 1(3)
ci⊗B: indicates whether the particle performs a Θ operation or not with matrix B according to the corresponding probability value of the random number ci(4)
A⊕B: represents ∀xia=1, xjb=1, ∃vij=1⇒xib=1, xja=1 in position matrix A and velocity matrix B. According to the above definition of switching operation rules, formula (10) can be updated as follows:(18)vidt+1=vidtΘc1⊗Pidt⋅θ⋅xidtΘc2⊗Pgdt⋅θ⋅xidt,xidt+1=xidt⊕vidt+1,i=1,2,⋯,m;d=1,2,⋯,DThe coding scheme is simple and feasible and thus meets the requirements of multiservice task scheduling of DRPP. It also clearly describes the mapping relationship between the particle population evolution space and the service task scheduling scheme, thus avoiding repeated searches in the process of particle evolution.


## 4.3. The Optimal Scheduling Algorithms of DRPP Based on Multicommunity Collaborative Search

Based on the multicommunity cooperative search algorithm and its coding scheme, the optimal scheduling process of multiservice tasks for distributed DRPP is shown in Figure2. The specific steps are as follows.Figure 2
Flow chart of scheduling optimization.Step 1. Initialization of population particles. According to the encoding strategy between the particle search space and the task scheduling scheme described in Section3.2, the initialization of n communities is carried out, and a random location (DRPP allocation scheme) and speed of population particles are given. The number of communities, the number of iterations of particles within the community members, and the acceleration coefficient of particles and the inertia weight coefficient are set.Step 2. Initialized population particles are evenly distributed into theq process to form a community of size intn/q. Residual particles are randomly allocated to the q process. The fitness of each particle in the q community is calculated according to the comprehensive optimization scheduling function constructed in Section 3.3.Step 3. Asynchronous parallel evolutionary computation is performed by running each community separately in theq process.Step 4. Calculate the fitness valuesFi of each community and divide all communities into either the model community or common community according to the threshold value.Step 5. According to the interactive evolution mechanism between different particle populations in Section3.1, the position and velocity of particles are updated according to formula (14), and the global optimal locations of the model and common communities are saved to the optimal storage area.Step 6. If all the particle populations satisfy the search termination condition, then the algorithm ends, the global optimal solution is obtained from the storage area, and the optimal scheduling scheme is output; otherwise, it will return to step 5.


## 5. Application Cases and Analysis

In this section, a DRPP scheduling case for the silk production line quality prediction and early warning service are given to validate the proposed model and algorithm. As shown in Figure3, the quality prediction and early warning service include the “ single operation quality prediction and early warning,” “ multiprocess quality prediction and early warning,” “ quality prediction and optimization of the whole production line,” and many other services, where each service activity needs to invoke DRPP using service tasks, such as the modle, standards, algorithm, and component to provide on-demand service for different business links of the the tobacco production line.Figure 3
The DRPP service platform.For the task of quality prediction and optimization of silk drying process service in the service platform, it is divided into five subtasks: online data reading, prediction algorithm call, online real-time prediction, prediction result analysis, optimization algorithm call, and optimization parameter return, which is recorded as task setΩ=t1,t2,⋯,t5. And then, the available DRPP set corresponding to task set Ω isX=x1,x2,⋯,xN. Following the idea proposed in Sections 1 and 2, the DRPP invoking process can be implemented as follows:
(1)
Coding settingsDefine the location vector of the particle in the scheduling algorithm as the matrixX:5×5, as shown in Table 1. Row i represents the allocation of service task ti, and column j represents the service situation of DRPP; if xij=1, it means that the task ti is served by data resources Xj. At this time, each particle represents a service task scheduling scheme.
(2)
Scheduling algorithmsTable 1
Particle encoding diagram.
Sub-tasksResourcesX1X2X3X4X5X6t1x11x12x13x14x15x16t2x21x22x23x24x25x26t3x31x32x33x34x35x36t4x41x42x43x44x45x46t5x51x52x53x54x55x56t6x61x62x63x64x65x66To verify the effectiveness of the presented scheduling method, the simulation experiment is carried out on the service platform based on the Xeon E5-2609V2 processor and RAM64G, and the service efficiency, response time, and load balancing in the process of multiservice task scheduling are collected as sample data. For comparison, the previously reported ERTPSO algorithm [24], DPSO algorithm [25], LAPSO algorithm [26], and the M-CBDCSM algorithm proposed in the present study are used to solve the optimal scheduling scheme for the engine fault identification and maintenance service. The simulation parameters are specified as the population size q=30-500, the dimension 30, the evolutionary algebra i=500, the inertia weight ω=1.1, and the acceleration constant c1=c2=2. Moreover, a random function rand is introduced into the service response time Rtd; Rtd=Rt+n⋅rand, where rand varies randomly in a range 0,1, and n=0,1,2,3. All the simulation experiments were carried out 500 times, and other parameters are the same to those used in the relevant literature.Simulation results of the relevant algorithm are provided in Figure4. It is shown that the multicommunity cooperative search algorithm can better adapt to the random changes of service response time in the process of multiservice task scheduling, in particular for the interactive evolutionary rules between communities are selected adaptively, the algorithm converges to the global optimal value quickly and stably. In particular, the optimal scheduling scheme can be found before 50 generations under different search conditions corresponding to the discrete particle swarm optimization (DPSO). Especially in the face of dynamic and random multitask scheduling, hybrid genetic algorithm is difficult to adaptively carry out individual mutation and cross-operation and then can not track the dynamic change of service scheduling, which makes it difficult to avoid premature phenomenon under high random search conditions, and its algorithm performance is far lower than multicommunity cooperative search algorithm.Figure 4
Comparison of simulation experiments.
(a)
n=0(b)
n=1(c)
n=2(d)
n=3To further validate the strong adaptability of the algorithm in the face of multiple scheduling tasks, the experiments of large population based on multi scheduling tasks is also simulated. For this purpose, the population and the scheduling tasks can be given asp=1000, t=5-20. The corresponding results are provided in Table 2. Although the number of service tasks is increasing, the convergence rate of multi community cooperative search algorithm does not decline significantly in the process of scheduling. From aforementioned results, one can conclude that the proposed algorithms in this paper can achieve better performance for large population and tasks-varying parameters in terms of convergence speed and steady-state errors.Table 2
Comparative experimental results of different task sizes.
Task scaleConvergent algebraOptimal valueStandard deviationAverage error515601.73e−0111.21e−01210151302.81e−0111.61e−01215171851.58e−0102.57e−01220182553.95e−0103.43e−01225183006.12e−0102.69e−011(n=0, iteration=200).


## 6. Conclusion

This paper addresses the multitask adaptive scheduling of DRPP. A heuristic scheduling framework are employed to deal with the uncertainty of DRPP service response and the imbalance of resource allocation. The load manager and dynamic scheduling engine are employed to approximate the uncertainty of scheduling service. Moreover, we propose novel cooperative search algorithm of the task scheduling model driven by scheduling objectives with service efficiency, reduced response time, and load balancing, so that fast scheduling convergence can be proved even in the dynamic random sense. The proposed scheduling schemes are robust against dynamic random disturbances. To guarantee the discrete data space of optimization algorithm, a binary coding strategy to map the particle position vector to resource allocation is introduced. Simulation examples are provided to verify the efficacy of the proposed algorithm.



---

*Source: 2660462-2022-03-12.xml*