Workflow scheduling in distributed systems under fuzzy environment

Abstract

A well-managed time-constrained workflow scheduling is needed for improving system performance and end user satisfaction. Meanwhile, the intrinsic uncertainty in dynamic systems increases the difficulties of scheduling problem. Therefore, it is a great challenge to improve performance and optimize several objectives simultaneously. To address these issues, a novel workflow scheduling method for distributed systems based on TOPSIS method with fuzzy set is proposed in this paper. The new method can minimize the makespan of the workflow application under uncertain environment. Finally, a numerical example is provided to demonstrate the efficiency of the proposed method.

Keywords

Workflow scheduling Triangular fuzzy numbers TOPSIS Distributed systems

1 Introduction

Many complex applications such as bioinformatics and disaster modeling can be naturally expressed in the form of workflow of tasks [1, 2]. One of the advantages for workflow representation is that the workflow is reproducible, traceable and reusable even by other workflows [3, 4]. Meanwhile, computing systems where catastrophe may occur will become useless, if tasks completion takes more than some specified time. Such applications based on the workflow management systems are increasing demands for processing large amounts of data in real-time tasks with desired cost reduction of computational resources [5].

Workflow scheduling is a process of mapping the workflow tasks to the appropriate networked resources. Because of the complex operations, the relationships of processing tasks are multiple interdependent. Hence, the tasks and dependencies of parent/child inter-relationship can be represented by the directed acyclic graph (DAG). Each task has various execution times, priorities and deadline constraints that are associated to other workflow [6, 7]. For achieving user quality of service (QoS) expectations, e.g., execution time minimization, while at the same time optimizing system performance, e.g., resource usage, an efficient workflow scheduling is imperative.

However, in order to attain good performance, different workflow applications need different scheduling approaches in distributed systems. Most literatures investigated the homogeneous computing system, while some works focused on heterogeneous system, each with different related constraints. The existing approaches tend to be process-oriented or data-oriented rather than resource-oriented, so that they lack efficient task-to-resource mapping capabilities [8]. Furthermore, in the conventional scheduling problem, the parameters such as task communication time and computation time have been assumed to be deterministic [9 –12]. In fact, in the real-world situations, various factors involved in the scheduling problems are often imprecise or uncertain in nature [13 –16]. Especially, human-made factors are involved into the problems. Up to now, the problems of modeling and handling uncertain information have attracted great attentions from researchers [17 –22].

In this paper, we consider fuzzy completion times in the workflow management systems. Nevertheless to say, fuzzy sets theory [23] introduced by Zadeh is a good approach to settle with such an uncertain problem [24, 25]. The Technique for Order Preferences by Similarity to an Ideal Solution (TOPSIS) method was proposed by Hwang and Yoon [26] in 1981 to determine the best alternative based on the concepts of the compromise solution [27, 28]. TOPSIS is widely used in decision-making [29 –31]. Because of incomplete or non-obtainable information, the data (attributes) are often not so deterministic [32]. Therefore, extension of the TOPSIS method for decision-making problems with fuzzy number was considered [33, 34]. Furthermore, TOPSIS has been extended with many math models. For example, D numbers [35 –37] is combined with TOPSIS to deal with linguistic decision making [38]. To address these issues, we propose an efficient workflow scheduling method for distributed systems based on triangular fuzzy numbers approach (WfSTFN). The proposed scheduling method enables efficient distribution of workflow tasks with different fuzzy computation and communication demands on networked resources. Effectiveness of the proposed scheduling method is demonstrated through a numerical experiment.

The rest of this paper is organized as follows. Section 2 briefly introduces the preliminaries of this paper. After that, a novel workflow scheduling approach on distributed systems under fuzzy environment is proposed in Section 3. Section 4 gives a numerical example to show the efficiency of the proposed method. Finally, conclusions are given in Section 5.

2 Preliminaries

2.1 Fuzzy number

Fuzzy set theory [23] provide an alternative and convenient framework for modeling of real-world fuzzy decision systems mathematically [39 –42], which has been widely applied in various fields, like information integration [43], sensor data fusion [44], strategy selection [45], tracking control [46], supplier selection [47], medical diagnosis [48, 49], and multi-criteria decision making [50 –54]. A fuzzy set is any set that allows its members to have different grades of membership in the interval [0,1]. It consists of two components: a set and a membership function associated with it.

Definition 2.1. (Fuzzy set) [23].

Let X be a collection of objects denoted generally by x, a fuzzy subset of X, $\tilde{a}$ , is a set of ordered pairs: $\tilde{a} = {(x, μ_{\tilde{a}} (x) | x \in X)},$ (1) where $μ_{\tilde{a}} (x) : X \to [0, 1]$ is called the membership function (generalized characteristic function) which maps X to the membership space M.

Definition 2.2. (Triangular fuzzy number) [23].

A fuzzy number is a fuzzy subset of X. And a triangular fuzzy number $\tilde{A}$ can be defined by a triplet (a, b, c) shown in Fig. 1, in which a, b and c are real numbers with a < b < c. Its membership function is defined as $μ_{\tilde{A}} (x) = {\begin{matrix} \begin{matrix} 0, & x < a \end{matrix} \\ \begin{matrix} \frac{x - a}{b - a}, & a \leq x \leq b \end{matrix} \\ \begin{matrix} \frac{c - x}{c - b}, & b \leq x \leq c \end{matrix} \\ \begin{matrix} 0, & x > c \end{matrix} \end{matrix} .$ (2)

Fig.1

A triangular fuzzy number.

Definition 2.3. (Distance between two triangular fuzzy number) [33].

Let $\tilde{A} = (a, b, c)$ and $\tilde{M} = (m, s, n)$ be two triangular fuzzy numbers, then the vertex method is defined to calculate the distance between them as $d (\tilde{A}, \tilde{M}) = \sqrt{\frac{1}{3} [(a - m)^{2} + (b - s)^{2} + (c - n)^{2}]} .$ (3)

2.2 TOPSIS method with fuzzy set

The main idea of TOPSIS is that the best compromise solution should have the shortest Euclidean distance from the positive ideal solution and the farthest Euclidean distance from the negative ideal solution.

The procedures of TOPSIS method with fuzzy set can be described as follows. Let A= {A_k|k = 1, 2, … , m } be the set of alternatives; C= {C_s| s = 1, 2, …, n} be the set of criteria; ${\tilde{x}}_{ij}$ be a fuzzy number (a_ks, b_ks, c_ks) representing the rating of alternative A_k with respect to criterion C_s; R = ${{\tilde{r}}_{ks} | k = 1, 2, \dots, m$ ; s = 1, 2, …, n} be the performance ratings with the criteria weight vector W = ${{\tilde{w}}_{s} | s = 1, 2, \dots, n}$ .

Step 1: Calculate normalized ratings.

Let B and C be the set of benefit criteria and cost criteria, respectively. The normalized value ${\tilde{r}}_{ks}$ is calculated by ${\tilde{r}}_{ks} = (\frac{a_{ks}}{c_{s}^{+}}, \frac{b_{ks}}{c_{s}^{+}}, \frac{c_{ks}}{c_{s}^{+}}), where c_{s}^{+} = \max_{k} (c_{ks}), s \in B,$ (4) ${\tilde{r}}_{ks} = (\frac{a_{s}^{-}}{c_{ks}}, \frac{a_{s}^{-}}{b_{ks}}, \frac{a_{s}^{-}}{a_{ks}}), where a_{s}^{-} = \min_{k} (a_{ks}), s \in C .$ (5)

Step 2: Calculate weighted normalized ratings.

In the weighted normalized decision matrix, the modified ratings are calculated by

$\begin{matrix} {\tilde{v}}_{ks} = {\tilde{w}}_{s} \times {\tilde{r}}_{ks} for k = 1, 2, \dots, m \\ and s = 1, 2, \dots, n, \end{matrix}$ (6) where ${\tilde{w}}_{s}$ is the weight of the s-th criteria.

Step 3: Determinate the fuzzy positive and negative ideal solutions.

The elements ${\tilde{v}}_{ij}$ , ∀i, j are normalized positive triangular fuzzy numbers and their ranges belong to the closed interval [0, 1]. Then, the fuzzy positive ideal solution (FPIS, A⁺) and the fuzzy negative ideal solution(FNIS, A^-) are derived as follows:

$A^{+} = {{\tilde{v}}_{1}^{+}, {\tilde{v}}_{2}^{+}, \dots {\tilde{v}}_{n}^{+}},$ (7)

$A^{-} = {{\tilde{v}}_{1}^{-}, {\tilde{v}}_{2}^{-}, \dots {\tilde{v}}_{n}^{-}},$ (8) where ${\tilde{v}}_{s}^{+} = (1, 1, 1)$ and ${\tilde{v}}_{s}^{-} = (0, 0, 0)$ , s = 1, 2, …, n.

Step 4: Calculate the distance of each alternative from the FPIS and the FNIS.

The distance of each alternative from A⁺ and A^- can be currently calculated as $d_{k}^{+} = \sum_{s = 1}^{n} d ({\tilde{v}}_{ks}, {\tilde{v}}_{s}^{+}), k = 1, 2, \dots m,$ (9) $d_{k}^{-} = \sum_{s = 1}^{n} d ({\tilde{v}}_{ks}, {\tilde{v}}_{s}^{-}), k = 1, 2, \dots m,$ (10) where d (· , ·) is the distance measurement between two fuzzy numbers.

Step 5: Calculate the relative closeness coefficient to the positive ideal solution.

The relative closeness coefficient for the alternative A_k with respect to A⁺ is $C_{k} = \frac{d_{k}^{-}}{d_{k}^{+} + d_{k}^{-}}, k = 1, 2, \dots m .$ (11)

Step 6. Rank the alternatives.

Obviously, an alternative A_k is closer to the FPIS (A⁺) and farther from FNIS(A^-) as C_k approaches to 1. Therefore according to relative closeness coefficient to the ideal alternative, larger value of C_k indicates the better alternative A_k.

2.3 Model

2.3.1 Assumptions and notations

Assumptions and notations for this paper are described as follows.

Assumptions.

(i) Each task can be processed on any machine.

(ii) The machines are fault-free.

(iii) Each machine/resource can process at most one task at a time

(iv) The computation time and communication time are assumed to be fuzzy variables.

(v) The workflow structures are single entry with single exit.

Notations.

t_i, i = 1, 2, …, n: the tasks to be scheduled;

t_entry: an entry task with no parent;

t_exit: an exit task with no child;

parent (t_i): the parent task(s) of task t_i;

h_j, j = 1, 2, …, m: the machines/resources;

T_i: the fuzzy completion time of task t_i;

T_make: the workflow makespan is the maximum completion time of all its n tasks;

ET_ij: the execution time of task t_i on r_j;

d_p,i: the number of bytes transferred from t_p to t_i;

b_p,i: the available bandwidth;

d_i: the deadline associated with task t_i;

$C_{comp} ({\tilde{t}}_{i})$ : the relative closeness coefficient for the alternative fuzzy computation time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution;

$C_{comm} ({\tilde{t}}_{i})$ : the relative closeness coefficient for the alternative fuzzy communication time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution.

2.3.2 System model

Figure 2 shows an example of a workflow management system (WfMS). The system is composed of networked homogenous resources. Once users submit requests to the workflow management system, along the workflow application, the system adopts a workflow scheduling to dispatch the tasks to avaiable workflow engines/processors that are hosted on the machines/resources. The workflow management system can provision dynamically to the workflow applications taking into account user QoS requirements (e.g., deadline) as well as the performance of the system (e.g., resource usage). In this paper, we focus on the workflow scheduling component of a workflow management system [55].

Fig.2

An example of a workflow management system.

2.3.3 Problem Statement

The key challenge in workflow scheduling is to decide the execution time and resource allocation of each of the atomic tasks. We consider a scheduling method that minimizes the total execution time of a workflow on set of resources, while satisfying a user-defined deadline. The workflow task scheduling problem is an optimization problem and can be formally expressed as follows [56]: $\min T_{make}$ (12) $s . t . T_{make} = \max_{1 \leq i \leq n} T_{i}$ (13) $T_{i} = {ET}_{ij} + {\begin{matrix} (\max_{t_{p} \in parent (t_{i})} T_{p} + \frac{d_{p, i}}{b_{p, i}}), if t_{i} \neq t_{entry} \\ 0, otherwise \end{matrix}$ (14) $\sum_{i = 1}^{n} x_{ij} = 1$ (15) $T_{i} x_{ij} \leq d_{i}, (1 \leq i \leq n, 1 \leq j \leq m)$ (16) $x_{ij} = {\begin{matrix} 1, if task t_{i} is assigned to resource r_{j} \\ 0, otherwise \end{matrix}$ (17)

Eq. (12) presents the workflow scheduling challenge which tends to find an assignment of the task t_i to the resource r_j such that the makespan is minimized. The workflow makespan is the maximum completion time of all its n tasks shown in Eq. (13). In Eq. (14), T_i denotes the fuzzy completion time of task t_i, where the first term ET_ij represents the execution time of task t_i on r_j, and the second term is the competition time of the parent tasks. If t_i has more than one parent task, we consider the parent task with the largest completion time will be selected. In Eq. (15), each task must be allocated to one available resource capable of executing the task. Eq. (16) ensures that each resource executes the tasks within the given deadline. In Eq. (17), x_ij is a variable indicating whether task t_i is assigned to resource r_j.

3 The proposed method

In this section, a novel workflow scheduling method for distributed systems based on triangular fuzzy numbers approach (WfSTFN) is proposed. Our proposal is inspired by [23] and [56]. The WfSTFN minimizes the makespan of the workflow application for distributed systems, while improving system performance and end user satisfaction.

Figure 3 illustrates the flow graph of the WfSTFN approach. Essentially, the proposed method consists of five steps. We will now explain each of the steps in detail.

Fig.3

A flow graph of the WfSTFN.

Step 1: Determining task levels.

As we discussed in Section 1, workflow applications can be divided into two sets of tasks. The first set of tasks are interdependent, in which the execution order must be coordinated such that a task will execute only after its immediate parent tasks have completed execution and the input data is readily available. The second set of tasks are independent, in which their execution order can be interleaved. Hence, these independent tasks compete for resources. Therefore, the layers of a workflow depend on the complexity of the interdependent task is taken into consideration within the workflow execution.

Fig. 4 shows an example of the layers of a workflow that is a four-layer workflow. There are 10 tasks with different fuzzy computation time and communication time shown in Table 1. As shown in Fig. 4, the workflow has layers and arc. The dotted lines indicates the layers for the workflow (layers 1-4). Each arc represents a precedence constraint which indicates that task t_p should complete execution before task t_i can start. In layer 2, there are four tasks (e.g., t₂, t₃, t₄, and t₅) with one parent (e.g., t₁). In layer 3, there are four tasks (e.g., t₆, t₇, t₈, and t₉) that have more than one parent (e.g., t₃, t₄, and t₅). We use parent (t_i) to denote the set of parents of task t_i, in which the set of parents are need to be completed before starting t_i. Similarly, a task can have no child (e.g. t₁₀), one child (e.g., t₉) or more than one child (e.g., t₃).

Fig.4

An example of the layers of a workflow.

Table 1

Workflow task with fuzzy computation and communication time

Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
Comp	(18,19,20)	(12,14,15)	(17,19,20)	(17,19,20)	(3,4,5)	(2,4,5)	(8,9,10)	(13,14,15)	(17,18,20)	(15,17,20)
Comm	(0,0,0)	(1,2,2)	(2,3,4)	(5,6,8)	(5,6,8)	(2,3,4)	(7,8,8)	(6,7,8)	(6,7,8)	(4,6,8)

Step 2: Task prioritizing based on the total number of dependency tasks.

In this step, the tasks prioritization is based on the task layers. For each layer, the tasks will be prioritized in terms of the total number of dependency tasks denoted as Num_depend (t_i) that consists of the number of children and the number of parents. And, this task prioritizing process will be done recursively until to the last task. Note that, the task on the first, namely, entry task is always assigned priority level 1.

We first compute the number of children and the number of parents for tasks in the workflow. Secondly, we add the above two numbers to create the total number of dependency tasks. Thirdly, we retrieve tasks for each layer and assigns the priority to tasks based on the location within the layer and the total number of dependency tasks.

Step 3: Task prioritizing based on the fuzzy computation time.

The purpose of Step 3 is to prioritize the tasks with the same number of dependency tasks. In this step, the tasks prioritization is also based on the task layers. For each layer, the tasks will be prioritized in terms of the fuzzy computation time. As we described in Section 2, C_k is defined as the relative closeness coefficient for the alternative A_k with respect to A⁺. The bigger the value of C_k is, the better alternative A_k is. We denote $C_{comp} ({\tilde{t}}_{i})$ as the relative closeness coefficient for the alternative fuzzy computation time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution. Therefore, we order the tasks with different fuzzy computation time according to the value of $C_{comp} ({\tilde{t}}_{i})$ .

Step 4: Task prioritizing based on the fuzzy communication time.

The purpose of Step 4 is to prioritize the tasks with the same number of dependency tasks and the same fuzzy communication time. In this step, the tasks prioritization is also based on the task layers. In each layer, the tasks will be prioritized in terms of the fuzzy communication time. We denote $C_{comm} ({\tilde{t}}_{i})$ as the relative closeness coefficient for the alternative fuzzy communication time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution. Similarly with Step 3, we order the tasks with different fuzzy communication time according to the value of $C_{comm} ({\tilde{t}}_{i})$ .

Step 5: Resource Selection.

On the basis of previous four steps, the new prioritized task scheduling list ready to be executed to the available resources, based on the computation of the time slots they are assigned to. The resources are selected based on the readiness of the resources. It means that the task will be scheduled to the resources which finishes the earliest task execution denoted as R_{t
_i}.

4 Numerical example

In this section, a numerical example is provided to demonstrate the effectiveness and advantages of our proposed method. This numerical example is based on the workflow of Fig. 4 where there are 10 tasks with different fuzzy computation time and communication time as shown in Table 1. Here, we assume that the workflow of Fig. 4 satisfies the user-defined deadline.

Step 1.

By taking the complexity of the interdependent task into consideration within the workflow execution, the layers of tasks are decided. As shown in Table 2, entry task t₁ belongs to layer 1. Tasks t₂, t₃, t₄, and t₅ belong to layer 2, while tasks t₆, t₇, t₈, and t₉ belong to layer 3. Exit task t₁₀ belongs to layer 4.

Step 2.

We calculate the total number of dependency tasks for each task in terms of the number of children and the number of parents. Then, we retrieve tasks for each layer and assigns the priority to tasks based on the location within the layer and the total number of dependency tasks as shown in Table 3. Note that, the entry task t₁ is assigned priority level 1. Task t₃ has the same number of dependency tasks as t₄, while task t₈ has the same number of dependency tasks with t₉.

Table 2
The layers of a workflow

Layer 1 2 2 2 2 3 3 3 3 4

Tasks t ₁ t ₂ t ₃ t ₄ t ₅ t ₆ t ₇ t ₈ t ₉ t ₁₀

Table 3

Workflow task dependency table

Layer	1	2	2	2	2	3	3	3	3	4
Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
Num _depend	4	1	3	3	2	1	3	2	2	3
Rank _num	1	5	2	2	4	9	6	7	7	10

Step 3.

We calculate the relative closeness coefficient for the alternative fuzzy computation time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution by $C_{comp} ({\tilde{t}}_{i})$ . The computational procedure of $C_{comp} ({\tilde{t}}_{i})$ is summarized as follows:

Step 3.1: Construct the normalized fuzzy decision matrix as Table 4.

Table 4

The normalized fuzzy decision matrix

Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
Comp	(0.9,0.95,1)	(0.6,0.7,0.75)	(0.85,0.95,1)	(0.85,0.95,1)	(0.15,0.2,0.25)	(0.1,0.2,0.25)	(0.4,0.45,0.5)	(0.65,0.7,0.75)	(0.85,0.9,1)	(0.75,0.85,1)

Step 3.2: Determine FPIS (A⁺) and FNIS (A^-) as

$\begin{matrix} A^{+} = [(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), \\ (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)], \end{matrix}$ $\begin{matrix} A^{-} = [(0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), \\ (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0)] . \end{matrix}$

Step 3.3: Calculate the distance of each alternative from FPIS and FNIS, respectively, as Table 5.

Table 5

The distance measurement

	A _{t ₁}	A _{t ₂}	A _{t ₃}	A _{t ₄}	A _{t ₅}	A _{t ₆}	A _{t ₇}	A _{t ₈}	A _{t ₉}	A _{t ₁₀}
A ⁺	0.0645	0.3227	0.0913	0.0913	0.8010	0.8190	0.5515	0.3208	0.1041	0.1683
A ^-	0.9509	0.6862	0.9354	0.9354	0.2041	0.1936	0.4518	0.7012	0.9188	0.8727

Step 3.4: Calculate the closeness coefficient of each alternative as Table 6.

Table 6

The closeness coefficient of each alternative

Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
$C_{comp} ({\tilde{t}}_{i})$	0.9364	0.6801	0.9111	0.9111	0.2031	0.1912	0.4503	0.6984	0.8982	0.8383

Step 3.5: According to the closeness coefficient, the ranking order of the alternatives with the same number of dependency tasks can be determine as Table 8. From the results, we can notice that tasks t₈ and t₉ can be prioritized by the value of $C_{comp} ({\tilde{t}}_{i})$ in terms of the fuzzy computation time, while task t₃ still has the same value of $C_{comp} ({\tilde{t}}_{i})$ as t₄.

Table 7

Nearness degree table in terms of fuzzy computation time

Layer	1	2	2	2	2	3	3	3	3	4
Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
Num _depend	4	1	3	3	2	1	3	2	2	3
Rank _num	1	5	2	2	4	9	6	7	7	10
Rank _comp	1	5	2	2	4	9	6	8	7	10

Table 8

The closeness coefficient of each alternative

Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
$C_{comm} ({\tilde{t}}_{i})$	0	0.2143	0.3803	0.7561	0.7561	0.3803	0.9301	0.8452	0.8452	0.7066

Step 4.

Similarly, we calculate the relative closeness coefficient for the alternative fuzzy communication time ${\tilde{t}}_{i}$ with respect to the triangular fuzzy ideal solution by $C_{comm} ({\tilde{t}}_{i})$ as Table 7. Because the computational procedures of $C_{comm} ({\tilde{t}}_{i})$ is similar with $C_{comp} ({\tilde{t}}_{i})$ , we ignore the discussion here. According to the closeness coefficient, the ranking order of all alternatives can be determine as Table 9. From the results, we can notice that tasks t₃ and t₄ can be prioritized by the value of $C_{comm} ({\tilde{t}}_{i})$ in terms of the fuzzy communication time.

Table 9

Nearness degree table in terms of fuzzy communication time

Layer	1	2	2	2	2	3	3	3	3	4
Tasks	t ₁	t ₂	t ₃	t ₄	t ₅	t ₆	t ₇	t ₈	t ₉	t ₁₀
Num _depend	4	1	3	3	2	1	3	2	2	3
Rank _num	1	5	2	2	4	9	6	7	7	10
Rank _comp	1	5	2	2	4	9	6	8	7	10
Rank _comm	1	5	3	2	4	9	6	8	7	10

Step 5.

Based on the the Rank_comm in Table 9, the task scheduling list is generated. Then, we schedule the new task scheduling list to the available resources. We assume there are three resources (R₁, R₂ and R₃). Considering user quality of service (QoS) expectations, we use the largest computation time and communication time when allocating the tasks. The resources are selected based on the readiness of the resources. The earliest start time for each task in all three resources will be computed. The scheduling trace of the new list is shown in Table 10. In the table, the execution start times of each node on all resources at each step are given. Meanwhile, the nodes on the list are scheduled one by one, to the available resources that have the earliest start time.

Table 10

Resource mapping table

Task list	Prioritize list	R ₁	R ₂	R ₃	Resource list
t ₁	t ₁	0	0	0	R ₁
t ₂	t ₄	20	28	28	R ₁
t ₃	t ₃	40	24	24	R ₂
t ₄	t ₅	40	44	28	R ₃
t ₅	t ₂	40	44	33	R ₃
t ₆	t ₇	40	44	48	R ₁
t ₇	t ₉	50	44	48	R ₂
t ₈	t ₈	50	64	48	R ₃
t ₉	t ₆	50	64	63	R ₁
t ₁₀	t ₁₀	55	64	63	R ₁

In order to demonstrate the effectiveness of the WfSTFN scheduling approach, we compare it with the earliest time first (ETF) scheduling approach by considering the resources that the tasks are most likely needed. The ETF scheduling approach searches for the earliest time for all tasks where it chooses the tasks with the minimum value. Specifically, the ETF first computes the computation cost and communication cost for each task. Based on the sum value of computation cost and communication cost, the tasks will be sorted and ranked. After implementing the WfSTFN and ETF scheduling approaches, the makespan for the two methods are shown in Fig. 5 and Fig. 6, respectively. It is easy noticed that the makespan for the WfSTFN scheduling approach is 84 ms, while the makespan for the ETF scheduling approach is 88 ms. Consequently, it can be concluded that the makespan is minimized by utilizing the proposed WfSTFN method.

Fig.5

The makespan for the WfSTFN scheduling approach.

Fig.6

The makespan for the ETF scheduling approach.

5 Conclusion

In this paper, we started off with identifying the general problems of scheduling tasks with fuzzy completion time in a distributed computing environment. We proposed a novel workflow scheduling method for distributed systems based on triangular fuzzy numbers approach (WfSTFN), which could minimize the makespan of the workflow application. The main idea of WfSTFN approach is to achieving user QoS requirements as well as the performance of the system. A numerical example was illustrated to demonstrate the effectiveness of our proposed method. In this study, we only consider the single-entry-single-exit workflow structure problem. In the future work, we would like to consider more complexity structure with multiple-entries-multiple-exits workflow.

6 Compliance with Ethical Standards

Funding: This research is supported by the Fundamental Research Funds for the Central Universities (No. XDJK2019C085) and Chongqing Overseas Scholars Innovation Program (No. cx2018077).

Disclosure of potential conflicts of interest: Author F.X. declares that she has no conflict of interest. Author Z.Z. declares that he has no conflict of interest. Author A.J. declares that he has no conflict of interest.

Research involving human participants and/or animals: This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent: Informed consent was obtained from all individual participants included in the study.

Footnotes

Acknowledgment

The author greatly appreciates the reviews’ suggestions and the editor’s encouragement.

References

Arabnejad

, Bubendorfer

and Ng

, Budget and deadline aware e-science workow scheduling in clouds, IEEE Transactions on Parallel and Distributed Systems 30(1) (2019), 29–44.

Partheeban

and Kavitha

, Versatile provisioning and workow scheduling in WaaS under cost and deadline constraints for cloud computing, Transactions on Emerging Telecommunications Technologies 30(1) (2019), e3527.

Guo

, Lin

, Chen

and Liang

, Cost-driven scheduling for deadline-based workow across multiple clouds, IEEE Transactions on Network and Service Management 15(4) (2018), 1571–1585.

Iyenghar

and Pulvermueller

, A model-driven workow for energy-aware scheduling analysis of IoT-enabled use cases, IEEE Internet of Things Journal 5(6) (2018), 4914–4925.

Ghafouri

, Movaghar

and Mohsenzadeh

, Time-cost efficient scheduling algorithms for executing workow in infrastructure as a service clouds, Wireless Personal Communications 103(3) (2018), 2035–2070.

Emmanuel

, Qin

, Wang

, Zhang

and Zheng

, Cost optimization heuristics for deadline constrained workow scheduling on clouds and their comparative evaluation, Concurrency and Computation: Practice and Experience 30(20) (2018), e4762.

Zhou

, Li

, Xu

and Qi

, Concurrent workow budget-and deadline-constrained scheduling in heterogeneous distributed environments, Soft Computing 22(23) (2018), 7705–7718.

Aziz

M.A.

, Abawajy

and Herawan

, Layered workow scheduling algorithm, in: 2015 IEEE International Conference on Fuzzy Systems, IEEE, 2015, pp. 1–7.

Khorsand

, Safi-Esfahani

, Nematbakhsh

and Mohsenzade

, ATSDS: Adaptive two-stage deadline-constrained workow scheduling considering run-time circumstances in cloud computing environments, The Journal of Supercomputing 73(6) (2017), 2430–2455.

10.

Wang

, Sun

, Su

S.-F.

and Wang

, Fuzzy uncertainty observer-based path-following control of underactuated marine vehicles with unmodeled dynamics and disturbances, International Journal of Fuzzy Systems 20(8) (2018), 2593–2604.

11.

Zhou

, Al-Durra

, Zhang

, Ravey

and Gao

, Online remaining useful lifetime prediction of proton exchange membrane fuel cells using a novel robust methodology, Journal of Power Sources 399 (2018), 314–328.

12.

S.-F.

, Hsueh

Y.-C.

, Tseng

C.-P.

, Chen

S.-S.

and Lin

Y.-S.

, Direct adaptive fuzzy sliding mode control for under-actuated uncertain systems, International Journal of Fuzzy Logic and Intelligent Systems 15(4) (2015), 240–250.

13.

Zavadskas

E.K.

and Podvezko

, Integrated determination of objective criteria weights in MCDM, International Journal of Information Technology & Decision Making 15(02) (2016), 267–283.

14.

Pan

and Deng

, A new belief entropy to measure uncertainty of basic probability assignments based on belief function and plausibility function, Entropy 20(11) (2018), 842.

15.

Jiang

and Hu

, An improved soft likelihood function for Dempster-Shafer belief structures, International Journal of Intelligent Systems 33(6) (2018), 1264–1282.

16.

Sun

and Deng

, A new method to identify incomplete frame of discernment in evidence theory, IEEE Access 7(1) (2019), 15547–15555.

17.

Yager

R.R.

, Categorization in multi-criteria decision making, Information Sciences 460 (2018), 416–423.

18.

and Jiang

, An evidential dynamical model to predict the interference effect of categorization on decision making results, Knowledge-Based Systems 150 (2018), 139–149.

19.

Kang

, Deng

, Hewage

and Sadiq

, A method of measuring uncertainty for Z-number, IEEE Transactions on Fuzzy Systems 27(4) (2019), 731–738.

20.

Yang

, Gao

and Ni

, Resolution principle in uncertain random environment, IEEE Transactions on Fuzzy Systems 26(3) (2018), 1578–1588.

21.

Deng

, Analyzing the monotonicity of belief interval based uncertainty measures in belief function theory, International Journal of Intelligent Systems 33(9) (2018), 1869–1879.

22.

Zavadskas

E.K.

, Bausys

, Kaklauskas

, Ubarte

, Kuzminske

and Gudiene

, Sustainable market valuation of buildings by the single-valued neutrosophic MAMVA method, Applied Soft Computing 57 (2017), 74–87.

23.

Zadeh

L.A.

, Fuzzy sets, Information and control 8(3) (1965), 338–353.

24.

Chen

and Yu

, Emergency alternative selection based on an E-IFWA approach, IEEE Access 7 (2019), 44431–44440.

25.

Zhou

, Liu

and Yang

, Evidential reasoning approach for MADM based on incomplete interval value, Journal of Intelligent & Fuzzy Systems 33(6) (2017), 3707–3721.

26.

Hwang

C.-L.

and Yoon

, Methods for multiple attribute decision making, in: Multile attribute decision making, Springer, 1981, pp. 58–191.

27.

Hussain

and Yang

M.-S.

, Entropy for hesitant fuzzy sets based on Hausdorff metric with construction of hesitant fuzzy TOPSIS, International Journal of Fuzzy Systems 20(8) (2018), 2517–2533.

28.

Shaverdi

, Ramezani

, Tahmasebi

and Rostamy

A.A.A.

, Combining fuzzy ahp and fuzzy topsis with financial ratios to design a novel performance evaluation model, International Journal of Fuzzy Systems 18(2) (2016), 248–262.

29.

Zavadskas

E.K.

, Mardani

, Turskis

, Jusoh

and Nor

K.M.

, Development of TOPSIS method to solve complicated decision-making problems-an overview on developments from 2000 to 2015, International Journal of Information Technology & Decision Making 15(03) (2016), 645–682.

30.

Samanlioglu

, Taskaya

Y.E.

, Gulen

U.C.

and Cokcan

, A fuzzy AHP-TOPSIS-based group decision-making approach to IT personnel selection, International Journal of Fuzzy Systems 20(5) (2018), 1576–1591.

31.

Lin

C.-M.

and Huynh

T.-T.

, Function-link fuzzy cerebellar model articulation controller design for nonlinear chaotic systems using TOPSIS multiple attribute decision-making method, International Journal of Fuzzy Systems (2018), 1–18.

32.

Zhou

, Liu

X.-B.

, Chen

Y.-W.

and Yang

J.-B.

, Evidential reasoning rule for MADM with both weights and reliabilities in group decision making, Knowledge-Based Systems 143 (2018), 142–161.

33.

Chen

C.-T.

, Extensions of the TOPSIS for group decision-making under fuzzy environment, Fuzzy Sets and Systems 114(1) (2000), 1–9.

34.

Vahdani

, Mousavi

S.M.

and Tavakkoli-Moghaddam

, Group decision making based on novel fuzzy modified TOPSIS method, Applied Mathematical Modelling 35(9) (2011), 4257–4269.

35.

and Deng

, A new MADA methodology based on D numbers, International Journal of Fuzzy Systems 20(8) (2018), 2458–2469.

36.

Xiao

, A multiple criteria decision-making method based on D numbers and belief entropy, International Journal of Fuzzy Systems 21(4) (2019), 1144–1153.

37.

Zhao

and Deng

, Performer selection in Human Reliability analysis: D numbers approach, International Journal of Computers Communications & Control 14(3) (2019), 437–452.

38.

Bian

, Zheng

, Yin

and Deng

, Failure mode and effects analysis based on D numbers and TOPSIS, Quality and Reliability Engineering International 34(4) (2018), 501–515.

39.

Yager

R.R.

, Multicriteria decision making with ordinal/linguistic intuitionistic fuzzy sets for mobile apps, IEEE Transactions on Fuzzy Systems 24(3) (2016), 590–599.

40.

Song

, Wang

, Quan

and Huang

, A new approach to construct similarity measure for intuitionistic fuzzy sets, Soft Computing (2017), 1–14.

41.

Herrera

, Herrera-Viedma

and Martínez

, A fusion approach for managing multi-granularity linguistic term sets in decision making, Fuzzy sets and systems 114(1) (2000), 43–58.

42.

S.-F.

, Chen

M.-C.

and Hsueh

Y.-C.

, A novel fuzzy modeling structure-decomposed fuzzy system, IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(8) (2017), 2311–2317.

43.

Liu

Y.-T.

, Pal

N.R.

, Marathe

A.R.

and Lin

C.-T.

, Weighted fuzzy Dempster-Shafer framework for multimodal information integration, IEEE Transactions on Fuzzy Systems 26(1) (2018), 338–352.

44.

Song

, Wang

, Zhu

and Lei

, Sensor dynamic reliability evaluation based on evidence theory and intuitionistic fuzzy sets, Applied Intelligence (2018), 1–13.

45.

Zavadskas

E.K.

, Turskis

, Vilutienė

and Lepkova

, Integrated group fuzzy multi-criteria model: Case of facilities management strategy selection, Expert Systems with Applications 82 (2017), 317–331.

46.

Wang

, Su

S.-F.

, Yin

, Zheng

and Er

M.J.

, Global asymptotic model-free trajectory-independent tracking control of an uncertain marine vehicle: An adaptive universe-based fuzzy control approach, IEEE Transactions on Fuzzy Systems 26(3) (2018), 1613–1625.

47.

Fei

, Deng

and Hu

, DS-VIKOR: A new multi-criteria decision-making method for supplier selection, International Journal of Fuzzy Systems 21(1) (2019), 157–175.

48.

Xiao

and Ding

, Divergence measure of Pythagorean fuzzy sets and its application in medical diagnosis, Applied Soft Computing 79 (2019), 254–267.

49.

Cao

and Lin

C.T.

, Inherent fuzzy entropy for the improvement of EEG complexity evaluation, IEEE Transactions on Fuzzy Systems 26(2) (2018), 1032–1035.

50.

Han

, Deng

, Cao

and Lin

C.-T.

, An interval-valued Pythagorean prioritized operator based game theoretical framework with its applications in multicriteria group decision making, Neural Computing and Applications (2019) DOI: 10.1007/s00521-019-04014-1.

51.

Wang

, Liu

and Wei

, A modified D numbers’ integration for multiple attributes decision making, International Journal of Fuzzy Systems 20(1) (2018), 104–115.

52.

Han

and Deng

, A hybrid intelligent model for assessment of critical success factors in high-risk emergency system, Journal of Ambient Intelligence and Humanized Computing 9(6) (2018), 1933–1953.

53.

Wei

G.-W.

, Maximizing deviation method for multiple attribute decision making in intuitionistic fuzzy setting, Knowledge-Based Systems 21(8) (2008), 833–836.

54.

Fei

, Wang

, Chen

and Deng

, A new vector valued similarity measure for intuitionistic fuzzy sets based on OWA operators, Iranian Journal of Fuzzy Systems 16(3) (2019), 113–126.

55.

Beloglazov

, Abawajy

and Buyya

, Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing, Future Generation Computer Systems 28(5) (2012), 755–768.

56.

Aziz

M.A.

, Abawajy

and Herawan

, Layered workow scheduling algorithm, IEEE International Conference on Fuzzy Systems, Istanbul, Turkey, 2015.

Workflow scheduling in distributed systems under fuzzy environment

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Fuzzy number

2.3.1 Assumptions and notations

2.3.2 System model

Table 2 The layers of a workflow Layer 1 2 2 2 2 3 3 3 3 4 Tasks t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10

6 Compliance with Ethical Standards

Footnotes

Acknowledgment

References

Table 2
The layers of a workflow

Layer 1 2 2 2 2 3 3 3 3 4

Tasks t ₁ t ₂ t ₃ t ₄ t ₅ t ₆ t ₇ t ₈ t ₉ t ₁₀