{'fraction_non_alphanumeric': 0.0370616132243018, 'fraction_numerical': 0.012139190850719178, 'mean_word_length': 4.6295319709953855, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Fuzzy Scheduling Strategy for Intelligent Workflow Decision Making Systems in Uncertain Edge-Cloud Environments

Workflow decision making is critical to performing many practical workflow applications. Scheduling in edgecloud environments can address the high complexity of workflow applications, while decreasing the data transmission delay between the cloud and end devices. However, due to the heterogeneous resources in edge-cloud environments and the complicated data dependencies between the tasks in a workflow, significant challenges for workflow scheduling remain, including the selection of an optimal tasks-servers solution from the possible numerous combinations. Existing studies are mainly done subject to rigorous conditions without fluctuations, ignoring the fact that workflow scheduling is typically present in uncertain environments. In this study, we focus on reducing the execution cost of workflow applications mainly caused by task computation and data transmission, while satisfying the workflow deadline in uncertain edge-cloud environments. The Triangular Fuzzy Numbers (TFNs) are adopted to represent the task processing time and data transferring time. A cost-driven fuzzy scheduling strategy based on an Adaptive Discrete Particle Swarm Optimization (ADPSO) algorithm is proposed, which employs the operators of Genetic Algorithm (GA). This strategy introduces the randomly two-point crossover operator, neighborhood mutation operator, and adaptive multipoint mutation operator of GA to effectively avoid converging on local optima. The experimental results show that our strategy can effectively reduce the workflow execution cost in uncertain edge-cloud environments, compared with other benchmark solutions.


I. INTRODUCTION
W ORKFLOWS are widely exploited for the modeling of complicated applications, such as DNN-based applications [1], [2]. Such a workflow is usually computing-intensive, typically composed of tens of interdependent tasks. Indeed, workflow scheduling is essential as its result could directly affect the performance of workflow applications [3]. Due to the complicated structure of a workflow and the sophisticated data dependencies between the tasks in a workflow, completing workflow scheduling in time can be rather challenging even with the use of a high-performance computing platform.
To tackle the aforementioned challenge, some research has been focused on workflow scheduling in the cloud computing environment [4]- [6]. Such work is mainly oriented towards cloud service providers (e.g., Amazon EC2, Rackspace, and GoGrid) which provide virtual resources to the end customers [7], [8]. The underlying techniques have been developed in an attempt to rationally schedule the dependent tasks among the virtual resources through the pay-as-you-go method. However, they are generally aimed at reducing the workflow completion time and improving the resource utilization, with far less a focus on optimizing the execution cost of workflow applications. They mostly ignore the performance variation between virtual machines with different configurations. In terms of scheduling workflow in the cloud, it might increase the traffic load of core networks and cause high latency due to massive data transmission between clients and the cloud [9].
Edge computing provides an essential technology to improve performance in workflow scheduling [10]. It enhances the computing ability of a mobile network through deploying the computation and storage resources around the edges of the mobile web, thereby providing the service with high broadband and low delay to the clients. Workflow scheduling in edge-cloud environments not only meets the computeintensive requirements of workflow applications, but also effectively reduces data transmission delays, while scheduling data-intensive tasks to the edge and compute-intensive tasks to the cloud [11]. Nonetheless, the service nodes (namely, the virtual machines in the cloud and servers in the edge) are generally heterogeneous and their processing capacities can be rather different, as well as the cost-performance in terms of load/energy consumption [12]. To reduce the workflow execution cost while satisfying deadline constraints, significant difficulties remain in rationally scheduling the data-dependent tasks for efficient data transmissions and task executions.

arXiv:2107.01405v3 [cs.DC] 14 Dec 2021
The existing studies on workflow scheduling are mainly carried out subject to certain conditions (e.g., assuming that the performance of the service nodes, bandwidth, and other factors are steady, without fluctuation) [13]- [15]. However, in the practical scheduling processes, the CPUs of the service nodes and bandwidths between them always fluctuate, which may have considerable impact upon workflow scheduling. Whilst uncertainties in scheduling have been addressed in the literature, the relevant work is mainly focussed on Fuzzy Job Shop Scheduling Problem (FJSSP) [16], [17] or task scheduling for real-time embedded systems [18]. Little has been done on the challenging problem of fuzzy scheduling for workflow applications.
In our previous work [2], [19], we have addressed the problem of cost-driven scheduling for deadline-based workflows across multiple clouds, and cost-driven offloading for DNNbased applications over the cloud, edge, and end devices. Based on the experience accumulated in the field of workflow scheduling, in this paper, we further address a significant issue facing workflow scheduling. That is, the problem of reducing the workflow execution cost caused by task computation and data transmission, while satisfying the required deadline constraints in uncertain edge-cloud environments. In particular, a novel cost-driven workflow scheduling strategy is proposed, on the basis of an Adaptive Discrete Particle Swarm Optimization (ADPSO) algorithm, which is employed the operators of genetic algorithm. In support of this development, Triangular Fuzzy Numbers (TFNs) [20] are adopted to represent task processing time and data transferring time in the uncertain environments. The strategy can obtain an optimal fuzzy total execution cost for a workflow within its deadline with respect to commonly adopted benchmark datasets, offering three major contributions to the relevant literature: • An order-server nesting strategy to encode the workflow scheduling problem in uncertain edge-cloud environments. • An adaptive discrete Particle Swarm Optimization (PSO) algorithm employing the operators of Genetic Algorithm (GA) to improve the performance and searching efficiency of the scheduling strategy. • A workflow scheduling strategy to reduce fuzzy workflow execution cost caused by task computation and data transmission, while meeting the required deadline constraints.
The rest of this paper is organized as follows. Section II briefly reviews the related work. Section III presents the problem definition of workflow scheduling in uncertain edge-cloud environments. Section IV describes our proposed workflow scheduling strategy in detail. Section V analyses the performance of our strategy through experimental studies in comparison with the state-of-the-art scheduling strategies. Finally, Section VI summarizes the work and outlines relevant future research directions.

II. RELATED WORK
A workflow model, used to simulate and analyze the workflow applications in the real world, consists of a set of computational tasks linked through control and data dependencies [21]. Workflow scheduling is essential as its result could directly affect the performance of workflow applications.
Many research efforts have been launched to workflow scheduling in cloud computing. Yuan et al. [4] considered the cost minimization of data centers in private cloud. They proposed a Temporary Task Scheduling Algorithm (TTSA) that could efficiently schedule all arriving tasks to the private or public clouds. This method effectively reduced the cost of the private cloud while satisfying all tasks' delay constraints. Meng et al. [6] proposed a security-aware scheduling method based on PSO algorithm for real-time resource allocation across heterogeneous clouds. Experimental results shown that this strategy could achieve a good balance between scheduling and security performance. Pham et al. [22] considered the fulfilment and interruption rates of the volatile resources in order to reflect the instability of the cloud infrastructure. In that work, a novel evolutionary multi-objective workflow scheduling approach was proposed for generating a set of trade-off solutions, whose makespan and cost were superior to the state-of-the-art algorithms. Paknejad et al. [23] proposed an enhanced multi-objective co-evolutionary algorithm, called ch-PICEA-g, for workflow scheduling in cloud environment. Experiments results indicated that the proposed algorithm outperformed its counterparts in terms of different performance metrics, such as cost, makespan, and energy consumption. It is of practical significance for scheduling workflow in cloud computing. However, it might increase the traffic load of core networks and cause high latency due to massive data transmission between clients and the cloud.
Edge computing can effectively reduce the system delay of workflow scheduling [10], [11], [24]. Workflow scheduling in edge-cloud environments has recently drawn great interest. For instance, Xie et al. [25] designed a novel Directional and Non-local-Convergent PSO (DNCPSO) algorithm to simultaneously optimize the completion time and execution cost of the workflow. Experimental results demonstrated that DNCPSO could achieve better performance than other classic algorithms. Peng et al. [26] proposed a node reliability model to evaluate resource reliability in Mobile Edge Computing (MEC) environments, defining workflow scheduling as an optimization problem and solving it by an algorithm based on Krill-Herd [27]. Through experiments based on real workflow applications and mobile user contract tracking, it had proven that the performance of this method was significantly better than the traditional methods in terms of success rate and makespan. However, existing research on workflow scheduling in edgecloud environments hardly considers the comprehensive cost optimization for task computation and data transmission.
In real-world practice, the performance of service nodes and the bandwidth may fluctuate while scheduling a workflow application. Initial work exists that deals with scheduling in uncertain computing environments, but such work is mainly oriented towards intelligent manufacturing systems. In particular, Lei [28] represented fuzzy processing time and fuzzy due-date with TFNs and trapezoidal fuzzy numbers, respectively, while introducing an improved fuzzy max operation to investigate the FJSSP. In that work, so-called availability constraints are employed for maximizing the satisfaction level of customers. Sun et al [16] also used TFNs to describe processing time to cope with the FJSSP problem, where an effective hybrid Cooperative Evolution Algorithm (hCEA) was proposed for minimizing the fuzzy makespan. Fortemps [29] expressed an uncertain duration as a six-point fuzzy number, thereby establishing a fuzzy scheduling model to minimize the fuzzy completion time for job shop scheduling problem. Similarly, Li et al [30] used TFNs to capture the uncertainty of fuzzy processing time and introduced a uniform parallel machine scheduling with such processing time representation under fuzzy resource consumption constraints, minimizing the makespan.
Despite the aforementioned remarkable developments in the relevant research area, an important open issue remains on fuzzy workflow scheduling that is of great practical significance: Workflow scheduling that considers fuzzy task processing time and fuzzy data transferring time in uncertain edgecloud environments. Inspired by this observation, the reminder of this paper will establish a novel approach to cost-driven scheduling for deadline-based workflows in uncertain edgecloud environments.

III. SYSTEM MODEL AND DEFINITIONS
In this section, the workflow scheduling in certain environments is described firstly. Then we further elaborate the workflow scheduling in uncertain environments. Thirdly, the operations for TFNs in fuzzy workflow scheduling are introduced in detail. Finally, an example of cost-driven scheduling for a deadline-based workflow application in uncertain edgecloud environments is illustrated.

A. Workflow Scheduling in Certain Environments
The workflow scheduling framework proposed in this study consists of three main components, i.e., the edge-cloud environments, a deadline-based workflow, and a cost-driven scheduler.
A certain environment means that there is no fluctuation during workflow scheduling and execution. The edge-cloud environments S = {S cloud , S edge } consist of the cloud and edge, where there are different computing nodes (i.e., virtual machines in the cloud and severs in the edge). For simplicity, we use 'servers' to denote the computing nodes in the cloud and edge with a uniform representation. There are n servers in the cloud S cloud = {s 1 , s 2 , . . . , s n }, and m servers in the edge S edge = {s n+1 , s n+2 , . . . , s n+m }. A server s i is denoted by Eq. (1).
where ζ i and i are the booting time and shutdown time of server s i , respectively; p i is the processing capacity of server s i ; c com i is the computation cost per time unit λ i , which is a specific time unit for server s i ; f i = {0, 1} refers to the platform to which the server s i belongs. Note that when f i = 0, s i belongs to the cloud with powerful processing capacity. Otherwise, s i belongs to the edge with normal processing capacity.
The bandwidth b i,j between any two different servers is denoted by Eq. (2).
where β i,j is the value of bandwidth b i,j , ∀i, j = 1, 2, ..., |S|, i = j; c tran i,j is the data transmission cost per GB from server s i to s j .
A workflow can be described as a directed acyclic graph indicates that there is a dataset d i,j transferred from task v i to v j , and v j cannot be executed until v i is finished. For an arc e i,j = v i , v j , v i is called the immediate predecessor task of v j , and v j is called the immediate successor task of v i . In addition, a workflow has a corresponding deadline constraint D (W ). When a workflow is completed within its deadline based on a specific scheduling strategy, this strategy is called as a feasible solution.
Suppose that the processing time of task v i on server s j is described as t com (v i , s j ). Owing to its popularity, the serial processing model [31] is adopted herein. It expresses that a task is processed on only one server, and a server can process only one task concurrently. The data transferring time where t tran (d i,j , s k , s l ) is the time to transfer dataset d i,j from server s k to s l . If s k and s l are the same server, the data transferring time is 0. A cost-driven scheduler aims to reduce the workflow execution cost mainly caused by task computation and data transmission, while satisfying its deadline in edge-cloud environments. A scheduling strategy Ψ is denoted by Eq. (4).
where M = {(v i , s j ) ∪ (d k,l , s r , s t ) |v i ∈ V , d k,l ∈ E, s j , s r , s t ∈ S} is the mapping from tasks and datasets to servers; t t is the workflow completion time, and c t is the workflow execution cost in edge-cloud environments with a given scheduling strategy,.
There are two subsets in the mapping M : (v i , s j ) indicates that task v i is executed on server s j , and (d k,l , s r , s t ) implies that dataset d k,l is transferred from server s r to s t . When the subset M V = {(v i , s j ) |v i ∈ V , s j ∈ S} is determined, the other subset M E = {(d k,l , s r , s t ) |d k,l ∈ E, s r , s t ∈ S} will be determined. Therefore, the mapping M is equivalent to M V as Eq. (5).
When the mapping M is determined, the servers processing all tasks are determined with a specific scheduling strategy Ψ. Due to the data dependencies between the tasks in a workflow, the execution order of each task is relatively fixed. Each task v i will have the start time t start (v i ) and end time t end (v i ) once the corresponding M is determined. The workflow completion time can be denoted by Eq. (6).
We assume that the shutdown time i of s i is equal to the end time of the last task on it. The total execution cost c t of scheduling a workflow in edge-cloud environments is determined by Eqs. (7)(8)(9).
where c com is the task computation cost, and c tran is the data transmission cost. In summary, the scheduling strategy for a workflow in certain environments can be described by Eq. (10), which indicates that the scheduler pursues to minimize the total workflow execution cost c t , while satisfying its deadline D(W ).

B. Workflow Scheduling in Uncertain Environments
Uncertain environments mean that there are fluctuations during workflow scheduling and execution. The task processing time and data transferring time are uncertain due to the fluctuations of server processing capacity and bandwidth, respectively. Fuzzy set are employed to reflect the uncertainties during workflow execution [32], while the task processing time and data transferring time are represented as TFNs.
The membership function µt (x) of a TFNt = t l , t m , t u can be denoted by Eq. (11), which is represented graphically as Fig. 1 [33].
Where t m is the normal (namely, the most possible) value of the fuzzy variablet; t l and t u are the lower and upper limit values oft, respectively. When t l = t m = t u ,t is a certain number. A fuzzy variableτ in uncertain environments corresponds to a variable τ in certain environments. According to the principles of fuzzy set theory [34], the scheduling strategy for a workflow in uncertain environments can be defined as Eq. (12).
Wherec t is the fuzzy total workflow execution cost, andt t is the fuzzy workflow completion time. Both fuzzy variables (i.e.,c t andt t ) are represented by TFNs. For the target minc t , an equivalent representation through its mean value and the standard deviation can be introduced [35], where the objective function given in Eq. (12) is equivalent to that Eq. (13).
Where m (c t ) and std (c t ) are the mean value and standard deviation ofc t , and η is the weighting factor of std (c t ).
According to the work of Lee and Li [35], the mean value and standard deviation of a TFN can be defined through uniform distribution and proportional distribution. Therefore, m (c t ) and std (c t ) can be computed as Eqs. (14) and (15), respectively. std In the process of workflow scheduling, the actual task processing time and data transferring time are more likely to be longer than the estimated values [36]. A new fuzzification method based on Sun et al. [16] is proposed to describe the uncertain values (namely, task processing time and data transferring time). Therefore, the related parameters of a TFÑ t = t l , t m , t u are redefined as follows: t m is the estimated time; t l and t u are randomly selected from the interval [δ 1 · t, t] and 2t − t l , δ 2 · t , respectively, where δ 1 and δ 2 are adjustment coefficients, satisfying that δ 1 < 1, δ 2 > 1 and Such a TFN will satisfy the constraint t u − t m ≥ t m − t l . Therefore, the mean value m t of a TFNt becomes that in Eq. (16), which is more likely to be longer than its estimate.
For the constraintt t ≤ D (W ), the upper limit value t u of t t should be no more than the deadline constraint in the worst case. Therefore, the constraint given in Eq. (12) is equivalent to that in Eq. (17).
In summary, the scheduling strategy for a workflow in uncertain edge-cloud environments can be formalized as Eq. (18).

C. Operations for TFNs in Fuzzy Workflow Scheduling
To construct a feasible schedule for a workflow in uncertain edge-cloud environments, the operations for TFNs (i.e., addition, ranking, max, and multiplication) need to be introduced as follows.
1) Addition Operation: Addition operation is used to calculate the end time of tasks. Suppose that the start time and processing time of a task are denoted byr = r l , r m , r u andt = t l , t m , t u , respectively. The end time of such a task e = e l , e m , e u is calculated by Eq. (19) [33].
2) Ranking Operation: Ranking operation is required to calculate the maximum end time of all the immediate predecessors of task v i . Suppose that the end time of one predecessor and that of another predecessor arer = r l , r m , r u andt = t l , t m , t u , respectively. The maximum end time of such two predecessors is then calculated with respect to three different situations, following the ranking criterion proposed by Sakawa et al. [37].
Note that multiple ranking operations are recursively performed if there are more than two predecessor tasks.
3) Max Operation: Max operation is needed to calculate the start time of tasks. Suppose that the maximum end time of all immediate predecessors of task v i isr = r l , r m , r u , and the last idle time of a server before processing task v i is t = t l , t m , t u . Then, the membership function µẽ (z) of v i 's start timeẽ =r ∨t is computed by Eq. (20).
According to the max criterion proposed by Lei [28], the start time of task v i can be approximated by Eq. (21) .

4) Multiplication Operation:
Multiplication operation is carried out to calculate the task computation cost and data transmission cost as addressed by Eqs. (8) and (9), respectively. The product of a TFNt = t l , t m , t u and a real number κ is computed by Eq. (22) [33].
Similarly, the quotient of a TFNt = t l , t m , t u divided by a real number υ can be transformed into the product of such a TFN and another real number as Eq. (23).

D. Illustration of Cost-Driven Workflow Scheduling
Fig. 2 presents an example of cost-driven scheduling for a deadline-based workflow in uncertain edge-cloud environments. The edge-cloud environments S = {s 1 , s 2 , s 3 , s 4 } consist of four servers, where s 1 , s 2 belong to the cloud and s 3 , s 4 belong to the edge. The workflow application has 8 tasks and 9 datasets, whose deadline is 7.2 × 10 3 s. The time unit λ i is set to 60s. Table I lists the relevant parameters for the bandwidths between different servers. Table II presents the computation cost per hour for all servers. Table III shows the fuzzy processing time for each task on the available servers.   Fig. 2(c) depicts the workflow scheduling results based on the random scheduling strategy [50]. It randomly schedules each task to their corresponding severs, and all tasks are executed according to their data dependencies. The fuzzy completion timet t of the workflow application is (11599.95s, 11599.96s, 11613.64s), which exceeds the corresponding deadline (i.e., 7.2 × 10 3 s). The fuzzy execution costc t based on the random scheduling strategy is (38.61$, 38.84$, 39.6$), whose equivalent defuzzified value is 39.14$. Fig. 2(d) depicts the optimal workflow scheduling. The fuzzy completion timẽ t t is (7036.56s, 7052.69s, 7129.24s), which meets its deadline constraint. The fuzzy execution costc t is (28.41$, 29.84$, 32.79$), whose equivalent defuzzified value is 30.93$. The optimal execution cost is significantly reduced by 21% compared to that based on the random scheduling strategy.

IV. OUR PROPOSED INTELLIGENT DECISION MAKING SYSTEMS
The goal of a workflow scheduling strategy, Ψ = W , S, M ,t t ,c t , is to find the best mapping M from all tasks in a workflow W to different servers in edge-cloud environments S, where the workflow execution costc t is optimal within its corresponding deadlinet t . The tasks on a server have their strict execution order based on the data dependencies. A task can be executed on different servers, and a server also can process many tasks. Therefore, finding the best mapping from all tasks to different servers is a NP-hard problem [39]. PSO is one of the effective algorithms to address such problems. Therefore, we propose a workflow scheduling strategy based on the modified PSO algorithm (i.e., ADPSO). The traditional PSO algorithm is introduced first, followed by a detailed description of ADPSO.

A. Traditional PSO Algorithm
PSO is an efficient evolutionary technique inspired by the social behavior of bird flocks. Kennedy and Eberhart first presented the PSO algorithm in 1995 [40], which has been broadly investigated and utilized ever since. The particle is the most significant concept in PSO, which usually represents a candidate solution for an optimization problem. Each , which will determine their direction and magnitude at the next iteration. The velocity of each particle is affected by their personal best particle pB t i and the global best particle gB t . Each particle constantly updates their own velocity and position in the potential solution space to obtain better fitness. The iterative update of velocities and positions for each particle are determined by Eqs. (24) and (25), respectively.
where w is an inertia weight, which determines to what extent the velocity of current particles will affect the corresponding particles of the next generation, having a great impact on the convergence of PSO; c 1 and c 2 are acceleration coefficients, which denote the cognitive ability of a particle for its personal and global best particle, respectively; r 1 and r 2 are the random numbers on the interval [0,1), used to enhance the searching ability of PSO. The traditional PSO algorithm is designed for continuous optimization problems. However, workflow scheduling in edge-cloud environments is a discrete optimization problem. Therefore, an applicable PSO-based algorithm with new problem encoding and population update needs to be further adjusted.

B. ADPSO
The proposed ADPSO are described from five aspects: problem encoding, fitness function, population update, mapping from a particle to a fuzzy scheduling, and parameter settings.
1) Problem encoding: Problem encoding affects the searchability of a PSO-based algorithm, which is expected to meet three major principles: Viability, Completeness, and Nonredundancy [41]. Inspired by the work in [42], an orderserver nesting strategy is developed to encode the cost-driven workflow scheduling in uncertain edge-cloud environments. In particular, the i th particle in the t th iteration (i.e., P t i ) is denoted by Eq. (26).
where (χ ij , s ij ) t , j = 1, 2, ..., |V |, indicates the assignment of task v j , meaning that v j is executed on the server s ij with a specified order χ ij . There are two criteria for task execution on a server as follows. Criterion 1: If two concurrent tasks without data dependencies (i.e., there are no direct or indirect data dependencies between the tasks) are scheduled to the same server, the task with a larger order value will be processed earlier. If two tasks have the same order value, the one entering pending queue earlier will be processed first.
Criterion 2: If two tasks with data dependencies are scheduled to the same server, the predecessor one is processed first.    Fig. 2(d). After task v 1 is executed, tasks v 5 and v 8 are both scheduled to server s 2 . Since there are no data dependencies between v 5 and v 8 , and v 5 has a larger order value (i.e., 3.9), it is processed first based on Criterion 1.
Tasks v 2 , v 3 and v 6 are next scheduled to the corresponding servers. At this moment, v 8 , v 2 and v 6 are in the pending queue of server s 2 . Whilst v 8 has the same order value (i.e., 1.5) as v 6 , it will be processed before v 6 because it enters the pending queue of s 2 earlier. The remaining tasks are similarly processed based on the two criteria.
2) Fitness function: Fitness function is used to evaluate the performance of particles. In general, a particle with a small fitness value represents a better candidate solution. This study aims to minimize the fuzzy total execution costc t of scheduling a workflow within its deadline D(W ). Therefore, a particle corresponding to a scheduling result with a smaller fuzzy execution costc t can be regarded as a better solution. However, the problem encoding strategy may not meet the Viability principle, which dictates that the fuzzy completion timet t of a workflow must not exceed its deadline D (W ). Therefore, we compare the performance of two particles following three different situations.
Situation 1: Both particles corresponding to the scheduling results are feasible. The one with a smaller fuzzy total execution costc t is deemed better, and the fitness function is defined by Eq. (27).
Situation 2: One particle corresponding to the scheduling result is feasible, and the other is infeasible. The feasible particle is naturally deemed better, and the fitness function is defined by Eq. (28).
Situation 3: Both particles corresponding to the scheduling results are infeasible. The one with less fuzzy completion timẽ t t is deemed better, which is more likely to become feasible after update operations. The fitness function is defined by Eq. (29).
3) Population update: The update of each particle is affected by three factors: inertia, individual cognition, and social cognition [43]. To strengthen the searchability and avoid premature convergence of the proposed scheduling strategy, ADPSO employs the mutation operator and crossover operator of GA. The iterative update of the i th particle at the (t + 1) th iteration for the workflow scheduling is defined as Eq. (30).
where op mu () and op cr () are mutation operation and crossover operation, respectively; w is an inertia weight; c 1 and c 2 are acceleration coefficients; r, r 1 and r 2 are random numbers generated from the interval [0, 1).
For the inertia part, the mutation operator of GA [44] is introduced to perform the updating as Eq. (31).
Where M u () denotes the dual mutation operator, which includes the neighborhood mutation operator for task order and the adaptive multi-point mutation operator for the number of servers.  The neighborhood mutation operator randomly chooses three locations in a particle, and generates all sort combinations for the task order in the corresponding field. Then, it randomly selects a particle from the sort combinations as the generated one for feeding to the adaptive multi-point mutation operator. Fig. 4(a) depicts the neighborhood mutation operator. It randomly chooses the locations l 1 , l 2 and l 3 , and generates all sort combinations for task order. It then randomly selects the second combination as the one for the adaptive multi-point mutation operator.
For individual cognition and social cognition parts, we introduce the crossover operator of GA to update the corresponding part of Eq. (24). The updating process is determined by Eqs. (32) and (33).
Where C r () is the two-point crossover operator. C r (A, B) randomly selects two locations in particle A, and then replaces the corresponding segments between the two locations of A with the same interval in particle B. Fig. 5 depicts this crossover operator in action. It randomly selects the locations l 1 and l 2 in a mutated particle, and replaces the segments between l 1 and l 2 with the same interval in pB t i (or gB t ).  1 1 1 1 1 1 1 1 1 7 7 7 7 7 1 1 1 1 1 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7 4 4 4 4 4 4 4 1 1 1  4) Mapping from a particle to a fuzzy scheduling: The mapping from a particle to a fuzzy scheduling in uncertain edge-cloud environments is summarized in Algorithm 1. The inputs are the workflow W , all available servers S, and an encoded particle P . The output is the corresponding fuzzy workflow scheduling Ψ = W , S, M ,t t ,c t based on the particle P . It first initializes the mapping M to an empty set null andc tran to (0,0,0). The fuzzy task processing timet com (|V | × |S|) on different servers, and the fuzzy data transferring timet tran (|E| , |S| × |S|) between servers are calculated (line 3). According to the encoded particle P , each task v i is scheduled on server s j with the order χ j . For a certain task v i , its start timet start (v i ) is equal to the booting time ζ j of server s j if it is an entry task. Otherwise, the task cannot start until the last dataset is transferred to s j from its parents (line [13][14][15][16][17][18][19][20][21][22]. Then, the end timet end (v i ) of v i is the sum of its start timet start (v i ) and its processing timẽ t com (v i , s j ) on server s j (line 24). According to Eqs. (6) and (7),t t andc t are subsequently calculated. Note that if the fuzzy completion timet t exceeds the corresponding deadline(i.e., ALGORITHM 1: Mapping from a particle P to a fuzzy scheduling strategy Ψ. Input: W , S, P . Output: Ψ = W , S, M ,t t ,c t 1 Initialization : M ← null,c tran ← (0, 0, 0). 2 begin 3 Calculatet com (|V | × |S|),t tran (|E| , |S| × |S|); if v i is a entry task then 7 if s j is off then 8 Turn on s j ,ζ j =˜ j = (0, 0, 0); Turn on s j ,ζ j =˜ j = maxT ; t u > D(W )), the algorithm stops immediately and returns a symbolic value of False, meaning that this particle is infeasible (line [27][28][29]. Finally, it returns the fuzzy scheduling strategy Ψ = W , S, M ,t t ,c t if this particle is feasible (line 31).

5) Parameter settings:
The inertia weight w influences the convergence and searchability of PSO-based algorithm [45]. A larger inertia weight helps the algorithm jumping out of local optima, improving its global searchability. By contrast, a smaller inertia weight improves the algorithm's local searchability. This study proposes a new adjustment mechanism that can adaptively adjust the value of inertia weight based on the particle's current state, thereby enhancing the algorithm's overall searchability, as shown in Eq. (34).
where w max and w min represent the predefined maximum and minimum values of w, div(gB t , P t i ) represents the number of different encoding values between the current particle P t i and the global best particle gB t , and |P t i | represents the size of the particle's encoding space. This mechanism can adaptively adjust the algorithm's searchability according to the difference between the global best particle and current particle. When div(gB t , P t i ) is relatively small, it means that the difference between gB t and P t i is small. Thus, the particle's local searchability is expected to be enhanced, increasing the algorithm's convergence. Conversely, a bigger value of div(gB t , P t i ) means to increase the magnitude of w, enhancing the particle's global searchability.
Regarding the adaptive multi-point mutation, the mutation number k is adaptively adjusted according to the change of the inertia weight w, and its adjustment strategy is implemented by Eq. (35).
where k max and k min are the predefined maximum and minimum values of the mutation number k. The inertia weight w has a positive effect on the mutation number k. When w is large, the mutation number k is increased to enhance the mutation ability so that the algorithm's global searchability can be intensified. On the contrary, if w is small, k is decreased and as such, only limited mutation ability is reserved to maintain the diversity of the population. The acceleration coefficients c 1 , c 2 are dynamically adjusted according to [43], where c s 1 and c s 2 denote the start values of c 1 and c 2 , and c e 1 and c e 2 denote their end values. 6) Algorithm flowcharts: Fig. 6 presents the flowchart of ADPSO algorithm, which includes the following steps.
Step 1: Initialize the parameters of ADPSO, including population size Γ, maximum iteration number Θ, inertia weight, and acceleration coefficients. Next, randomly generate the initial population.
Step 2: Calculate each particle's fitness value according to Eqs. (27)(28)(29). Each particle is set to its personal best particle and the particle with the smallest fitness value is set to the global best particle.
Step 3: Update all particles according to Eq. (30), and recalculate the fitness value of each updated particle.
Step 4: Set the updated particle as the current personal best particle if its fitness value is less than the existing personal best; else, go to Step 6.
Step 5: Set the updated particle as the global best particle if its fitness value is less than the existing global best.
Step 6: Check whether the termination condition is met; if so, output the global best particle and terminate, else, go back to Step 3.

V. PERFORMANCE ANALYSIS
To validate the effectiveness of the workflow scheduling strategy based on the proposed ADPSO, experimental evaluations are carried out. In particular, the following Research Questions (RQs) are checked with the experiments conducted.
RQ1: Compared with traditional PSO-based Algorithms, does ADPSO improve the searchability and convergence? (Section V-B) RQ2: In optimizing the fuzzy workflow execution cost, is ADPSO superior to other algorithms in terms of performance stability? (Section V-C) RQ3: In workflow scheduling with respect to given deadlines in uncertain edge-cloud environments, does ADPSO help reduce workflow execution cost? (Section V-D)
Five types of workflow are tested for this study, obtained from different scientific fields [46], including: CyberShake from earthquake science, Epigenomics from biogenetics, LIGO from gravitational physics, Montage from astronomy, and SIPHT from bioinformatics. Each type of workflow has different structures, numbers of tasks, and data transmissions between tasks, with detailed information stored in an XML file [47]. For each type of workflow, we choose three categories for the experiments: Tiny (approximately 30 tasks), Small (approximately 50 tasks) and Medium (approximately 100 tasks).
There are three cloud servers (s 1 , s 2 , s 3 ) and two edge servers (s 4 , s 5 ) in edge-could environments. Each server has specific processing ability and computation cost per time unit. We assume that s 3 has the most powerful processing ability, the processing time of tasks on s 3 can be directly recorded from the corresponding XML file. Also, the processing capacity of s 1 or s 2 is approximately half or a quarter of that of s 3 , while the processing capacity of s 4 or s 5 is about one-eighth or one-tenth of that of s 3 . The computation cost per hour for s 3 is set to 15.5 $·h −1 , and the other severs' computation cost are approximately proportional to their processing abilities.
The bandwidth and data transmission cost between different types of server are set as Table I. Each workflow W is assumed to have a corresponding deadline constraint in order to test the algorithm performance, set as Eq. (36).
where H(W ) represents the execution time for scheduling W based on the HEFT algorithm [48].
Section III-C has elaborated how to fuzzify the task processing time t com and data transferring time t tran to TFNs. The parameters δ 1 and δ 2 are empirically set to 0.85 and 1.2, respectively. For comparing the results effectively among different algorithms, conventional defuzzification method for TFNs [34] is applied to the fuzzy execution cost and fuzzy completion time, where η is set to 1.
B. RQ1. Searchability and convergence 1) Compared algorithms: In this subsection, we regard the traditional PSO [40] as the baseline algorithm for comparison, which adopts a similar order-server nesting encoding strategy. The server encoding value is computed continuously, and its rounding value is set as the server number. The update strategy of PSO is based on Eqs. (24) and (25), and the parameters w, c 1 , c 2 are set according to [43]. By comparing the fuzzy execution cost of the candidate solutions and checking the deadline constraint's satisfaction for both algorithms, we analyze their performances in terms of the searchability and convergence.
2) Results and analysis: Different time units λ i are used depending on the size of the workflow. For the tiny and small workflows, the time unit λ i is one minute. For the medium workflow, the time unit λ i is one hour. We record both defuzzified fuzzy execution cost and fuzzy completion time of ADPSO and PSO algorithms over 1000 iterations. To clearly illustrate the convergence of fuzzy execution cost and to check whether fuzzy completion time meets the corresponding deadline constraint, Fig. 7 shows the time-cost iteration curves created by ADPSO and PSO algorithms for five types of medium workflow, where a blue full-line, a red dotted-line, and a horizontal black dotted-line indicate the workflow's execution cost, completion time, and the corresponding deadline, respectively.
ADPSO and PSO algorithms focus on decreasing the workflow completion time during the early global searching, so that they could meet the deadline constraint and obtain a feasible solution. With the increasing of the iteration number, they become emphasizing on optimizing the execution cost within the given deadline while the local search becomes more accurate. The number of iterations required for ADPSO and that for PSO to obtain the first feasible solution are similar. In particular, for CyberShake, as the execution cost is continuously optimizing, the completion time gradually stabilizes, fluctuating within the deadline. However, the scheduling strategy based on PSO becomes stable and converges to the global optimal particle at around the 200 th iteration, whilst ADPSO can still update the global optimal particle even at the 700 th iteration. In terms of the workflow execution cost, the scheduling strategy based on ADPSO is superior to that based on PSO. Regarding LIGO, as the execution cost decreases, the workflow completion time overall tends to decrease as well. Interestingly, the iteration number for convergence by PSO is less than that by ADPSO, but the convergence is reached prematurely as its performance on the execution cost is higher than that of ADPSO. For Montage, from the perspective of fluctuation on the workflow completion time, although PSO may generate the global optimal particle at a latter stage, it has an inapparent improvement concerning the workflow execution cost.
The more experimental results described in a github project [49] show that the workflow execution cost of the scheduling strategy based on ADPSO is always better than that of PSO, for both medium and small workflows, owing to the ability of dynamicaly adjusting the parameters in ADPSO. This enables ADPSO to focus on the global search at early stages, while focusing on the precise local search at later stages to obtain a better global optimal particle. As the mutation operator and crossover operator of GA are introduced into ADPSO, the encoded particles avoid convergence prematurely. By contrast, PSO uses the continuous encoding method and the traditional update strategy for the particles to solve the discrete problem, which easily leads to convergence to the local optima. In summary, ADPSO performs better because of its stronger searchability compared to PSO,.
C. RQ2. Stability on fuzzy execution cost 1) Compared algorithms: Apart from the PSO algorithm introduced in Section V-B1, this subsection also describe the following two compared algorithms. (i) Genetic Algorithm (GA) [44]: It employs the same order-server nesting encoding strategy as ADPSO. Following the classical update strategy of GA, the population is updated through binary tournament selection, two-point crossover operator, and mutation operator. Also, this algorithm takes the elitist preservation mechanism and completely copies the elite individuals into the next generation. The crossover probability and mutation probability of GA are set to 0.8 and 0.1, respectively [44]. (ii) Random Searching (RS) [50]: RS also employs the same order-server nesting encoding strategy as ADPSO. The random searching strategy is adopted to generate the new population, with the order and server encoding of each particle being randomly created. In addition, there is no interference between iterations. The optimal solution in the population is produced at the end iteration.
2) Stability performance index: To test the stability of all algorithms, the sample variance vector var [51] is introduced to measure the performance of each algorithm. The sample variance var i of an algorithm is defined by Eq. (37).  the fitness value at the j th test, andF denotes the mean fitness value after h tests.
Due to the uncertainty of fuzzy workflow scheduling, the weak fluctuation can have a significant impact on the fuzzy execution cost. Hence, we consider the relative magnitudes of the variances among the four algorithms and normalize the sample variance vector var as follows: where var is the standardized sample variance vector, and · 2 is the 2-norm. In general, the smaller the normalized sample variance is, the better stability the algorithm has.
3) Results and analysis: For each algorithm, ten independent repeated experiments are carried out, i.e., h = 10. Table IV shows the normalized sample variances of the fuzzy execution cost for different types of workflow. To visually compare the normalized sample variances for each workflow among different algorithms, we annotate the minimum and maximum values of the normalized sample variances with the bold and underline fonts, respectively. As shown in Table IV, ADPSO frequently obtains the minimum normalized sample variances, followed by PSO. By contrast, GA and RS frequently obtain the maximum normalized sample variances, while ADPSO has the maximum normalized sample variance only for the case of tiny CyberShake. Furthermore, among these compared algorithms, ADPSO has the smallest normalized sample variance of the fuzzy execution cost among 12 types of workflow. For the case involving tiny workflow, ADPSO obtains the smallest normalized sample variances on 3 workflows. Considering the cases involving small or medium workflows, ADPSO obtains the smallest normalized sample variances over four workflows. In summary, ADPSO has the optimal normalized sample variances, which means that it has the best stability compared with other classical algorithms.
D. RQ3. Fuzzy workflow execution cost 1) Compared algorithms: The experiments conducted in this subsection also employ those compared algorithms adopted in Section V-C1.
2) Results and analysis: To compare the performance of these different algorithms for fuzzy workflow execution cost in the given uncertain edge-cloud environments, we carry out 10 sets of independent repeated experiments for each algorithm with respect to cases involving different types of workflow.
For each algorithm with one type of workflow, we record the optimal execution cost and its corresponding fitness (Unit: $), as well as the mean execution cost and its corresponding fitness (Unit: $) in the 10 independent repeated experiments. Table V shows the fuzzy workflow execution cost of different algorithms for the tiny workflows. All the optimal solutions are listed in bold, and all the infeasible solutions are noted by '*'. Except for the case of SIPHT, ADPSO always obtains the optimal solution, beating PSO, GA and RS (with RS having the worst performance, and returning infeasible solutions). The superior performance of ADPSO is mainly owing to the improved encoding strategy, and the particle update mechanisms adopting the crossover operator and mutation operator of GA. Thus, better scheduling strategy is attained by ADPSO while avoiding premature convergence to local optima. Note that as the solution space of workflow scheduling is generally exponential, the random search strategy of RS is ineffective. As such, given limited population size and iteration number, it is difficult for RS to find high-quality solutions, even returning infeasible solutions.
For the small workflows, experimental results [49] show that the performance of ADPSO is still the best, obtaining all the optimal solutions. For CyberShake, the optimal value of ADPSO is 26.4% better than that of PSO, 15.9% better than that of GA, and 125.5% better than that of RS. In addition, the mean execution cost value of ADPSO beats PSO, GA, and RS by 19.9% for Montage, 16.3% for CyberShake, and 117.6% for Montage, respectively. Indeed, ADPSO outperforms the other algorithms while scheduling CyberShake and Montage which involve computing-intensive tasks. The scheduling results for medium workflows are almost the same as those for small workflows, with ADPSO achieving optimal solutions for all such workflows [49]. By contrast, RS suffers from the worse performance with the expansion of task sizes, becoming almost impossible to obtain a feasible solution. In short, the scheduling strategy based on ADPSO is able to reduce fuzzy workflow execution cost while achieving better scheduling outcomes compared with other algorithms.  Vehicle identification is one of the workflow applications in transportation systems, whose core technology is Deep Neural Networks (DNN) [52], [53]. Traffic cameras with limited process capacity periodically record the images of on-road vehicles, and usually fail to complete the applications within their deadlines. Workflow decision making is one of the key issues to performance DNNs in vehicle identification applications. Fig. 8   The uncertain environments have a great impact on the system latency for such problems, which can easily lead to the misjudgement of the optimal scheduling. In addition, it is difficult to select an optimal layers-servers solution from the numerous combinations. Therefore, as shown in Fig. 9, we can employ the scheduling strategy based on ADPSO to make intelligent workflow decisions for vehicle identification applications, which can reduce the execution cost mainly caused by layer computation and data transmission between layers within their deadlines, even in uncertain edge-cloud environments. Complex DNN layers (tasks) in vehicle identification applications can be scheduled to the cloud for execution, while simple ones are processed on the edge. The cloud and edge platforms collaborate with each other and execute the DNN layers with low system cost and latency.

VI. CONCLUSION AND THE FUTURE WORK
This paper has proposed a cost-driven scheduling strategy based on ADPSO for deadline-based workflow applications in uncertain edge-cloud environments. The work enables the reduction of workflow execution cost that is mainly caused by task computation and data transmission, while satisfying given deadlines. Experimental results have shown that the proposed strategy offers a better performance on scheduling computingintensive workflows than the state-of-the-art approaches. Particularly, ADPSO can obtain the optimal fuzzy execution cost for almost all types of workflows investigated.
Our future work intends to improve the current strategy to address more types of workflow applications (than experimentally studied herein), as well as workflow ensembles in fuzzy edge-cloud environments. Also, to reflect the fact that in general, different tasks may have different requirements, we plan to refine the proposed approach to consider different load-to-cost ratios for different servers, while optimizing the overall workflow scheduling process.