# Multiobjective Real-Time Scheduling of Tasks in Cloud Manufacturing with Genetic Algorithm

Authors: Gilseung Ahn; Sun Hur
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

In cloud manufacturing, customers register customized requirements, and manufacturers provide appropriate services to complete the task. A cloud manufacturing manager establishes manufacturing schedules that determine the service provision time in a real-time manner as the requirements are registered in real time. In addition, customer satisfaction is affected by various measures such as cost, quality, tardiness, and reliability. Thus, multiobjective and real-time scheduling of tasks is important to operate cloud manufacturing effectively. In this paper, we establish a mathematical model to minimize tardiness, cost, quality, and reliability. Additionally, we propose an approach to solve the mathematical model in a real-time manner using a multiobjective genetic algorithm that includes chromosome representation, fitness function, and genetic operators. From the experimental results, we verify whether the proposed approach is effective and efficient.


---

## Body

## 1. Introduction

Cloud manufacturing (CM) is an advanced model that provides a cloud-based manufacturing platform on which enterprises virtualize and share their manufacturing services such as welding, milling, and machining to produce highly customized products [1–3]. A task to produce a customized product consists of several activities, and each activity provides a related manufacturing service. The task is processed in the following order [4]. First, a platform manager determines the manufacturing services and an appropriate processing order. This step is called a task definition. The manager then establishes a schedule by selecting services from the platform and determines the start times of each service, considering availability, processing time, and service order. This step, called task scheduling, differs from service allocation in that it considers time [5]. In other words, it allows duplicate assignment of a service (in this case, delay may occur), while service allocation does not. Finally, the task sequence begins processing according to the schedule.Because task scheduling is an important operational problem in CM, many researchers have recently addressed it. Zhou et al. [6] modeled a scheduling problem to minimize the weighted sum of differences between requirement levels and actual levels in terms of time, cost, and quality, and service type is considered a major constraint. They improved a genetic algorithm (GA) to solve the scheduling problem and compared it with particle swarm optimization (PSO) and simulated annealing in an experiment in which each task was given a different weight. They argued that their proposed algorithm outperformed other algorithms in terms of objective value. Cao et al. [7] investigated a task-scheduling problem in terms of time, quality, cost, and service and adopted fuzzy decision-making theory to transform these criteria into degrees of relative superiority. They presented a mathematical model that maximizes the weighted sum of the relative degrees and applied ant colony optimization (ACO) to obtain a solution. Through experiments, they showed that ACO outperformed GA and PSO in every iteration. Liu et al. [8] revealed that workloads affect total completion time, service utilization, and so forth in task-scheduling problems. They compared two scheduling methods based on workload. The first completes the tasks with larger workloads first, while the second completes tasks with smaller workloads first. They concluded that the first method yields a superior performance. Jiang et al. [9] addressed a task-scheduling problem in CM that specializes in disassembly, with the objective of minimizing both total expected makespan and cost. They designed a multiobjective algorithm using the nondominated sorting genetic algorithm II (NSGA-II) to solve the task-scheduling problem. Li et al. [10] studied a task-scheduling problem for distributed robots in CM in which tasks were scheduled by allocating a robot to a subtask, considering geographical location. They solved the problem from three perspectives: difference of workload among robots, overall cost, and overall processing time with a GA.Although previous research investigated task scheduling from multiple perspectives, the chosen approaches were unrealistic in terms of multiobjective and real-time characteristics. Scheduling problems should consider two or more objectives simultaneously. Some researches such as in [6] considered multiple objectives as a weighted sum, but they also were not practical as it proved difficult to choose the proper weight. Only a few (e.g., [9]) considered simultaneous objectives, when modeling the scheduling problem. In addition, the proper services should be used in real-time process (sub) tasks whenever they are registered because this aspect is an important characteristic of CM platform operations.Meta-heuristic algorithms have been frequently employed to solve computational engineering problems [11–17]. For example, Hoang [11] integrated history-based adaptive differential evolution and linear population size reduction to find the optimal hyperparameters of the support vector machine for pitting corrosion detection. Chen et al. [12] developed a hybrid of variable neighborhood search (VNS) and estimation of distribution algorithm (EDA), called VNS-EDA, to compose the feature subset for credit risk classification. Jiang et al. [18] improved particle swarm optimization (PSO) by integrating with the gravitational search algorithm with dependent random coefficients. Peng et al. [19] introduced chaotic search for the fuzzy neural network to improve PSO to handle complex engineering problems.A GA is one of the most famous meta-heuristic algorithms to solve diverse scheduling problems such as project scheduling [20, 21], job-shop scheduling [22], parallel machine scheduling [23], and flow-shop scheduling [24, 25] and usually performs well. In addition, a multiobjective genetic algorithm (MOGA) has also been successfully applied to various multiobjective problems, such as a scheduling problem to minimize both production cost and time. For example, Tang et al. [26] addressed a multiobjective radio frequency identification network-planning problem with the objective of minimizing collision and interference of the network and network cost. They integrated a divide and conquer greedy heuristic algorithm and an MOGA to solve the problem. Zhang et al. [27] addressed multiobjective assembly line-balancing problems to minimize cycle time and rebalancing cost by modifying NSGA-II. Because GA is appropriate for handling the multiobjective scheduling problem, as shown in many previous researches, we choose GA to solve a multiobjective real-time task-scheduling problem in CM.In this paper, we study a multiobjective real-time task-scheduling problem in CM where tasks are scheduled whenever they are registered. The major research contents and contributions are as follows. First, we formalized the scheduling problem as a binary integer programming model with four objectives to minimize total tardiness, cost, quality, and reliability penalties. In addition, we design an MOGA to solve the problem by focusing on feasibility because most solutions to the problem are infeasible. Finally, we conduct an experiment to verify the proposed approach’s performance. Table1 summarizes how the contribution of our study extends previous research results.Table 1
Contribution of this paper to previous research.
Previous studyConsidering multiobjectiveConsidering real-timeConsidering various composition typesImproving meta-heuristic algorithmZhou et al. [6]√√√Cao et al. [7]√√√Liu et al. [8]√√Jiang et al. [9]√√√Li et al. [10]√√This paper√√√√The rest of this paper is organized as follows. Section2 describes the problem and introduces a mathematical model. Section 3 develops the proposed approach by focusing on designing a multiobjective GA that includes chromosome representation, a fitness function, and genetic operators. Section 4 conducts the experiments and compares the efficiency of the GA, and Section 5 concludes the paper.


## 2. Problem Description and Mathematical Model

### 2.1. Notation

Table2 shows notations used in this paper.Table 2
Notations.
NotationDescriptionService relatedSkTypek service, k=1,2,…,lSk,vvth type k service, v=1,2,…,Skck,vCost ofSk,vqk,vQuality ofSk,vrk,vReliability ofSk,vpk,vProcessing time ofSk,vTask and activity relatedTitTaski registered at time t=1,2,…,T, i=1,2,…,nt, where nt is the number of tasks registered at time tAi,jtActivityj in task Tit, j=1,2,…,mit, where mit is the number of activities in TitTypeAi,jtService type required forAi,jt, typeAi,jt∈S1,S2,…,SlPi,jtSet of precedent activities ofAi,jtFi,jtSet of following activities ofAi,jtDitDue date ofTitCitMaximum allowed cost to completeTitQitMinimum allowed quality ofTitRitMinimum allowed reliability ofTitD^itActual delivery date ofTitC^itActual cost to completeTitQ^itActual quality ofTitR^itActual reliability ofTitT˜itTardiness penalty onTitC˜itCost penalty onTitQ˜itQuality penalty onTitR˜itReliability penalty onTitDecision variablesxi,j,k,vt,τ=1,ifSk,vis matched toAi,jtat timeτ≥t,and=0,otherwiseISk,vt=1,ifSk,vis available at timet,and=0,otherwise


### 2.2. Problem Description

In cloud manufacturing, customers upload their requirements in the cloud-based manufacturing platform, and then the requirements are converted into a task, each of which consists of several activities and saved in the task pool. Enterprises virtualize and upload their manufacturing services (e.g., milling and cutting), and the services are saved in the service pool. The task-scheduling problem is to make a schedule for each task in the task pool by assigning a set of proper manufacturing services in the service pool. The considered task-scheduling problem is to assign a proper service to each activity of every task to minimize total tardiness and cost, quality, and reliability penalties at each time. Figure1 shows a typical example of the structure of a task-scheduling problem. The schedule is constructed by a manager (or management system) on a cloud-based manufacturing platform.Figure 1
Typical example of task scheduling.Each task is composed of several activities in sequence or in parallel. TaskT2t, in Figure 1, for example, is composed of three activities: A2,1t, A2,2t, and A2,3t. A2,1t,A2,2t are composed sequentially, while A2,2t,A2,3t are in parallel. The required service type differs according to the activity. For example, if Sk is the service type needed by Ai,jt, then one of Sk,vv=1,2,…,Sk can be matched to Ai,jt. Each activity can be processed only after the preceding activities have been completed. The activity without preceding activities (the root activity) can be processed only after the task to which it belongs is registered. Finally, services may have different performance metrics such as cost and quality even though they are of the same type. Services should be scheduled considering all required levels of tasks.Additional assumptions of the problem are summarized as follows:(1)
Required service type to process each activity is known(2)
The maximum allowed cost, minimum allowed quality and reliability, and due date are given(3)
There is no rework for any activity(4)
Customer satisfaction can be measured by cost, quality, reliability, and due date(5)
Geographical distances among service providers are not considered(6)
The outcome of a task is delivered to the customer once the task is completed


### 2.3. Mathematical Model

We describe objective functions and constraints of the established mathematical model in Sections2.3.1 and 2.3.2, respectively.


#### 2.3.1. Objective Functions

The objectives are to minimize the total penalty associated with tardiness, cost, quality, and reliability. In this section, we explain how to obtain objective values from the service schedule.Actual delivery timeD^it of task Tit is the maximum among completion times of activities that do not have the following activities. Because completion time of Ai,jt is calculated as the sum of service assignment time and processing time, D^it is obtained as follows:(1)D^it=maxFi,jt=∅∑k=TypeAi,jt,∀v,τ≥txi,j,k,vt,τ×τ+pk,v−1,where Fi,jt and pk,v denote the set of Ai,jt’s following activities and the processing time of Sk,v, respectively. With equation (1), the tardiness penalty T˜it of Tit is computed as the difference between D^it and Dit if it is bigger than zero, and zero otherwise:(2)T˜it=maxD^it−Dit,0,where Dit is the due date of Tit. By expanding equation (2) to all tasks registered at t, we have the first objective function, which is the sum of tardiness penalty for every task registered at t:(3)minimizeZ1=∑i=1ntT˜it.The actual costC^it to complete Tit is calculated as the sum of costs of services assigned to the task as given by(4)C^it=∑j=1mt/i∑k=TypeAi,jt,∀vck,v×xi,j,k,vt,τ,with equation (4), the cost penalty cpit on Tit is(5)C˜it=maxC^it−Cit,0,where Cit is the maximum allowed cost to complete Tit. By expanding equation (5) to all tasks, the second objective function is obtained as follows:(6)minimizeZ2=∑i=1ntC˜it.Similarly, the actual qualityQ^it of Tit is the average of qualities of services, and actual reliability R^it is the product of reliabilities of services assigned to the task as given by(7)Q^it=∑j=1mt/j∑k=TypeAi,jt,∀vqk,v×xi,j,k,vt,τmjt,R^it=∏j=1mt/j∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ,where ∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ is the reliability of the service assigned to activity Ai,jt.The quality penalty isQ˜it=maxQit−Q^it,0, and the reliability penalty is R˜it=maxRit−R^it,0. The third and fourth objective functions become (8) and (9), respectively:(8)minimizeZ3=∑i=1ntQ˜it,(9)minimizeZ4=∑i=1ntR˜it.


#### 2.3.2. Constraints

Constraints are related with service type, activity precedence, and service availability. Services of the required type can be assigned to an activity; therefore,(10)∑v=1Sk∑τ≥tTxi,j,k,vt,τ=1,∀TypeAi,jt=kk=1,2,…,l.Another constraint is the activity precedence. A service cannot be allocated to an activity with a preceding activity that has not been completed, which is expressed as follows:(11)τ0≤τ1,ifxi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1,andAi,j0t∈Pi,j1t,where τ0 is the assignment time for a preceding activity with assignment time τ1. xi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1 implies that Sk0,v0 and Sk1,v1 are assigned to Ai,j0t and Ai,j1t at τ0 and τ1, respectively.The next constraint is service availability. A service cannot be allocated to other activities until it is released:(12)∑w=0pk,v∑i,jxi,j,k,vt,τ−w≤1,∀τ,Tit,j,k,v.Constraint (12) can also be expressed by means of indicator variables as follows:(13)ISk,vτ≥xi,j,k,vt,τ,∀τ,Tit,j,k,v.In other words,xi,j,k,vt,τ=0 if ISk,vτ=0, and xi,j,k,vt,τ=1 otherwise. The indicator ISk,vt can prevent the system from allocating an unavailable service and resolve an unexpected situation in which a service becomes unavailable suddenly. For example, a service Sk,v that is supposed to be allocated to a task at time τ≥t may suddenly become unavailable because of a service-provider issue (e.g., contract expiration). The proposed GA can resolve this by setting ISk,vτ=0 for τ≥t and then continuing to search the solutions.Finally, because every decision variable is binary, we need the following:(14)xi,j,k,vt,τ∈0,1,∀τ,Tit,k,v,j.


## 2.1. Notation

Table2 shows notations used in this paper.Table 2
Notations.
NotationDescriptionService relatedSkTypek service, k=1,2,…,lSk,vvth type k service, v=1,2,…,Skck,vCost ofSk,vqk,vQuality ofSk,vrk,vReliability ofSk,vpk,vProcessing time ofSk,vTask and activity relatedTitTaski registered at time t=1,2,…,T, i=1,2,…,nt, where nt is the number of tasks registered at time tAi,jtActivityj in task Tit, j=1,2,…,mit, where mit is the number of activities in TitTypeAi,jtService type required forAi,jt, typeAi,jt∈S1,S2,…,SlPi,jtSet of precedent activities ofAi,jtFi,jtSet of following activities ofAi,jtDitDue date ofTitCitMaximum allowed cost to completeTitQitMinimum allowed quality ofTitRitMinimum allowed reliability ofTitD^itActual delivery date ofTitC^itActual cost to completeTitQ^itActual quality ofTitR^itActual reliability ofTitT˜itTardiness penalty onTitC˜itCost penalty onTitQ˜itQuality penalty onTitR˜itReliability penalty onTitDecision variablesxi,j,k,vt,τ=1,ifSk,vis matched toAi,jtat timeτ≥t,and=0,otherwiseISk,vt=1,ifSk,vis available at timet,and=0,otherwise


## 2.2. Problem Description

In cloud manufacturing, customers upload their requirements in the cloud-based manufacturing platform, and then the requirements are converted into a task, each of which consists of several activities and saved in the task pool. Enterprises virtualize and upload their manufacturing services (e.g., milling and cutting), and the services are saved in the service pool. The task-scheduling problem is to make a schedule for each task in the task pool by assigning a set of proper manufacturing services in the service pool. The considered task-scheduling problem is to assign a proper service to each activity of every task to minimize total tardiness and cost, quality, and reliability penalties at each time. Figure1 shows a typical example of the structure of a task-scheduling problem. The schedule is constructed by a manager (or management system) on a cloud-based manufacturing platform.Figure 1
Typical example of task scheduling.Each task is composed of several activities in sequence or in parallel. TaskT2t, in Figure 1, for example, is composed of three activities: A2,1t, A2,2t, and A2,3t. A2,1t,A2,2t are composed sequentially, while A2,2t,A2,3t are in parallel. The required service type differs according to the activity. For example, if Sk is the service type needed by Ai,jt, then one of Sk,vv=1,2,…,Sk can be matched to Ai,jt. Each activity can be processed only after the preceding activities have been completed. The activity without preceding activities (the root activity) can be processed only after the task to which it belongs is registered. Finally, services may have different performance metrics such as cost and quality even though they are of the same type. Services should be scheduled considering all required levels of tasks.Additional assumptions of the problem are summarized as follows:(1)
Required service type to process each activity is known(2)
The maximum allowed cost, minimum allowed quality and reliability, and due date are given(3)
There is no rework for any activity(4)
Customer satisfaction can be measured by cost, quality, reliability, and due date(5)
Geographical distances among service providers are not considered(6)
The outcome of a task is delivered to the customer once the task is completed


## 2.3. Mathematical Model

We describe objective functions and constraints of the established mathematical model in Sections2.3.1 and 2.3.2, respectively.


### 2.3.1. Objective Functions

The objectives are to minimize the total penalty associated with tardiness, cost, quality, and reliability. In this section, we explain how to obtain objective values from the service schedule.Actual delivery timeD^it of task Tit is the maximum among completion times of activities that do not have the following activities. Because completion time of Ai,jt is calculated as the sum of service assignment time and processing time, D^it is obtained as follows:(1)D^it=maxFi,jt=∅∑k=TypeAi,jt,∀v,τ≥txi,j,k,vt,τ×τ+pk,v−1,where Fi,jt and pk,v denote the set of Ai,jt’s following activities and the processing time of Sk,v, respectively. With equation (1), the tardiness penalty T˜it of Tit is computed as the difference between D^it and Dit if it is bigger than zero, and zero otherwise:(2)T˜it=maxD^it−Dit,0,where Dit is the due date of Tit. By expanding equation (2) to all tasks registered at t, we have the first objective function, which is the sum of tardiness penalty for every task registered at t:(3)minimizeZ1=∑i=1ntT˜it.The actual costC^it to complete Tit is calculated as the sum of costs of services assigned to the task as given by(4)C^it=∑j=1mt/i∑k=TypeAi,jt,∀vck,v×xi,j,k,vt,τ,with equation (4), the cost penalty cpit on Tit is(5)C˜it=maxC^it−Cit,0,where Cit is the maximum allowed cost to complete Tit. By expanding equation (5) to all tasks, the second objective function is obtained as follows:(6)minimizeZ2=∑i=1ntC˜it.Similarly, the actual qualityQ^it of Tit is the average of qualities of services, and actual reliability R^it is the product of reliabilities of services assigned to the task as given by(7)Q^it=∑j=1mt/j∑k=TypeAi,jt,∀vqk,v×xi,j,k,vt,τmjt,R^it=∏j=1mt/j∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ,where ∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ is the reliability of the service assigned to activity Ai,jt.The quality penalty isQ˜it=maxQit−Q^it,0, and the reliability penalty is R˜it=maxRit−R^it,0. The third and fourth objective functions become (8) and (9), respectively:(8)minimizeZ3=∑i=1ntQ˜it,(9)minimizeZ4=∑i=1ntR˜it.


### 2.3.2. Constraints

Constraints are related with service type, activity precedence, and service availability. Services of the required type can be assigned to an activity; therefore,(10)∑v=1Sk∑τ≥tTxi,j,k,vt,τ=1,∀TypeAi,jt=kk=1,2,…,l.Another constraint is the activity precedence. A service cannot be allocated to an activity with a preceding activity that has not been completed, which is expressed as follows:(11)τ0≤τ1,ifxi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1,andAi,j0t∈Pi,j1t,where τ0 is the assignment time for a preceding activity with assignment time τ1. xi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1 implies that Sk0,v0 and Sk1,v1 are assigned to Ai,j0t and Ai,j1t at τ0 and τ1, respectively.The next constraint is service availability. A service cannot be allocated to other activities until it is released:(12)∑w=0pk,v∑i,jxi,j,k,vt,τ−w≤1,∀τ,Tit,j,k,v.Constraint (12) can also be expressed by means of indicator variables as follows:(13)ISk,vτ≥xi,j,k,vt,τ,∀τ,Tit,j,k,v.In other words,xi,j,k,vt,τ=0 if ISk,vτ=0, and xi,j,k,vt,τ=1 otherwise. The indicator ISk,vt can prevent the system from allocating an unavailable service and resolve an unexpected situation in which a service becomes unavailable suddenly. For example, a service Sk,v that is supposed to be allocated to a task at time τ≥t may suddenly become unavailable because of a service-provider issue (e.g., contract expiration). The proposed GA can resolve this by setting ISk,vτ=0 for τ≥t and then continuing to search the solutions.Finally, because every decision variable is binary, we need the following:(14)xi,j,k,vt,τ∈0,1,∀τ,Tit,k,v,j.


## 2.3.1. Objective Functions

The objectives are to minimize the total penalty associated with tardiness, cost, quality, and reliability. In this section, we explain how to obtain objective values from the service schedule.Actual delivery timeD^it of task Tit is the maximum among completion times of activities that do not have the following activities. Because completion time of Ai,jt is calculated as the sum of service assignment time and processing time, D^it is obtained as follows:(1)D^it=maxFi,jt=∅∑k=TypeAi,jt,∀v,τ≥txi,j,k,vt,τ×τ+pk,v−1,where Fi,jt and pk,v denote the set of Ai,jt’s following activities and the processing time of Sk,v, respectively. With equation (1), the tardiness penalty T˜it of Tit is computed as the difference between D^it and Dit if it is bigger than zero, and zero otherwise:(2)T˜it=maxD^it−Dit,0,where Dit is the due date of Tit. By expanding equation (2) to all tasks registered at t, we have the first objective function, which is the sum of tardiness penalty for every task registered at t:(3)minimizeZ1=∑i=1ntT˜it.The actual costC^it to complete Tit is calculated as the sum of costs of services assigned to the task as given by(4)C^it=∑j=1mt/i∑k=TypeAi,jt,∀vck,v×xi,j,k,vt,τ,with equation (4), the cost penalty cpit on Tit is(5)C˜it=maxC^it−Cit,0,where Cit is the maximum allowed cost to complete Tit. By expanding equation (5) to all tasks, the second objective function is obtained as follows:(6)minimizeZ2=∑i=1ntC˜it.Similarly, the actual qualityQ^it of Tit is the average of qualities of services, and actual reliability R^it is the product of reliabilities of services assigned to the task as given by(7)Q^it=∑j=1mt/j∑k=TypeAi,jt,∀vqk,v×xi,j,k,vt,τmjt,R^it=∏j=1mt/j∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ,where ∑k=TypeAi,jt,∀vrk,v×xi,j,k,vt,τ is the reliability of the service assigned to activity Ai,jt.The quality penalty isQ˜it=maxQit−Q^it,0, and the reliability penalty is R˜it=maxRit−R^it,0. The third and fourth objective functions become (8) and (9), respectively:(8)minimizeZ3=∑i=1ntQ˜it,(9)minimizeZ4=∑i=1ntR˜it.


## 2.3.2. Constraints

Constraints are related with service type, activity precedence, and service availability. Services of the required type can be assigned to an activity; therefore,(10)∑v=1Sk∑τ≥tTxi,j,k,vt,τ=1,∀TypeAi,jt=kk=1,2,…,l.Another constraint is the activity precedence. A service cannot be allocated to an activity with a preceding activity that has not been completed, which is expressed as follows:(11)τ0≤τ1,ifxi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1,andAi,j0t∈Pi,j1t,where τ0 is the assignment time for a preceding activity with assignment time τ1. xi,j0,k0,v0t,τ0×xi,j1,k1,v1t,τ1=1 implies that Sk0,v0 and Sk1,v1 are assigned to Ai,j0t and Ai,j1t at τ0 and τ1, respectively.The next constraint is service availability. A service cannot be allocated to other activities until it is released:(12)∑w=0pk,v∑i,jxi,j,k,vt,τ−w≤1,∀τ,Tit,j,k,v.Constraint (12) can also be expressed by means of indicator variables as follows:(13)ISk,vτ≥xi,j,k,vt,τ,∀τ,Tit,j,k,v.In other words,xi,j,k,vt,τ=0 if ISk,vτ=0, and xi,j,k,vt,τ=1 otherwise. The indicator ISk,vt can prevent the system from allocating an unavailable service and resolve an unexpected situation in which a service becomes unavailable suddenly. For example, a service Sk,v that is supposed to be allocated to a task at time τ≥t may suddenly become unavailable because of a service-provider issue (e.g., contract expiration). The proposed GA can resolve this by setting ISk,vτ=0 for τ≥t and then continuing to search the solutions.Finally, because every decision variable is binary, we need the following:(14)xi,j,k,vt,τ∈0,1,∀τ,Tit,k,v,j.


## 3. Genetic Algorithm

This section describes the design procedure of the multiobjective GA to solve the mathematical model developed in the previous section. Figure2 shows an illustrative flowchart of the proposed multiobjective GA, with which the schedule for a task Tit is constructed in the order of the registered time. That is, the proposed GA selects the proper services for a task, which are scheduled to process the task and then service availability is updated. Therefore, a task can be scheduled as soon as it is uploaded (that is, task can be scheduled in a real-time manner).Figure 2
Flowchart of the proposed approach.


### 3.1. Chromosome Representation

Thehth chromosome in the gth population is represented as χtgh=χ1tgh,χ2tgh,…,χnttgh, where χitgh is a chromosome for scheduling Tit. χitgh consists of χi,1tgh, χi,2tgh, …, χi,mittgh, and χi,1tgh has two elements such as(15)χi,jtgh=vi,jtgh,τi,jtgh,where vi,jtgh is a service assigned to the activity and τi,jtgh=ττi,jt,sgh,τi,jt,sgh+1,…,τi,jt,egh is a processing period of Ai,jt by vi,jtgh. Here, τi,jt,sgh is the starting time and τi,jt,egh=τi,jt,sgh+pk,v−1 is the completion time of Ai,jt.


### 3.2. Generation of Initial Solution

If the GA generates initial solutions randomly, then convergence would take an extended amount of time because most solutions are infeasible. We therefore propose a method to generate initial solutions,χt1h, that are feasible, through Algorithm 1.Algorithm 1: Generation of initial solutions of χt1h.
Input:ISk,ντ for all τ≥t, k, vProcedure:Step 1. i=1.Step 2. j=1, and save the service type for Ai,jt as k, and randomly select vi,jt and τi,jt,s which satisfies:(1)
ISk,ντ=1 for τ=τi,js,τi,js+1,…,τi,js+pk,v−1, and(2)
τi,js is one of minimums among τ satisfying (1), and update ISk,ντ=0 for ν=vi,jt and τ=τi,js,τi,js+1,…,τi,js+pk,v−1.Step 3. Increase j by 1 and save the service type for Ai,jt as k.Step 4. Randomly select vi,jt and τi,js which satisfies:(1)
ISk,ντ=1 for τ=τi,js,τi,js+1,…,τi,js+pi,j−1,(2)
τi,js≥τi,j′s+pi,j′−1 for Ai,j′t∈PAi,jt,(3)
τi,js is one of minimums among τ satisfying both (1) and (2), and update ISk,ντ=0 for ν=vi,jt and τ=τi,js,τi,js+1,…,τi,js+pk,v−1.Step 5. χi,jt1h=vi,jt,τi,js,τi,js+1,…,τi,js+pk,v−1.Step 6. If i=nt and j=mit, terminate this algorithm. If j=mit and i≠nt, increase i by 1 and go to Step 2. If j≠mit, increase j by 1 and go to step 3.output:χt1h.This algorithm generates solutions satisfying the constraints in Section3.3 and operates ps times to generate χt11, χt12, …, χt1ps, where ps is the number of chromosomes in a population.


### 3.3. Fitness Function

Pareto ranking is employed as a fitness function to selectps chromosomes and to yield the best chromosome in each generation. This method calculates a fitness value stgh of χtgh as follows [28]:(16)stgh=1μγ1χtgh,γ2χtgh,γ3χtgh,γ4χtgh,where γiχtghi=1,2,3,4 is the ranking of the value, Zi, of the objective function with regard to χtgh among chromosomes in the same generation and μ⋅ denotes a mean function. Table 3 demonstrates how to calculate the fitness value by means of Pareto ranking.Table 3
An example of the Pareto ranking method.For example, because theZ1 values of χtgii=1,2,3,4 are 10, 12, 5, and 8, their ranks by rank1χtgii=1,2,3,4 are 3, 4, 1, and 2, respectively (see the first column of Table 3, circled by a bold blue rectangle). The rankings of Z1,Z2,Z3, and Z4 with regard to χtg1 are 3, 1, 3, and 2, respectively, and the fitness value is calculated as 1/μ3,1,3,2=0.444 (see the first row of Table 3, delineated by a dashed red rectangle). Note that the solution with a smaller objective function value takes a higher ranking because they are to be minimized.


### 3.4. Genetic Operators

We adopt a uniform crossover operator that selects one of the crossover lines randomly and assigns chromosomes of parents to the children based on those lines [29]. In this paper, we avoided generating infeasible solutions as presented in Algorithm 2.Algorithm 2: Procedure of uniform crossover.
Input: parent chromosomes χtgh1 and χtgh2h1≠h2Procedure:Step 1. Initialize i as 1.Step 2. Initialize j as 1.Step 3. Randomly select an element from h1,h2, and let h be the chosen and h˜ be the other one.Step 4. χi,jtg+1h3=χi,jtg+1h and χi,jtg+1h4=χi,jtg+1h˜.Step 5. If τi,jt,egh≤minj¯τi,j¯t,sgh˜, τi,jt,egh˜≤minj¯τi,j¯t,sgh, maxj˜τi,j˜t,egh≤τi,jt,sgh˜, and maxj˜τi,j˜t,egh≤τi,jt,sgh˜, then exchange h and h˜ with a probability λ, where Ai,j˜t∈PAi,jt and Ai,j¯t∈FAi,jt. Otherwise, do nothing.Step 6. If j=mit and i=nt, terminate. If j=mit and i≠nt, increase i by 1 and go to Step 2. If j≠mit, increase j by 1 and go to Step 3.Output: children chromosomes χtg+1h3 and χtg+1h4.


## 3.1. Chromosome Representation

Thehth chromosome in the gth population is represented as χtgh=χ1tgh,χ2tgh,…,χnttgh, where χitgh is a chromosome for scheduling Tit. χitgh consists of χi,1tgh, χi,2tgh, …, χi,mittgh, and χi,1tgh has two elements such as(15)χi,jtgh=vi,jtgh,τi,jtgh,where vi,jtgh is a service assigned to the activity and τi,jtgh=ττi,jt,sgh,τi,jt,sgh+1,…,τi,jt,egh is a processing period of Ai,jt by vi,jtgh. Here, τi,jt,sgh is the starting time and τi,jt,egh=τi,jt,sgh+pk,v−1 is the completion time of Ai,jt.


## 3.2. Generation of Initial Solution

If the GA generates initial solutions randomly, then convergence would take an extended amount of time because most solutions are infeasible. We therefore propose a method to generate initial solutions,χt1h, that are feasible, through Algorithm 1.Algorithm 1: Generation of initial solutions of χt1h.
Input:ISk,ντ for all τ≥t, k, vProcedure:Step 1. i=1.Step 2. j=1, and save the service type for Ai,jt as k, and randomly select vi,jt and τi,jt,s which satisfies:(1)
ISk,ντ=1 for τ=τi,js,τi,js+1,…,τi,js+pk,v−1, and(2)
τi,js is one of minimums among τ satisfying (1), and update ISk,ντ=0 for ν=vi,jt and τ=τi,js,τi,js+1,…,τi,js+pk,v−1.Step 3. Increase j by 1 and save the service type for Ai,jt as k.Step 4. Randomly select vi,jt and τi,js which satisfies:(1)
ISk,ντ=1 for τ=τi,js,τi,js+1,…,τi,js+pi,j−1,(2)
τi,js≥τi,j′s+pi,j′−1 for Ai,j′t∈PAi,jt,(3)
τi,js is one of minimums among τ satisfying both (1) and (2), and update ISk,ντ=0 for ν=vi,jt and τ=τi,js,τi,js+1,…,τi,js+pk,v−1.Step 5. χi,jt1h=vi,jt,τi,js,τi,js+1,…,τi,js+pk,v−1.Step 6. If i=nt and j=mit, terminate this algorithm. If j=mit and i≠nt, increase i by 1 and go to Step 2. If j≠mit, increase j by 1 and go to step 3.output:χt1h.This algorithm generates solutions satisfying the constraints in Section3.3 and operates ps times to generate χt11, χt12, …, χt1ps, where ps is the number of chromosomes in a population.


## 3.3. Fitness Function

Pareto ranking is employed as a fitness function to selectps chromosomes and to yield the best chromosome in each generation. This method calculates a fitness value stgh of χtgh as follows [28]:(16)stgh=1μγ1χtgh,γ2χtgh,γ3χtgh,γ4χtgh,where γiχtghi=1,2,3,4 is the ranking of the value, Zi, of the objective function with regard to χtgh among chromosomes in the same generation and μ⋅ denotes a mean function. Table 3 demonstrates how to calculate the fitness value by means of Pareto ranking.Table 3
An example of the Pareto ranking method.For example, because theZ1 values of χtgii=1,2,3,4 are 10, 12, 5, and 8, their ranks by rank1χtgii=1,2,3,4 are 3, 4, 1, and 2, respectively (see the first column of Table 3, circled by a bold blue rectangle). The rankings of Z1,Z2,Z3, and Z4 with regard to χtg1 are 3, 1, 3, and 2, respectively, and the fitness value is calculated as 1/μ3,1,3,2=0.444 (see the first row of Table 3, delineated by a dashed red rectangle). Note that the solution with a smaller objective function value takes a higher ranking because they are to be minimized.


## 3.4. Genetic Operators

We adopt a uniform crossover operator that selects one of the crossover lines randomly and assigns chromosomes of parents to the children based on those lines [29]. In this paper, we avoided generating infeasible solutions as presented in Algorithm 2.Algorithm 2: Procedure of uniform crossover.
Input: parent chromosomes χtgh1 and χtgh2h1≠h2Procedure:Step 1. Initialize i as 1.Step 2. Initialize j as 1.Step 3. Randomly select an element from h1,h2, and let h be the chosen and h˜ be the other one.Step 4. χi,jtg+1h3=χi,jtg+1h and χi,jtg+1h4=χi,jtg+1h˜.Step 5. If τi,jt,egh≤minj¯τi,j¯t,sgh˜, τi,jt,egh˜≤minj¯τi,j¯t,sgh, maxj˜τi,j˜t,egh≤τi,jt,sgh˜, and maxj˜τi,j˜t,egh≤τi,jt,sgh˜, then exchange h and h˜ with a probability λ, where Ai,j˜t∈PAi,jt and Ai,j¯t∈FAi,jt. Otherwise, do nothing.Step 6. If j=mit and i=nt, terminate. If j=mit and i≠nt, increase i by 1 and go to Step 2. If j≠mit, increase j by 1 and go to Step 3.Output: children chromosomes χtg+1h3 and χtg+1h4.


## 4. Experiment

In this section, we conduct experiments to verify that the proposed approach is practical under the experiment environment:OS: Microsoft Windows 10 Home (×64)CPU: Intel® Core™ i7-6700 CPURAM: 16.0 GBLanguage: Python 3.6.9First, a small toy problem is introduced to find all possible solutions and calculate their fitness values by means of a Pareto ranking method in Section4.1, followed by checking the ranks of the solutions obtained by the proposed approach. Second, we apply the proposed approach to solve a more realistic, large-scale scheduling problem and examine the search time to establish a schedule in Section 4.2. The first experiment shows that our approach can find a schedule that is effective and sufficiently close to the optimal schedule. The second experiment is to verify the given schedule as efficient and appropriate for a large-scale practical problem in real time.


### 4.1. Effectiveness Verification

Figure3 shows the task type introduced to compare the proposed method with an exhaustive search method. “S” and “H” are activities that require software and hardware services, respectively.Figure 3
Task type for effectiveness verification.We assume three tasks, three software services, and three hardware services in this problem. Information about the tasks, such as maximum allowed due dateDit, cost Cit, minimum quality Qit, and reliability Rit, is summarized in Table 4.Table 4
Task information.
TaskDitCitQitRitT111016098.50.98T21817099.00.99T121415098.00.98Table5 supplies information on services such as cost ck,v, quality qk,v, reliability rk,v, and processing time pk,v.Table 5
Service information.
Software serviceck,vqk,vrk,vpk,vS1,1221001.001S1,218990.982S1,314970.973Hardware serviceS2,1401001.001S2,234980.982S2,328970.973GA parameters in the proposed approach are set as follows: the number of generations is 50; the number of solutions per each generation is 20. Therefore, the GA searches 50×20 = 1000 solutions. We calculate the ranks of all solutions, including the one obtained by the proposed approach. Any inferior solutions (e.g., those waiting to allocate a service even though it is available, solutions that allocate no service at all, and solutions that allocate a single service to every activity) are ignored when searching all possible solutions. Table 6 summarizes all possible solutions, which are listed in the descending order of fitness values. The values in bold indicate the solution obtained by the proposed GA.Table 6
Objective functions, ranks, and fitness values of all possible solutions.
RankValueRankFitness valueZ1Z2Z3Z4Z1Z2Z3Z411940.00000.3187353,4545,661,61113,899,8204.034×10−721940.00000.3187353,4545,661,61113,899,5474.034×10−731960.00000.3101353,4546,921,45612,932,6203.918×10−741960.00000.3101353,4546,921,45612,934,6103.917×10−751900.00000.3361353,4544,163,14916,170,4973.742×10−7⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮1721960.10710.3195272,9786,921,4569,569,5074,248,1741.904×10−7⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮34,012,2247980.14280.372714,330,8897,321,56414,768,74711,846,9728.287×10−8As seen in Table6, our approach has found the 172th solution among 34,012,224 solutions, which lies in the top 0.00051%. In other words, the proposed algorithm can find a solution which is very close to the optimal. Because the proposed algorithm makes a schedule after a task is uploaded in the task pool, we expect that the number of tasks has little effect on the result. From the experiment result and the real-time property of the algorithm, we can conclude that the proposed algorithm is effective for task scheduling in cloud manufacturing.


### 4.2. Efficiency Verification

Next, a CM platform is assumed dealing with a more complicated and realistic task, depicted in Figure4, which was adopted from [30].Figure 4
Task type for efficiency verification.We randomly generate six situations where 5, 10, 15, 20, 25, and 30 tasks are uploaded at a day, and we calculate search time to establish the schedules in each situation. We assume that every task is uploaded att, and Dit, Cit, Qit, and Rit are uniformly distributed in the intervals [30, 60], [400, 450], [95, 100], and [0.95, 1.00], respectively.A total of 30 software services and 15 hardware services are virtualized and shared in the platform, and every service is idle at first. We assume thatqk,v, rk,v, and pk,v follow uniform distributions in the intervals [95, 100], [0.95, 1.00], and [1, 3], respectively. The costs of hardware and software services are assumed to be different from each other; that is, ck,v of software and hardware service is assumed to follow uniform distributions in [28, 40] and [95, 100], respectively.Table7 shows the search times when the numbers of solutions are 1000, 5000, and 10,000 and tasks are 5, 10, 15, 20, 25, and 30. It is obvious that as more solutions are searched it takes longer but is more likely to find the best solution. The rightmost column is the average scheduling time per task when 10,000 solutions are considered.Table 7
Search time according to the numbers of solutions and tasks (unit: seconds).
The number of solutions to be searched1,0005,00010,000Average scheduling time for each taskThe number of tasks to be scheduled51407671,551310102251,6462,050205156861,9396,442429208314,2677,964398251,0687,69410,141406301,3229,01212,438415As seen, the maximum search time is 12,438 seconds (3.455 hours) for 10,000 solutions and 30 tasks. A search time of three and a half hours is a relatively long time, raising the concern that the proposed approach is inadequate to be applied to in real time. However, the average time to schedule a task when we searched 10,000 solutions is 205∼420 seconds, approximately 3∼7 minutes. In practice, it is not usual for a complicated task to be uploaded every 7 minutes. In addition, the considered task is overly complicated comparing to realistic tasks, implying that the average time will be much lower than the experiment result provided in this study. Thus, once a complete and full schedule has been established, which may take several hours, a couple of tasks can be added to the existing schedule, which can be updated within 10 minutes, to produce an efficient schedule. Therefore, we conclude that the proposed approach is efficient and can be used in practice with a large number of complicated tasks and services. Even though the proposed algorithm is applied to establish schedules under an unreal situation in terms of the number of tasks and services, it can be applied to real tasks and services uploaded in CM such as in [8].


## 4.1. Effectiveness Verification

Figure3 shows the task type introduced to compare the proposed method with an exhaustive search method. “S” and “H” are activities that require software and hardware services, respectively.Figure 3
Task type for effectiveness verification.We assume three tasks, three software services, and three hardware services in this problem. Information about the tasks, such as maximum allowed due dateDit, cost Cit, minimum quality Qit, and reliability Rit, is summarized in Table 4.Table 4
Task information.
TaskDitCitQitRitT111016098.50.98T21817099.00.99T121415098.00.98Table5 supplies information on services such as cost ck,v, quality qk,v, reliability rk,v, and processing time pk,v.Table 5
Service information.
Software serviceck,vqk,vrk,vpk,vS1,1221001.001S1,218990.982S1,314970.973Hardware serviceS2,1401001.001S2,234980.982S2,328970.973GA parameters in the proposed approach are set as follows: the number of generations is 50; the number of solutions per each generation is 20. Therefore, the GA searches 50×20 = 1000 solutions. We calculate the ranks of all solutions, including the one obtained by the proposed approach. Any inferior solutions (e.g., those waiting to allocate a service even though it is available, solutions that allocate no service at all, and solutions that allocate a single service to every activity) are ignored when searching all possible solutions. Table 6 summarizes all possible solutions, which are listed in the descending order of fitness values. The values in bold indicate the solution obtained by the proposed GA.Table 6
Objective functions, ranks, and fitness values of all possible solutions.
RankValueRankFitness valueZ1Z2Z3Z4Z1Z2Z3Z411940.00000.3187353,4545,661,61113,899,8204.034×10−721940.00000.3187353,4545,661,61113,899,5474.034×10−731960.00000.3101353,4546,921,45612,932,6203.918×10−741960.00000.3101353,4546,921,45612,934,6103.917×10−751900.00000.3361353,4544,163,14916,170,4973.742×10−7⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮1721960.10710.3195272,9786,921,4569,569,5074,248,1741.904×10−7⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮34,012,2247980.14280.372714,330,8897,321,56414,768,74711,846,9728.287×10−8As seen in Table6, our approach has found the 172th solution among 34,012,224 solutions, which lies in the top 0.00051%. In other words, the proposed algorithm can find a solution which is very close to the optimal. Because the proposed algorithm makes a schedule after a task is uploaded in the task pool, we expect that the number of tasks has little effect on the result. From the experiment result and the real-time property of the algorithm, we can conclude that the proposed algorithm is effective for task scheduling in cloud manufacturing.


## 4.2. Efficiency Verification

Next, a CM platform is assumed dealing with a more complicated and realistic task, depicted in Figure4, which was adopted from [30].Figure 4
Task type for efficiency verification.We randomly generate six situations where 5, 10, 15, 20, 25, and 30 tasks are uploaded at a day, and we calculate search time to establish the schedules in each situation. We assume that every task is uploaded att, and Dit, Cit, Qit, and Rit are uniformly distributed in the intervals [30, 60], [400, 450], [95, 100], and [0.95, 1.00], respectively.A total of 30 software services and 15 hardware services are virtualized and shared in the platform, and every service is idle at first. We assume thatqk,v, rk,v, and pk,v follow uniform distributions in the intervals [95, 100], [0.95, 1.00], and [1, 3], respectively. The costs of hardware and software services are assumed to be different from each other; that is, ck,v of software and hardware service is assumed to follow uniform distributions in [28, 40] and [95, 100], respectively.Table7 shows the search times when the numbers of solutions are 1000, 5000, and 10,000 and tasks are 5, 10, 15, 20, 25, and 30. It is obvious that as more solutions are searched it takes longer but is more likely to find the best solution. The rightmost column is the average scheduling time per task when 10,000 solutions are considered.Table 7
Search time according to the numbers of solutions and tasks (unit: seconds).
The number of solutions to be searched1,0005,00010,000Average scheduling time for each taskThe number of tasks to be scheduled51407671,551310102251,6462,050205156861,9396,442429208314,2677,964398251,0687,69410,141406301,3229,01212,438415As seen, the maximum search time is 12,438 seconds (3.455 hours) for 10,000 solutions and 30 tasks. A search time of three and a half hours is a relatively long time, raising the concern that the proposed approach is inadequate to be applied to in real time. However, the average time to schedule a task when we searched 10,000 solutions is 205∼420 seconds, approximately 3∼7 minutes. In practice, it is not usual for a complicated task to be uploaded every 7 minutes. In addition, the considered task is overly complicated comparing to realistic tasks, implying that the average time will be much lower than the experiment result provided in this study. Thus, once a complete and full schedule has been established, which may take several hours, a couple of tasks can be added to the existing schedule, which can be updated within 10 minutes, to produce an efficient schedule. Therefore, we conclude that the proposed approach is efficient and can be used in practice with a large number of complicated tasks and services. Even though the proposed algorithm is applied to establish schedules under an unreal situation in terms of the number of tasks and services, it can be applied to real tasks and services uploaded in CM such as in [8].


## 5. Conclusion

CM is a manufacturing model based on the concept of sharing manufacturing resources among manufacturing enterprises to deal with highly customized requests of customers. In CM, each request is regarded a task, and it is assigned to one or more enterprises, called task scheduling. The objective of the task scheduling is to maximize customer satisfaction, and therefore, tardiness, cost, quality, and so forth should be considered. In addition, the task should be assigned as soon as possible for practical usage.This paper addressed a real-time and multiobjective task-scheduling problem to minimize total tardiness, cost, quality, and reliability penalties in CM. This problem was formalized as a binary integer programming model, and the MOGA was designed to solve the model by focusing on generating feasible solutions. From the experiment, we showed that the schedule based on the proposed approach is near the optimal schedule for small problems. In addition, we verified that the proposed approach establishes effective schedules in a real-time manner for a more realistic large-scale problem.In future research, we will develop a GA that does not generate infeasible or inferior solutions. This will surely reduce the search time remarkably. In addition, we will conduct practical research to apply our algorithm to the commercialized cloud manufacturing system. Finally, we will improve the proposed multiobjective GA to apply it to train the deep learning model-based CM scheduler.



---

*Source: 1305849-2021-02-15.xml*