# A Heuristic Task Scheduling Strategy for Intelligent Manufacturing in the Big Data-Driven Fog Computing Environment

Authors: Rong Zhou
Journal: Mobile Information Systems
 (2022)

---

## Abstract

A heuristic task scheduling strategy for intelligent manufacturing in the big data-driven fog computing environment is proposed to address the problem that current resource scheduling and allocation methods in the fog computing environment cannot comprehensively consider the dynamics and uncertainty of resources, resulting in the prolonged delay and high energy consumption. First, a system model with three computing modes for intelligent manufacturing is constructed based on intelligent terminal devices, fog nodes, fog servers, fog gateways, and the cloud. Then, the objective function is optimized by jointly considering the delay matrix, the energy consumption matrix, and the reliability matrix, and corresponding constraints are given based on the selection of computing modes, the decision variables of fog nodes as well as the constraints about the delay. Finally, the intervals of crossover-mutation operators are divided according to the fitness value, and individuals of the population are updated by taking different operations based on the operators in different intervals, so as to achieve an improvement on the traditional genetic algorithms. Meanwhile, a fog resource scheduling algorithm is proposed based on the improved adaptive genetic algorithm. Simulation experiments are conducted to compare and analyze the delay, energy consumption, and reliability of the proposed method with three other methods under the same conditions. The results show that the proposed method has the lowest delay and energy consumption and the highest reliability, with values of 361.3 s, 352.4 J, and 94.6%, respectively, when the number of task requests is 500. The performance is better than the other three comparison methods.


---

## Body

## 1. Introduction

With advances in information technology such as the Internet of Things (IoT) and fog computing, the “smart factory” controlled by cyber-physical systems (CPS) is also developing rapidly [1, 2]. The Intellectualization of information and production methods has led to a higher level of interconnectivity, smarter devices, and more powerful data processing in intelligent manufacturing. Through the connected information, statistical data, and dynamic analysis, intelligent manufacturing makes the production smarter, leaner, more effective, and more energy-efficient [3–5]. The introduction of the IoT technology in intelligent manufacturing places new and higher demands on data sensing, collection, consolidation, transmission, and reverse control in smart factories. At the same time, the spread of intelligent devices and terminals and the use of various kinds of sensors will bring about ubiquitous sensing and connectivity, generating a constant flow of industrial data [6–8].The efficient processing of large volumes of data in traditional manufacturing can be achieved using cloud computing. However, due to the complexity of networking in the IoT and the limited computing capacity of devices in the bottom layer, traditional data processing methods cannot be used for delay-sensitive applications of intelligent manufacturing services [9, 10]. Fog computing, as a highly virtualized platform that locates on the edge of the local network, can provide computing and storage services near the underlying network and the Internet. Therefore, it is a good solution to the problem of rapid response and bandwidth consumption for delay-sensitive applications [11, 12]. When terminal devices request services from the cloud data center, fog computing can first perform data filtering, data pre-processing, and analysis before delivering it to the cloud computing system, thus reducing the burden on the cloud data center. Fog computing resources are therefore ideal for terminal users today [13]. Due to the dynamic and uncertainty of resources and the high variability and unpredictability of the fog computing environment, rational resource scheduling and allocation are particularly important, which have become a research hotspot in the industry [14, 15].A heuristic task scheduling strategy for intelligent manufacturing in a big data-driven fog computing environment is proposed to address the problems of prolonged delay, high energy consumption, and low reliability of current resource scheduling and allocation methods in fog computing environment. The basic ideas are: (1) First, a system model for intelligent manufacturing that can be used for computing mode selection is constructed. (2) The corresponding objective function and constraints are given in the consideration of delay, energy consumption, and reliability. (3) The applicability of the genetic algorithm to the problem under study is improved by making appropriate refinements to it. Compared with traditional task scheduling strategies, the main contributions of the proposed method can be summarized as follows:(1)
Intelligent devices, fog nodes, fog servers, fog gateways, and the cloud are taken into account when constructing the system model, greatly improving the utilization of fog computing resources.(2)
The objective function is optimized in terms of three aspects of task scheduling: delay, energy consumption, and the success rate of task execution.(3)
The traditional genetic algorithm is improved by dividing the crossover-mutation operators into intervals to further enhance the reliability of task scheduling.The remaining chapters of this paper are arranged as follows: the second chapter introduces the efficient resource allocation and task scheduling strategies for intelligent manufacturing in the fog computing environment, and some current research results. The third chapter establishes the system model. The fourth chapter introduces the proposed fog resource scheduling method based on a genetic algorithm. In Chapter 5, experiments are designed to verify the performance of the proposed algorithm. The sixth chapter is the conclusion, which summarizes this study and puts forward the further improvement direction.


## 2. Related Works

Some scholars have done relevant research and achieved certain results on resource allocation and task scheduling strategies for intelligent manufacturing in the fog computing environment. Li et al. standardized and normalized the attributes of resources, and combined the fuzzy clustering method with particle swarm optimization method to reduce the scale of resource search and divide the resources [16]. It proposed a new resource scheduling algorithm based on optimized fuzzy clustering for fog computing. However, the method only optimizes the processing time and cost of the tasks without considering the limited computational resources in the smart factory. In Yang et al., aiming at the multi-objective task scheduling problem in fog computing, a multi-objective task scheduling model was designed based on the Pareto optimal solution [17]. However, the method cannot reduce the overall reliance on large data centers and the Internet data are distant from the users. Ren et al. addressed the problem of limited resources in mobile devices and used fog computing to improve the WAN delay for delay-sensitive and resource-intensive applications [18]. It proposed an improved three-layer fog-to-cloud architecture and the schedule fit algorithm, which can provide computational resources and transmission delay according to the delay sensitivity of applications. The method fails to minimize the processing delay of the task and needs further improvement. Based on Lyapunov drift and the penalty function on the queue length, a scheduling strategy for tasks in the queues was proposed in Reference [19] to decide the number of tasks to be offloaded to the underloaded fog nodes to fully utilize the computational resources offered by all fog nodes in the network. However, this approach does not consider the service delay. By extending the architecture of fog computing, Tang et al. proposed a computational resource allocation scheme based on stable matching for open fog computing environment [20]. Based on the idea of stable matching, the allocation problem between tasks and computing service devices is solved by combining the priority list of subtasks and the preference lists of subtasks and computing service devices. However, the fog computing network is heavily used in this method. Alqahtani et al. classified requests to real-time, important, and time-tolerant, and proposed a scheduling method for allocating customers’ requests to the resources of the cloud-fog environment by considering load balancing among resources while allocating requests to them [21]. But the algorithm does not take the cost and energy consumption of resource scheduling into account. In Reference [22], in order to solve the resource scheduling and load balancing problems in fog computing, an optimized fuzzy clustering-based resource scheduling and dynamic load balancing algorithm was proposed. On this basis, an enhanced fuzzy C-means and the crow search optimization algorithm in fog computing were used to solve the problem. However, the method does not combine the characteristics of smart factories as a whole to fully optimize them.


## 3. System Model

### 3.1. System Model Description

Different from the traditional computing mode selection strategies, the proposed computing mode selection strategy is applicable to fog computing platforms with the combination of heterogeneous computing modes. In the fog computing platform, if the traditional strategies are still used, not only will the resource utilization of fog computing be reduced, but also the tasks which are related to intelligent manufacturing will not be guaranteed to be real-time, energy-efficient, or reliable. In order to improve the utilization of resources in fog computing, a system model of computing mode selection for intelligent manufacturing is established, which is shown in Figure1.Figure 1
The system model of computing mode selection for intelligent manufacturing.As can be seen from Figure1, the system model of computing mode selection for intelligent manufacturing consists mainly of intelligent terminal devices, fog nodes, fog servers, fog gateways, and the cloud. The intelligent terminal devices can either execute tasks locally or transmit the tasks that they cannot execute to other computing nodes. The fog node is the middleware that connects the intelligent terminal device to the cloud, and using the fog node as well as the cloud can enhance the computing capacity of the intelligent terminal devices. The fog node provides a real-time and distributed fog computing model for intelligent terminal devices in task execution. The cloud provides a remote and centralized cloud computing model for intelligent terminal devices in task execution. Different from the traditional strategies where all of the tasks are transmitted to the cloud to be executed, each task in the fog computing environment has a choice of three computing modes.Intelligent terminal devices forward the tasks through the fog nodes. Task requests from intelligent terminal devices are transmitted to the fog nodes, and all information of task requests is gathered at the fog gateway and subsequently forwarded to the fog server. The fog server can sense the global information of the fog nodes, which provides a reference for the dynamic selection of the computing modes of the task. The fog server manages the tasks, calculates the priority of each task, and adjusts the task queue according to the priority of the task, and then it formulates the optimal selection scheme of computing modes for the task. The fog server sends the selection scheme of computing modes to the fog gateway, and the fog gateway then sends the set of allocated tasks to the corresponding intelligent terminal devices, thus implementing the function of computing mode selection for the intelligent terminal devices when executing tasks.All devices in the system model are described below. The system model containsz intelligent terminal devices, n fog nodes and a cloud server. The set of intelligent terminal devices is represented by Z, where Z=E1,E2,E3,…,Ez and the attributes of the intelligent device Ei can be modeled as a triple Ci,P0i,P1i. Ci represents the computing capacity of the intelligent terminal device Ei. P0i represents the transmission power of the intelligent terminal device Ei. P1i denotes the computation power of the intelligent terminal device Ei. N denotes the set of fog nodes, where N=F1,F2,F3,…,Fn. And the computation power of the fog nodes is denoted as JN. The computing capacity of the cloud server is denoted as JC. T is a compound task and can be partitioned into n subtasks according to certain rules, which can be represented as T=T1,T2,T3,…,Tn. The attributes of the task Ti can be modeled as a triple Di,ρi,tmaxi. Di represents the amount of data of the task Ti. ρi represents the computational density of the task Ti. tmaxi denotes the maximum tolerance time of the task Ti. The system model of computing mode selection shows that each task can be executed through one of the three computing modes. The task can be either executed locally in the intelligent terminal device or transmitted to a fog node or a cloud server for execution. For the task Ti, the delay and energy consumption in the local execution mode are recorded as ti1 and ei1, respectively. The delay and energy consumption in fog computing mode are recorded as ti2 and ei2, respectively. And the delay and energy consumption in cloud computing mode are recorded as ti3 and ei3, respectively.


### 3.2. Optimization Objectives

In order to facilitate the description of the computing mode selection problem and better formulate the computing mode selection algorithm proposed in this section, relevant definitions and optimization objective functions are given to provide a basis for implementing the selection of computing modes. Based on the above analysis, the delay of the taskTi can be expressed as follows:(1)ti=αi1ti1+αi2ti2+αi3ti3,where αi1,αi2,αi3 represents the set of decision variables for the selection of the computing mode for the task Ti. When αi1=1, it indicates that the task Ti selects the local execution mode, which means that the task Ti will be executed by the intelligent terminal device Ei. Otherwise, αi1=0. When αi2=1, it indicates that the task Ti selects the fog computing mode, which means that the task Ti will be executed by a fog node. Otherwise, αi2=0. And when αi3=1, it indicates that the task Ti selects the cloud computing mode, which means that each Ti will be executed by a cloud server. Otherwise, αi3=0. The task Ti can only selects one of the computing modes, i.e., αi1,αi2,αi3∈0,1.We define the computing mode selection decision matrix asA, where the number of tasks being executed based on (1) is taken as the row and the number of computing modes that can be selected are taken as columns, as follows:(2)A=α11α12…α1Jα21α22…α2J…………αI1αI2…αIJ,aij denotes the decision variables for the task Ti in the computing model j, where i=1,2,3,…,I and j=1,2,3,…,J.We define the delay matrix asTt. According to the computing mode selection decision matrix A, the delay of each task in the task set T under three computing modes can be obtained. Thus, the delay matrix Tt for the task set T can be constructed as(3)Tt=t11,t12,…,t1Jt21,t22,…,t2J…,…,…,…tI1,tI2,…,tIJ,,where tij indicates the delay of the task Ti in the computing mode j, i=1,2,3,…,I, j=1,2,3,…,J. For tasks that select the fog computing mode, they will be allocated to all of the fog nodes according to the polling algorithm. hin denotes the selection decision of fog nodes for the task Ti, and hin=1 denotes that the task Ti selects to be executed by the fog node lF. Otherwise, hin=0. Hence, hin∈0,1 and ∑n=1Nhin=1,i=1,2,…,I.The energy consumption matrix is defined asE. Based on the computing mode selection decision matrix A, the energy consumption of each task in the task set T under three computing modes can be calculated. Hence, the energy consumption matrix E for the task T can be written as(4)E=e11,e12,…,e1Je21,e22,…,e2J…,…,…,…eI1,eI2,…,eIJ,where eij represents the energy consumption of the task Ti in the computing mode j, i=1,2,3,…,I, j=1,2,3,…,J.The reliability matrix is defined asK, and it is used to evaluate the execution performance of each task in the task set T within its maximum tolerance time. The reliability matrix can be expressed as(5)K=k11,k12,…,k1jk21,k22,…,k2j…,…,…,…ki1,ki2,…,kij,where kij represents the execution performance of the task Ti in the computing mode j, and it should meet the following constraints:(6)kij=0,αijtij≤tmaxi,1,αijtij>tmaxi.If the taskTi can be completed within its maximum tolerance time, the task Ti will be executed successfully. Otherwise, the task Ti fails. The number of successfully executed tasks is counted as zC and the higher the value of zC, the better the reliability of the task. The success rate of a task is given by p, which can be calculated as(7)p=zCz×100%.The energy consumption of all tasks in the task setT can be described as(8)eS=∑iIαi1ei1+αi2ei2+αi3ei3.The optimization objective of the computing mode selection strategy is to minimize the task delay and energy consumption, which can be formulated as(9)fo=minmax1<i<Iαi1ti1max1<n<N∑i=1Iαi2hnitn2,imax∑i=1Iαi3ti3,eS.The constraints are shown as(10)αi1,αi2,αi3∈0,1,i=1,2,3,…,I,αi1+αi2+αi3=1,i=1,2,3,…,I,hi1,hi2,hi3,…,hin∈0,1,i=1,2,3,…,I,∑n=1Nhin=1,i=1,2,…,I,i=1,2,3,…,I,ti≤tmaxi,i=1,2,3,…,I,where the first and second constraints are about the decision variables of the computing mode selection, ensuring that only one computing mode can be selected for each task. The third and fourth constraints are about the decision variables of the fog node selection, which guarantee that only one fog node can be selected for each task. The last inequality indicates the constraint about the delay for each task.


## 3.1. System Model Description

Different from the traditional computing mode selection strategies, the proposed computing mode selection strategy is applicable to fog computing platforms with the combination of heterogeneous computing modes. In the fog computing platform, if the traditional strategies are still used, not only will the resource utilization of fog computing be reduced, but also the tasks which are related to intelligent manufacturing will not be guaranteed to be real-time, energy-efficient, or reliable. In order to improve the utilization of resources in fog computing, a system model of computing mode selection for intelligent manufacturing is established, which is shown in Figure1.Figure 1
The system model of computing mode selection for intelligent manufacturing.As can be seen from Figure1, the system model of computing mode selection for intelligent manufacturing consists mainly of intelligent terminal devices, fog nodes, fog servers, fog gateways, and the cloud. The intelligent terminal devices can either execute tasks locally or transmit the tasks that they cannot execute to other computing nodes. The fog node is the middleware that connects the intelligent terminal device to the cloud, and using the fog node as well as the cloud can enhance the computing capacity of the intelligent terminal devices. The fog node provides a real-time and distributed fog computing model for intelligent terminal devices in task execution. The cloud provides a remote and centralized cloud computing model for intelligent terminal devices in task execution. Different from the traditional strategies where all of the tasks are transmitted to the cloud to be executed, each task in the fog computing environment has a choice of three computing modes.Intelligent terminal devices forward the tasks through the fog nodes. Task requests from intelligent terminal devices are transmitted to the fog nodes, and all information of task requests is gathered at the fog gateway and subsequently forwarded to the fog server. The fog server can sense the global information of the fog nodes, which provides a reference for the dynamic selection of the computing modes of the task. The fog server manages the tasks, calculates the priority of each task, and adjusts the task queue according to the priority of the task, and then it formulates the optimal selection scheme of computing modes for the task. The fog server sends the selection scheme of computing modes to the fog gateway, and the fog gateway then sends the set of allocated tasks to the corresponding intelligent terminal devices, thus implementing the function of computing mode selection for the intelligent terminal devices when executing tasks.All devices in the system model are described below. The system model containsz intelligent terminal devices, n fog nodes and a cloud server. The set of intelligent terminal devices is represented by Z, where Z=E1,E2,E3,…,Ez and the attributes of the intelligent device Ei can be modeled as a triple Ci,P0i,P1i. Ci represents the computing capacity of the intelligent terminal device Ei. P0i represents the transmission power of the intelligent terminal device Ei. P1i denotes the computation power of the intelligent terminal device Ei. N denotes the set of fog nodes, where N=F1,F2,F3,…,Fn. And the computation power of the fog nodes is denoted as JN. The computing capacity of the cloud server is denoted as JC. T is a compound task and can be partitioned into n subtasks according to certain rules, which can be represented as T=T1,T2,T3,…,Tn. The attributes of the task Ti can be modeled as a triple Di,ρi,tmaxi. Di represents the amount of data of the task Ti. ρi represents the computational density of the task Ti. tmaxi denotes the maximum tolerance time of the task Ti. The system model of computing mode selection shows that each task can be executed through one of the three computing modes. The task can be either executed locally in the intelligent terminal device or transmitted to a fog node or a cloud server for execution. For the task Ti, the delay and energy consumption in the local execution mode are recorded as ti1 and ei1, respectively. The delay and energy consumption in fog computing mode are recorded as ti2 and ei2, respectively. And the delay and energy consumption in cloud computing mode are recorded as ti3 and ei3, respectively.


## 3.2. Optimization Objectives

In order to facilitate the description of the computing mode selection problem and better formulate the computing mode selection algorithm proposed in this section, relevant definitions and optimization objective functions are given to provide a basis for implementing the selection of computing modes. Based on the above analysis, the delay of the taskTi can be expressed as follows:(1)ti=αi1ti1+αi2ti2+αi3ti3,where αi1,αi2,αi3 represents the set of decision variables for the selection of the computing mode for the task Ti. When αi1=1, it indicates that the task Ti selects the local execution mode, which means that the task Ti will be executed by the intelligent terminal device Ei. Otherwise, αi1=0. When αi2=1, it indicates that the task Ti selects the fog computing mode, which means that the task Ti will be executed by a fog node. Otherwise, αi2=0. And when αi3=1, it indicates that the task Ti selects the cloud computing mode, which means that each Ti will be executed by a cloud server. Otherwise, αi3=0. The task Ti can only selects one of the computing modes, i.e., αi1,αi2,αi3∈0,1.We define the computing mode selection decision matrix asA, where the number of tasks being executed based on (1) is taken as the row and the number of computing modes that can be selected are taken as columns, as follows:(2)A=α11α12…α1Jα21α22…α2J…………αI1αI2…αIJ,aij denotes the decision variables for the task Ti in the computing model j, where i=1,2,3,…,I and j=1,2,3,…,J.We define the delay matrix asTt. According to the computing mode selection decision matrix A, the delay of each task in the task set T under three computing modes can be obtained. Thus, the delay matrix Tt for the task set T can be constructed as(3)Tt=t11,t12,…,t1Jt21,t22,…,t2J…,…,…,…tI1,tI2,…,tIJ,,where tij indicates the delay of the task Ti in the computing mode j, i=1,2,3,…,I, j=1,2,3,…,J. For tasks that select the fog computing mode, they will be allocated to all of the fog nodes according to the polling algorithm. hin denotes the selection decision of fog nodes for the task Ti, and hin=1 denotes that the task Ti selects to be executed by the fog node lF. Otherwise, hin=0. Hence, hin∈0,1 and ∑n=1Nhin=1,i=1,2,…,I.The energy consumption matrix is defined asE. Based on the computing mode selection decision matrix A, the energy consumption of each task in the task set T under three computing modes can be calculated. Hence, the energy consumption matrix E for the task T can be written as(4)E=e11,e12,…,e1Je21,e22,…,e2J…,…,…,…eI1,eI2,…,eIJ,where eij represents the energy consumption of the task Ti in the computing mode j, i=1,2,3,…,I, j=1,2,3,…,J.The reliability matrix is defined asK, and it is used to evaluate the execution performance of each task in the task set T within its maximum tolerance time. The reliability matrix can be expressed as(5)K=k11,k12,…,k1jk21,k22,…,k2j…,…,…,…ki1,ki2,…,kij,where kij represents the execution performance of the task Ti in the computing mode j, and it should meet the following constraints:(6)kij=0,αijtij≤tmaxi,1,αijtij>tmaxi.If the taskTi can be completed within its maximum tolerance time, the task Ti will be executed successfully. Otherwise, the task Ti fails. The number of successfully executed tasks is counted as zC and the higher the value of zC, the better the reliability of the task. The success rate of a task is given by p, which can be calculated as(7)p=zCz×100%.The energy consumption of all tasks in the task setT can be described as(8)eS=∑iIαi1ei1+αi2ei2+αi3ei3.The optimization objective of the computing mode selection strategy is to minimize the task delay and energy consumption, which can be formulated as(9)fo=minmax1<i<Iαi1ti1max1<n<N∑i=1Iαi2hnitn2,imax∑i=1Iαi3ti3,eS.The constraints are shown as(10)αi1,αi2,αi3∈0,1,i=1,2,3,…,I,αi1+αi2+αi3=1,i=1,2,3,…,I,hi1,hi2,hi3,…,hin∈0,1,i=1,2,3,…,I,∑n=1Nhin=1,i=1,2,…,I,i=1,2,3,…,I,ti≤tmaxi,i=1,2,3,…,I,where the first and second constraints are about the decision variables of the computing mode selection, ensuring that only one computing mode can be selected for each task. The third and fourth constraints are about the decision variables of the fog node selection, which guarantee that only one fog node can be selected for each task. The last inequality indicates the constraint about the delay for each task.


## 4. Fog Computing Task Scheduling Algorithm

### 4.1. Overview of the Algorithm

Based on the aforementioned analysis, a fog resource scheduling method is proposed based on an adaptive bi-adaptive genetic algorithm. Population optimization is carried out by drawing on biological phenomena such as heredity, mutation, natural selection, and hybridization in the theory of biological evolution to find the optimal individual. The algorithm takes the individual in the population as a solution and evaluates the performance of the individual by the dual fitness function. The genetic operations can be divided into three main operators, which are selection, crossover, and mutation. The roulette wheel method is used in the selection operation to maintain genetic diversity in the survival of the fittest. However, as the mutation of chromosomal genes is random, the chromosomal solutions generated may not be feasible solutions, which mean that they do not satisfy the constraint between tasks. Therefore, in the selection operation, a repair strategy is also required for the selected individuals, which allows maximizing the maintenance of genes while changing infeasible solutions into feasible ones. Traditional single-point crossover and partial mapping crossover are combined in the crossover operation. The partial mapping crossover is used for scheduling sequences, and the traditional single-point crossover is used for fog node allocation sequences.


### 4.2. Improved Genetic Algorithm

#### 4.2.1. Encoding

Initialization of the adaptive genetic algorithm: set the termination conditions of the population iteration as the number of iterations reaching the maximum, the appearance of the optimal solution, or the iteration time reaching the constraint time. Set the optimization weights of delay and communication load asc1 and c2, respectively.By encoding chromosomes, genetic algorithms make a chromosome correspond to a solution of the optimization problem. The general encoding methods are direct encoding and indirect encoding. In this paper, indirect encoding is used. Thus, the mapping relationship between task requests and fog nodes is represented by a set of sequencesS,A, where S represents the scheduling ordered sequence and A represents the fog node allocation sequence. Each task request is mapped into a fog resource. A single task request corresponds to a single fog resource, and a single fog resource can correspond to multiple task requests. Each bit in the sequence S and the sequence A represents the number of task requests and the fog resource, and all of them are positive integers. The length of the sequence S and the sequence A is equal to the total number of task requests, which is denoted as k. And the gene value represented in the sequence A corresponds to the number of fog resources allocated to the task. The total number of fog nodes in a fog cluster is l, the total number of task requests is k and a set of sequences S,A is called a chromosome.Chromosome decoding strategy: The fog resource allocation strategy can be derived from the chromosome encoding rules. For example, a chromosome9,5,1,7,3,8,4,6,10,2,1,2,3,3,2,1,3,2,1,2 means that 10 tasks will be allocated to 3 fog nodes for execution. First, the task T9 will be allocated to the fog node F1 for execution, then the task T5 will be allocated to the fog node F2 for execution, and so on. Finally, the allocation strategy can be obtained, where the task T9, T8, and T10 will be executed in the fog node F1 in turn. Also, the task T5, T3, T6, and T2 will be executed in the fog node F2 in turn, and the task T1, T7, and T4 will be executed in the fog node F3 in turn.


#### 4.2.2. Populations Initialization

Population initialization is quite important for scheduling terminal user tasks in a fog computing architecture. The initial population is generated randomly and invalid solutions are excluded based on constraints. Let the size of the initial population beP, and the number of iterations is initialized as i=0. The constraints ask that the time-critical requests from the terminal user must be scheduled to the fog that is close to the user for execution, while requests which are not so urgent should be allocated to the cloud for execution. Meanwhile, in order to avoid severe load disparity, all requests from users cannot be placed on the same resource simultaneously.


#### 4.2.3. Fitness Function

The fitness function is the key to assessing the direction of population evolution when scheduling the terminal user tasks in a fog computing architecture. In order to make the fitness function remain meaningful when the total cost of the service provider is zero, it is defined as(11)fW=e−W.W represents the total cost of the service provider.


#### 4.2.4. Genetic Manipulation

Once traditional genetic algorithms have selected suitable individuals using the roulette wheel operator, they take crossover and mutation operations to obtain the next generation of individuals. However, traditional genetic algorithms adopt a uniform crossover variation operator for the evolution of populations, which is not conducive to either the retention of good individuals or the generation of even better individuals. Therefore, in this paper, the interval division of crossover-mutation operators is adopted. After the fitness value of individuals in the population is calculated based on the fitness function, all individuals are divided into different intervals according to the fitness value, which are the mutation interval with low fitness value, the retention interval with high fitness value, and the asymptotic interval with moderate fitness value. The population is then updated by applying different crossover-mutation operators to the individuals in the different intervals.Individuals with high fitness values are retained directly, ensuring that the best individuals are preserved at each iteration. For individuals with low fitness values, mutation operation is taken to change their chromosomes. By doing this, it gives the opportunity to mutate individuals with low fitness values into individuals with high fitness values, allowing the population to jump out of the local optimum and avoid premature convergence during the iteration, so as to improve the performance of global searching. For individuals with moderate fitness values, the custom interval division operator is used to select the parent individuals and then retain the better individuals by crossover operations. The main idea of the interval division crossover-mutation operator is shown in Figure2.Figure 2
The process of interval division of crossover-mutation operators.The crossover operator, which is a search operator in genetic algorithms, is mainly used when generating new individuals by crossing over the chromosomal genes of the current parent individuals. In this paper, a combination of traditional single-point crossover and partial mapping crossover is used. Specifically, the partial mapping crossover operation is used for the scheduling sequenceS and the traditional single-point crossover operation is used for the fog node allocation sequence A. In addition, a mechanism of individual self-adaptation is introduced, which means that the crossover rate changes with the fitness value.In the partial mapping crossover operation, a crossover selection position is set between any two adjacent genes in each chromosome subsequenceS, where the indexes are 1, 2,…, k + 1 from left to right. There are k + 1 different crossover selection positions in total. A partial mapping crossover is a random selection of two positions from k + 1 crossover selection positions, and the two parent chromosomes will produce a corresponding pair of genes between these two crossover selection positions. This pair is used to replace the genes of two parent chromosomes, respectively, resulting in two new children chromosomes. For example, if there are two parent sequences {8, 5, 9, 2, 7, 1, 3, 6, 4} and {1, 3, 7, 4, 6, 8, 2, 9, 5}, and the crossover selection positions are randomly generated to be 5 and 8, then the corresponding pair will be {7 : 6, 1 : 8, 3 : 2} and the two children chromosomes resulting from the partial mapping crossover operation will be {1, 5, 9, 3, 6, 8, 2, 7, 4} and {8, 2, 6, 4, 7, 1, 3, 9, 5}. In the single-point crossover operation, a crossover position is set between any two adjacent genes in each chromosome subsequence A, where the indexes are 1, 2,…, k − 1 from left to right. There are k − 1 different crossover positions in total. In the single-point crossover operation, a crossover position is randomly selected among k − 1 crossover positions, and all genes in those two chromosomes are exchanged from the positions onwards. For example, if the parent sequences are {3, 1, 1, 2, 3, 2, 1, 3, 2} and {1, 2, 3, 2, 2, 3, 3, 1, 1}, and the randomly generated crossover position is 5, then the two children chromosomes resulting from the single-point crossover operation will be {3, 1, 1, 2, 3, 3, 3, 1, 1} and {1, 2, 3, 2, 2, 2, 1, 3, 2}.The adaptive crossover rate can be obtained as(12)ft=∑m=1MftmM,fc=∑m=1MfcmM,PI=β1fmax−f0fmax−f,f0≥f,β2,f0≥f,where ft and fc denote the average fitness values for the maximum time span and communication overhead, respectively. PI is the crossover rate of the two individuals. β1 and β2 are constant coefficients of the crossover rate and satisfy the constraints of 0<β1<1 and 0<β2<1. Two crossed individuals will generate two fitness values each. The fitness function, which can generate the smallest fitness value among the four fitness values, is chosen as the criterion for crossover, i.e., one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. f0 is the larger fitness value of the two individuals fm and fmax is the largest fitness value of the current population fm.The mutation operator combines the methods of basic bit mutation and inversion mutation. Heuristic mutation is applied for the scheduling sequenceS and basic bit mutation is applied for the fog node allocation sequence A. The inversion mutation is applied for the chromosome subsequence S. In the inversion mutation, two gene bits are randomly selected from the k gene bits and the values of genes at these two bits are exchanged. For example, there is the parent sequence {3, 6, 1, 5, 2, 9, 7, 4, 8}, and if the two randomly generated gene bits are 2 and 6, a subsequence {3, 9, 1, 5, 2, 6, 7, 4, 8} will be generated after the inversion mutation. The basic bit mutation is applied for chromosome subsequence A. In the basic bit mutation, a gene bit is randomly selected from the k gene bits and a number from {1, 2, 3,...,n} is randomly selected to replace the gene at the current gene bit, which means that a new fog resource is randomly selected to replace the original fog resource. For example, if the parent sequence is {3, 1 ,1, 2, 3, 2, 1, 3, 2}, and the index of randomly generated gene bit for mutation is 3 and the random gene value selected for replacement is 2, then a child sequence {3, 1, 2, 2, 3, 2, 1, 3, 2} will be generated by the basic bit mutation. Mutation generates new genes and provides the diversity of the population. Like the crossover operator, the mutation operator introduces a mechanism of individual adaption, thus the mutation rate varies with the fitness value.The adaptive mutation rate can be written as(13)PV=λ1fmax−f0fmax−f,f0≥f,λ2,f0≥f,where PV is the mutation rate for an individual. λ1 and λ2 are constant coefficients of the crossover rate and they satisfy the constraints of 0<λ1<1 and 0<λ2<1. The fitness function which can generate the smaller fitness value of the current individual is used as the criterion for mutation, which means that one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. fmax is the largest fitness value in the current population fm.Genes are constantly evolving in each generation by operations such as selection, crossover, and mutation. Therefore, in order to keep each generation of individuals as feasible solutions, gene repair is required for individuals after the mutation operation.


### 4.3. Steps for Scheduling Fog Computation Tasks

The flow of the task scheduling algorithm in the fog computing environment for intelligent manufacturing is shown in Figure3.Figure 3
The flow of task scheduling algorithm in fog computing environment.The specific process of the algorithm is given as follows:(1)
Population initialization: the users submit the terminal request and the initial population is randomly set based on the request. A counter for the number of iterations is initialized as well.(2)
Fitness value calculation: the fitness values of individuals are calculated according to the fitness function.(3)
Judgment of termination conditions: when the number of evolutionary generations reaches the specified number of iterations, the result is output and a better solution for fog computing task scheduling should be obtained. Otherwise, go to step (4).(4)
Selection operation: a roulette wheel method is used to perform selection operations on the population.(5)
Crossover operation: according to the crossover method in the improved genetic algorithm, two individuals are randomly selected among those produced by the selection operation and then operated according to the crossover rate to generate new individuals.(6)
Mutation operation: according to the mutation method in the improved genetic algorithm, some individuals are selected from the new individuals generated by crossover operation and then operated according to the mutation rate to generate new individuals.(7)
Judgment of fitness value: the fitness value of the mutated individuals is judged, and if the fitness value is smaller than that of the parent, the parent is retained; if it is greater than or equal to that of the parent, the parent is replaced.(8)
Update the iteration counter: add 1 to the iteration counter and go to step (2).


## 4.1. Overview of the Algorithm

Based on the aforementioned analysis, a fog resource scheduling method is proposed based on an adaptive bi-adaptive genetic algorithm. Population optimization is carried out by drawing on biological phenomena such as heredity, mutation, natural selection, and hybridization in the theory of biological evolution to find the optimal individual. The algorithm takes the individual in the population as a solution and evaluates the performance of the individual by the dual fitness function. The genetic operations can be divided into three main operators, which are selection, crossover, and mutation. The roulette wheel method is used in the selection operation to maintain genetic diversity in the survival of the fittest. However, as the mutation of chromosomal genes is random, the chromosomal solutions generated may not be feasible solutions, which mean that they do not satisfy the constraint between tasks. Therefore, in the selection operation, a repair strategy is also required for the selected individuals, which allows maximizing the maintenance of genes while changing infeasible solutions into feasible ones. Traditional single-point crossover and partial mapping crossover are combined in the crossover operation. The partial mapping crossover is used for scheduling sequences, and the traditional single-point crossover is used for fog node allocation sequences.


## 4.2. Improved Genetic Algorithm

### 4.2.1. Encoding

Initialization of the adaptive genetic algorithm: set the termination conditions of the population iteration as the number of iterations reaching the maximum, the appearance of the optimal solution, or the iteration time reaching the constraint time. Set the optimization weights of delay and communication load asc1 and c2, respectively.By encoding chromosomes, genetic algorithms make a chromosome correspond to a solution of the optimization problem. The general encoding methods are direct encoding and indirect encoding. In this paper, indirect encoding is used. Thus, the mapping relationship between task requests and fog nodes is represented by a set of sequencesS,A, where S represents the scheduling ordered sequence and A represents the fog node allocation sequence. Each task request is mapped into a fog resource. A single task request corresponds to a single fog resource, and a single fog resource can correspond to multiple task requests. Each bit in the sequence S and the sequence A represents the number of task requests and the fog resource, and all of them are positive integers. The length of the sequence S and the sequence A is equal to the total number of task requests, which is denoted as k. And the gene value represented in the sequence A corresponds to the number of fog resources allocated to the task. The total number of fog nodes in a fog cluster is l, the total number of task requests is k and a set of sequences S,A is called a chromosome.Chromosome decoding strategy: The fog resource allocation strategy can be derived from the chromosome encoding rules. For example, a chromosome9,5,1,7,3,8,4,6,10,2,1,2,3,3,2,1,3,2,1,2 means that 10 tasks will be allocated to 3 fog nodes for execution. First, the task T9 will be allocated to the fog node F1 for execution, then the task T5 will be allocated to the fog node F2 for execution, and so on. Finally, the allocation strategy can be obtained, where the task T9, T8, and T10 will be executed in the fog node F1 in turn. Also, the task T5, T3, T6, and T2 will be executed in the fog node F2 in turn, and the task T1, T7, and T4 will be executed in the fog node F3 in turn.


### 4.2.2. Populations Initialization

Population initialization is quite important for scheduling terminal user tasks in a fog computing architecture. The initial population is generated randomly and invalid solutions are excluded based on constraints. Let the size of the initial population beP, and the number of iterations is initialized as i=0. The constraints ask that the time-critical requests from the terminal user must be scheduled to the fog that is close to the user for execution, while requests which are not so urgent should be allocated to the cloud for execution. Meanwhile, in order to avoid severe load disparity, all requests from users cannot be placed on the same resource simultaneously.


### 4.2.3. Fitness Function

The fitness function is the key to assessing the direction of population evolution when scheduling the terminal user tasks in a fog computing architecture. In order to make the fitness function remain meaningful when the total cost of the service provider is zero, it is defined as(11)fW=e−W.W represents the total cost of the service provider.


### 4.2.4. Genetic Manipulation

Once traditional genetic algorithms have selected suitable individuals using the roulette wheel operator, they take crossover and mutation operations to obtain the next generation of individuals. However, traditional genetic algorithms adopt a uniform crossover variation operator for the evolution of populations, which is not conducive to either the retention of good individuals or the generation of even better individuals. Therefore, in this paper, the interval division of crossover-mutation operators is adopted. After the fitness value of individuals in the population is calculated based on the fitness function, all individuals are divided into different intervals according to the fitness value, which are the mutation interval with low fitness value, the retention interval with high fitness value, and the asymptotic interval with moderate fitness value. The population is then updated by applying different crossover-mutation operators to the individuals in the different intervals.Individuals with high fitness values are retained directly, ensuring that the best individuals are preserved at each iteration. For individuals with low fitness values, mutation operation is taken to change their chromosomes. By doing this, it gives the opportunity to mutate individuals with low fitness values into individuals with high fitness values, allowing the population to jump out of the local optimum and avoid premature convergence during the iteration, so as to improve the performance of global searching. For individuals with moderate fitness values, the custom interval division operator is used to select the parent individuals and then retain the better individuals by crossover operations. The main idea of the interval division crossover-mutation operator is shown in Figure2.Figure 2
The process of interval division of crossover-mutation operators.The crossover operator, which is a search operator in genetic algorithms, is mainly used when generating new individuals by crossing over the chromosomal genes of the current parent individuals. In this paper, a combination of traditional single-point crossover and partial mapping crossover is used. Specifically, the partial mapping crossover operation is used for the scheduling sequenceS and the traditional single-point crossover operation is used for the fog node allocation sequence A. In addition, a mechanism of individual self-adaptation is introduced, which means that the crossover rate changes with the fitness value.In the partial mapping crossover operation, a crossover selection position is set between any two adjacent genes in each chromosome subsequenceS, where the indexes are 1, 2,…, k + 1 from left to right. There are k + 1 different crossover selection positions in total. A partial mapping crossover is a random selection of two positions from k + 1 crossover selection positions, and the two parent chromosomes will produce a corresponding pair of genes between these two crossover selection positions. This pair is used to replace the genes of two parent chromosomes, respectively, resulting in two new children chromosomes. For example, if there are two parent sequences {8, 5, 9, 2, 7, 1, 3, 6, 4} and {1, 3, 7, 4, 6, 8, 2, 9, 5}, and the crossover selection positions are randomly generated to be 5 and 8, then the corresponding pair will be {7 : 6, 1 : 8, 3 : 2} and the two children chromosomes resulting from the partial mapping crossover operation will be {1, 5, 9, 3, 6, 8, 2, 7, 4} and {8, 2, 6, 4, 7, 1, 3, 9, 5}. In the single-point crossover operation, a crossover position is set between any two adjacent genes in each chromosome subsequence A, where the indexes are 1, 2,…, k − 1 from left to right. There are k − 1 different crossover positions in total. In the single-point crossover operation, a crossover position is randomly selected among k − 1 crossover positions, and all genes in those two chromosomes are exchanged from the positions onwards. For example, if the parent sequences are {3, 1, 1, 2, 3, 2, 1, 3, 2} and {1, 2, 3, 2, 2, 3, 3, 1, 1}, and the randomly generated crossover position is 5, then the two children chromosomes resulting from the single-point crossover operation will be {3, 1, 1, 2, 3, 3, 3, 1, 1} and {1, 2, 3, 2, 2, 2, 1, 3, 2}.The adaptive crossover rate can be obtained as(12)ft=∑m=1MftmM,fc=∑m=1MfcmM,PI=β1fmax−f0fmax−f,f0≥f,β2,f0≥f,where ft and fc denote the average fitness values for the maximum time span and communication overhead, respectively. PI is the crossover rate of the two individuals. β1 and β2 are constant coefficients of the crossover rate and satisfy the constraints of 0<β1<1 and 0<β2<1. Two crossed individuals will generate two fitness values each. The fitness function, which can generate the smallest fitness value among the four fitness values, is chosen as the criterion for crossover, i.e., one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. f0 is the larger fitness value of the two individuals fm and fmax is the largest fitness value of the current population fm.The mutation operator combines the methods of basic bit mutation and inversion mutation. Heuristic mutation is applied for the scheduling sequenceS and basic bit mutation is applied for the fog node allocation sequence A. The inversion mutation is applied for the chromosome subsequence S. In the inversion mutation, two gene bits are randomly selected from the k gene bits and the values of genes at these two bits are exchanged. For example, there is the parent sequence {3, 6, 1, 5, 2, 9, 7, 4, 8}, and if the two randomly generated gene bits are 2 and 6, a subsequence {3, 9, 1, 5, 2, 6, 7, 4, 8} will be generated after the inversion mutation. The basic bit mutation is applied for chromosome subsequence A. In the basic bit mutation, a gene bit is randomly selected from the k gene bits and a number from {1, 2, 3,...,n} is randomly selected to replace the gene at the current gene bit, which means that a new fog resource is randomly selected to replace the original fog resource. For example, if the parent sequence is {3, 1 ,1, 2, 3, 2, 1, 3, 2}, and the index of randomly generated gene bit for mutation is 3 and the random gene value selected for replacement is 2, then a child sequence {3, 1, 2, 2, 3, 2, 1, 3, 2} will be generated by the basic bit mutation. Mutation generates new genes and provides the diversity of the population. Like the crossover operator, the mutation operator introduces a mechanism of individual adaption, thus the mutation rate varies with the fitness value.The adaptive mutation rate can be written as(13)PV=λ1fmax−f0fmax−f,f0≥f,λ2,f0≥f,where PV is the mutation rate for an individual. λ1 and λ2 are constant coefficients of the crossover rate and they satisfy the constraints of 0<λ1<1 and 0<λ2<1. The fitness function which can generate the smaller fitness value of the current individual is used as the criterion for mutation, which means that one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. fmax is the largest fitness value in the current population fm.Genes are constantly evolving in each generation by operations such as selection, crossover, and mutation. Therefore, in order to keep each generation of individuals as feasible solutions, gene repair is required for individuals after the mutation operation.


## 4.2.1. Encoding

Initialization of the adaptive genetic algorithm: set the termination conditions of the population iteration as the number of iterations reaching the maximum, the appearance of the optimal solution, or the iteration time reaching the constraint time. Set the optimization weights of delay and communication load asc1 and c2, respectively.By encoding chromosomes, genetic algorithms make a chromosome correspond to a solution of the optimization problem. The general encoding methods are direct encoding and indirect encoding. In this paper, indirect encoding is used. Thus, the mapping relationship between task requests and fog nodes is represented by a set of sequencesS,A, where S represents the scheduling ordered sequence and A represents the fog node allocation sequence. Each task request is mapped into a fog resource. A single task request corresponds to a single fog resource, and a single fog resource can correspond to multiple task requests. Each bit in the sequence S and the sequence A represents the number of task requests and the fog resource, and all of them are positive integers. The length of the sequence S and the sequence A is equal to the total number of task requests, which is denoted as k. And the gene value represented in the sequence A corresponds to the number of fog resources allocated to the task. The total number of fog nodes in a fog cluster is l, the total number of task requests is k and a set of sequences S,A is called a chromosome.Chromosome decoding strategy: The fog resource allocation strategy can be derived from the chromosome encoding rules. For example, a chromosome9,5,1,7,3,8,4,6,10,2,1,2,3,3,2,1,3,2,1,2 means that 10 tasks will be allocated to 3 fog nodes for execution. First, the task T9 will be allocated to the fog node F1 for execution, then the task T5 will be allocated to the fog node F2 for execution, and so on. Finally, the allocation strategy can be obtained, where the task T9, T8, and T10 will be executed in the fog node F1 in turn. Also, the task T5, T3, T6, and T2 will be executed in the fog node F2 in turn, and the task T1, T7, and T4 will be executed in the fog node F3 in turn.


## 4.2.2. Populations Initialization

Population initialization is quite important for scheduling terminal user tasks in a fog computing architecture. The initial population is generated randomly and invalid solutions are excluded based on constraints. Let the size of the initial population beP, and the number of iterations is initialized as i=0. The constraints ask that the time-critical requests from the terminal user must be scheduled to the fog that is close to the user for execution, while requests which are not so urgent should be allocated to the cloud for execution. Meanwhile, in order to avoid severe load disparity, all requests from users cannot be placed on the same resource simultaneously.


## 4.2.3. Fitness Function

The fitness function is the key to assessing the direction of population evolution when scheduling the terminal user tasks in a fog computing architecture. In order to make the fitness function remain meaningful when the total cost of the service provider is zero, it is defined as(11)fW=e−W.W represents the total cost of the service provider.


## 4.2.4. Genetic Manipulation

Once traditional genetic algorithms have selected suitable individuals using the roulette wheel operator, they take crossover and mutation operations to obtain the next generation of individuals. However, traditional genetic algorithms adopt a uniform crossover variation operator for the evolution of populations, which is not conducive to either the retention of good individuals or the generation of even better individuals. Therefore, in this paper, the interval division of crossover-mutation operators is adopted. After the fitness value of individuals in the population is calculated based on the fitness function, all individuals are divided into different intervals according to the fitness value, which are the mutation interval with low fitness value, the retention interval with high fitness value, and the asymptotic interval with moderate fitness value. The population is then updated by applying different crossover-mutation operators to the individuals in the different intervals.Individuals with high fitness values are retained directly, ensuring that the best individuals are preserved at each iteration. For individuals with low fitness values, mutation operation is taken to change their chromosomes. By doing this, it gives the opportunity to mutate individuals with low fitness values into individuals with high fitness values, allowing the population to jump out of the local optimum and avoid premature convergence during the iteration, so as to improve the performance of global searching. For individuals with moderate fitness values, the custom interval division operator is used to select the parent individuals and then retain the better individuals by crossover operations. The main idea of the interval division crossover-mutation operator is shown in Figure2.Figure 2
The process of interval division of crossover-mutation operators.The crossover operator, which is a search operator in genetic algorithms, is mainly used when generating new individuals by crossing over the chromosomal genes of the current parent individuals. In this paper, a combination of traditional single-point crossover and partial mapping crossover is used. Specifically, the partial mapping crossover operation is used for the scheduling sequenceS and the traditional single-point crossover operation is used for the fog node allocation sequence A. In addition, a mechanism of individual self-adaptation is introduced, which means that the crossover rate changes with the fitness value.In the partial mapping crossover operation, a crossover selection position is set between any two adjacent genes in each chromosome subsequenceS, where the indexes are 1, 2,…, k + 1 from left to right. There are k + 1 different crossover selection positions in total. A partial mapping crossover is a random selection of two positions from k + 1 crossover selection positions, and the two parent chromosomes will produce a corresponding pair of genes between these two crossover selection positions. This pair is used to replace the genes of two parent chromosomes, respectively, resulting in two new children chromosomes. For example, if there are two parent sequences {8, 5, 9, 2, 7, 1, 3, 6, 4} and {1, 3, 7, 4, 6, 8, 2, 9, 5}, and the crossover selection positions are randomly generated to be 5 and 8, then the corresponding pair will be {7 : 6, 1 : 8, 3 : 2} and the two children chromosomes resulting from the partial mapping crossover operation will be {1, 5, 9, 3, 6, 8, 2, 7, 4} and {8, 2, 6, 4, 7, 1, 3, 9, 5}. In the single-point crossover operation, a crossover position is set between any two adjacent genes in each chromosome subsequence A, where the indexes are 1, 2,…, k − 1 from left to right. There are k − 1 different crossover positions in total. In the single-point crossover operation, a crossover position is randomly selected among k − 1 crossover positions, and all genes in those two chromosomes are exchanged from the positions onwards. For example, if the parent sequences are {3, 1, 1, 2, 3, 2, 1, 3, 2} and {1, 2, 3, 2, 2, 3, 3, 1, 1}, and the randomly generated crossover position is 5, then the two children chromosomes resulting from the single-point crossover operation will be {3, 1, 1, 2, 3, 3, 3, 1, 1} and {1, 2, 3, 2, 2, 2, 1, 3, 2}.The adaptive crossover rate can be obtained as(12)ft=∑m=1MftmM,fc=∑m=1MfcmM,PI=β1fmax−f0fmax−f,f0≥f,β2,f0≥f,where ft and fc denote the average fitness values for the maximum time span and communication overhead, respectively. PI is the crossover rate of the two individuals. β1 and β2 are constant coefficients of the crossover rate and satisfy the constraints of 0<β1<1 and 0<β2<1. Two crossed individuals will generate two fitness values each. The fitness function, which can generate the smallest fitness value among the four fitness values, is chosen as the criterion for crossover, i.e., one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. f0 is the larger fitness value of the two individuals fm and fmax is the largest fitness value of the current population fm.The mutation operator combines the methods of basic bit mutation and inversion mutation. Heuristic mutation is applied for the scheduling sequenceS and basic bit mutation is applied for the fog node allocation sequence A. The inversion mutation is applied for the chromosome subsequence S. In the inversion mutation, two gene bits are randomly selected from the k gene bits and the values of genes at these two bits are exchanged. For example, there is the parent sequence {3, 6, 1, 5, 2, 9, 7, 4, 8}, and if the two randomly generated gene bits are 2 and 6, a subsequence {3, 9, 1, 5, 2, 6, 7, 4, 8} will be generated after the inversion mutation. The basic bit mutation is applied for chromosome subsequence A. In the basic bit mutation, a gene bit is randomly selected from the k gene bits and a number from {1, 2, 3,...,n} is randomly selected to replace the gene at the current gene bit, which means that a new fog resource is randomly selected to replace the original fog resource. For example, if the parent sequence is {3, 1 ,1, 2, 3, 2, 1, 3, 2}, and the index of randomly generated gene bit for mutation is 3 and the random gene value selected for replacement is 2, then a child sequence {3, 1, 2, 2, 3, 2, 1, 3, 2} will be generated by the basic bit mutation. Mutation generates new genes and provides the diversity of the population. Like the crossover operator, the mutation operator introduces a mechanism of individual adaption, thus the mutation rate varies with the fitness value.The adaptive mutation rate can be written as(13)PV=λ1fmax−f0fmax−f,f0≥f,λ2,f0≥f,where PV is the mutation rate for an individual. λ1 and λ2 are constant coefficients of the crossover rate and they satisfy the constraints of 0<λ1<1 and 0<λ2<1. The fitness function which can generate the smaller fitness value of the current individual is used as the criterion for mutation, which means that one of ftm and fcm is chosen as the criterion fm, where fm=ftm|fcm and f=ft|fc. fmax is the largest fitness value in the current population fm.Genes are constantly evolving in each generation by operations such as selection, crossover, and mutation. Therefore, in order to keep each generation of individuals as feasible solutions, gene repair is required for individuals after the mutation operation.


## 4.3. Steps for Scheduling Fog Computation Tasks

The flow of the task scheduling algorithm in the fog computing environment for intelligent manufacturing is shown in Figure3.Figure 3
The flow of task scheduling algorithm in fog computing environment.The specific process of the algorithm is given as follows:(1)
Population initialization: the users submit the terminal request and the initial population is randomly set based on the request. A counter for the number of iterations is initialized as well.(2)
Fitness value calculation: the fitness values of individuals are calculated according to the fitness function.(3)
Judgment of termination conditions: when the number of evolutionary generations reaches the specified number of iterations, the result is output and a better solution for fog computing task scheduling should be obtained. Otherwise, go to step (4).(4)
Selection operation: a roulette wheel method is used to perform selection operations on the population.(5)
Crossover operation: according to the crossover method in the improved genetic algorithm, two individuals are randomly selected among those produced by the selection operation and then operated according to the crossover rate to generate new individuals.(6)
Mutation operation: according to the mutation method in the improved genetic algorithm, some individuals are selected from the new individuals generated by crossover operation and then operated according to the mutation rate to generate new individuals.(7)
Judgment of fitness value: the fitness value of the mutated individuals is judged, and if the fitness value is smaller than that of the parent, the parent is retained; if it is greater than or equal to that of the parent, the parent is replaced.(8)
Update the iteration counter: add 1 to the iteration counter and go to step (2).


## 5. Experiments and Analysis

### 5.1. Simulation Environment and Parameter Settings

The simulation platform is configured with an Intel i5 processor with a CPU of 3.3 GHz and 4 GB of memory. A simulation environment for the selection of computing models for intelligent manufacturing is set up in MATLAB R2020a. A scenario of the intelligent production line is established in the simulation environment, the production object is the personalized candy packaging, and the production link, which is the manufacturing task, is the identification of multiple categories of candy. The size of task data is randomly selected between 1 and 10 Mb, and the number of tasks is taken as 10, 30, 40, 50, 90, 100, 300, 500, 700, and 900, respectively. The parameter set in the simulation is shown in Table1.Table 1
Simulation experiment parameters.
ParameterValueNumber of intelligent terminal devices200Number of fog nodes15The size of task data (Mb)1–10Maximum tolerance time for task1–3 sComputing capacity of cloud server (Gcycles/s)10Computing capacity of cloud server (W)50Computing capacity of fog nodes (Mcycles/s)300–500Computational density of tasks (cycles/bit)300Transmission power of smart device (M)3–6Computational power of smart device (M)3–6Network bandwidth of smart device (M)150Fog node network bandwidth (M)120Cloud server network bandwidth (M)5Real-time intensity weight for tasks0.8Complex intensity weight for tasks0.3Crossover rate0.8Mutation rate0.1The maximum number of iterations150Number of species100


### 5.2. Simulation Analysis

The delay and energy consumption of the method under the different number of task requests and the reliability of the method for task execution are important evaluation metrics for the performance of the task scheduling method. In the following, the heuristic task scheduling strategy for intelligent manufacturing in big data-driven fog computing environment proposed in this paper is compared and analyzed with the methods proposed in References [16, 17, 20] under the same conditions in terms of three evaluation metrics.First, the comparative analysis for the delay of the methods is conducted under the different number of task requests. The performance of delay in different methods is simulated in two different cases with a small number of task requests and a large number of task requests. The results are shown in Figures4 and 5, respectively.Figure 4
Delay of different methods in the case of a small number of task requests.Figure 5
Delay of different methods in the case of a large number of task requests.As can be seen from Figures4 and 5, the delay of all task scheduling strategies tends to rise as the number of tasks increases. However, compared to the other three methods, the heuristic task scheduling strategy proposed in this paper is more advantageous in terms of delay, as it has a smaller delay both in the case of a smaller number of task requests and in the case of a larger number of task requests. The delay is 123.4 s and 361.3 s, respectively when the number of task requests is 100 and 500. This is because the proposed method can better allocate the time-critical task requests to the fog computing resource nodes for execution. Compared with the traditional methods that all of the tasks are executed on the cloud, it can more effectively reduce the delay.The energy consumption of the methods under the same conditions when there are different numbers of task requests is compared, and the results are shown in Figure6.Figure 6
Energy consumption of different methods under different number of task requests.It is shown in Figure6 that the energy consumption of the system all shows an increasing trend with more task requests. However, the energy consumption of the proposed strategy is always the smallest and the most energy efficient compared to the other three comparison methods. When the number of task requests is 100 and 500, the energy consumption is 205.2 J and 352.4 J, respectively. The energy consumption of the task is determined by the delay of the task and the power of the computing node. In addition, the power of the computing node is a fixed value, and the delay of the task is the main factor that affects the performance of energy consumption of the task. As the delay of the proposed method is small, its energy consumption is also relatively small.Then, the success rate of task execution is calculated for the different number of task requests under the same conditions to verify the reliability of the respective methods. The results of success rates of task execution are shown in Figure7.Figure 7
Success rate of task execution of different methods under the different number of task requests.As shown in Figure7, the reliability of all four methods decreases as the number of tasks increases, but the reliability of the proposed method decreases the least and it remains the highest as the number of task requests changes. The task execution success rates of 95.3% and 94.6% are achieved for 100 and 500 task requests, respectively. This is because the proposed method takes into account the delay matrix, the energy consumption matrix and the reliability matrix in the process of objective optimization. The traditional genetic algorithm is improved in the calculation process. In the proposed method, the fitness function is used to calculate the fitness value of individuals in the population, and all individuals are divided into different intervals according to their fitness values. Also, the crossover-mutation operators are divided by intervals. Therefore, it can generate better individuals in the global scope, which improves the success rate and reliability of the proposed method in task execution.


## 5.1. Simulation Environment and Parameter Settings

The simulation platform is configured with an Intel i5 processor with a CPU of 3.3 GHz and 4 GB of memory. A simulation environment for the selection of computing models for intelligent manufacturing is set up in MATLAB R2020a. A scenario of the intelligent production line is established in the simulation environment, the production object is the personalized candy packaging, and the production link, which is the manufacturing task, is the identification of multiple categories of candy. The size of task data is randomly selected between 1 and 10 Mb, and the number of tasks is taken as 10, 30, 40, 50, 90, 100, 300, 500, 700, and 900, respectively. The parameter set in the simulation is shown in Table1.Table 1
Simulation experiment parameters.
ParameterValueNumber of intelligent terminal devices200Number of fog nodes15The size of task data (Mb)1–10Maximum tolerance time for task1–3 sComputing capacity of cloud server (Gcycles/s)10Computing capacity of cloud server (W)50Computing capacity of fog nodes (Mcycles/s)300–500Computational density of tasks (cycles/bit)300Transmission power of smart device (M)3–6Computational power of smart device (M)3–6Network bandwidth of smart device (M)150Fog node network bandwidth (M)120Cloud server network bandwidth (M)5Real-time intensity weight for tasks0.8Complex intensity weight for tasks0.3Crossover rate0.8Mutation rate0.1The maximum number of iterations150Number of species100


## 5.2. Simulation Analysis

The delay and energy consumption of the method under the different number of task requests and the reliability of the method for task execution are important evaluation metrics for the performance of the task scheduling method. In the following, the heuristic task scheduling strategy for intelligent manufacturing in big data-driven fog computing environment proposed in this paper is compared and analyzed with the methods proposed in References [16, 17, 20] under the same conditions in terms of three evaluation metrics.First, the comparative analysis for the delay of the methods is conducted under the different number of task requests. The performance of delay in different methods is simulated in two different cases with a small number of task requests and a large number of task requests. The results are shown in Figures4 and 5, respectively.Figure 4
Delay of different methods in the case of a small number of task requests.Figure 5
Delay of different methods in the case of a large number of task requests.As can be seen from Figures4 and 5, the delay of all task scheduling strategies tends to rise as the number of tasks increases. However, compared to the other three methods, the heuristic task scheduling strategy proposed in this paper is more advantageous in terms of delay, as it has a smaller delay both in the case of a smaller number of task requests and in the case of a larger number of task requests. The delay is 123.4 s and 361.3 s, respectively when the number of task requests is 100 and 500. This is because the proposed method can better allocate the time-critical task requests to the fog computing resource nodes for execution. Compared with the traditional methods that all of the tasks are executed on the cloud, it can more effectively reduce the delay.The energy consumption of the methods under the same conditions when there are different numbers of task requests is compared, and the results are shown in Figure6.Figure 6
Energy consumption of different methods under different number of task requests.It is shown in Figure6 that the energy consumption of the system all shows an increasing trend with more task requests. However, the energy consumption of the proposed strategy is always the smallest and the most energy efficient compared to the other three comparison methods. When the number of task requests is 100 and 500, the energy consumption is 205.2 J and 352.4 J, respectively. The energy consumption of the task is determined by the delay of the task and the power of the computing node. In addition, the power of the computing node is a fixed value, and the delay of the task is the main factor that affects the performance of energy consumption of the task. As the delay of the proposed method is small, its energy consumption is also relatively small.Then, the success rate of task execution is calculated for the different number of task requests under the same conditions to verify the reliability of the respective methods. The results of success rates of task execution are shown in Figure7.Figure 7
Success rate of task execution of different methods under the different number of task requests.As shown in Figure7, the reliability of all four methods decreases as the number of tasks increases, but the reliability of the proposed method decreases the least and it remains the highest as the number of task requests changes. The task execution success rates of 95.3% and 94.6% are achieved for 100 and 500 task requests, respectively. This is because the proposed method takes into account the delay matrix, the energy consumption matrix and the reliability matrix in the process of objective optimization. The traditional genetic algorithm is improved in the calculation process. In the proposed method, the fitness function is used to calculate the fitness value of individuals in the population, and all individuals are divided into different intervals according to their fitness values. Also, the crossover-mutation operators are divided by intervals. Therefore, it can generate better individuals in the global scope, which improves the success rate and reliability of the proposed method in task execution.


## 6. Conclusion

A heuristic task scheduling strategy for intelligent manufacturing in the big data-driven fog computing environment is proposed to address the problems of prolonged delay, high energy consumption, and low reliability of resource scheduling and allocation methods in the fog computing environment. The proposed method and three other comparative methods are compared and analyzed through simulation experiments. The results show that the comprehensive consideration of fog nodes, fog servers, and fog gateways on the basis of intelligent terminal devices and the cloud can significantly improve the utilization of fog computing resources. Optimization of the objective function with the constraints of delay, energy consumption, and success rate can improve the overall performance of the algorithm. By dividing the crossover-mutation operators into intervals, the genetic algorithm can generate better individuals and thus improve the reliability of task scheduling. Future work will delve into the impact of the dynamic characteristics of network and storage resources on fog computing and the improvement method.



---

*Source: 5830760-2022-08-26.xml*