1 Introduction

For last several years, distributed computing have become user friendly and a very popular choice for effective and efficient use of resources and for information processing. The benefits of distributed computing are: better throughput, effective use of available resources and access to wide web of information. Distributed computing has many challenges. A fair and balanced load distribution is one such challenge. Improperly distributed load results in reduced performance of the system. Therefore task scheduling is a vital step for better performance of the system, which can be done in the following ways:

Static Allocation In static allocation, the information of the current stage of nodes is not used for assigning the tasks. Thus an assignment pattern is needed to be found that holds for a life time of a program and results in optimum throughput [1].

Dynamic Allocation In dynamic allocation, the information of current state of the system is used. To update the information of the system, exchange of information is necessary [2].

Static allocation is simple in implementation but is not adaptable to the changes in system i.e. it does not change the task distribution as the system state changes. Different static allocation algorithms are discussed in [3,4,5,6,7]. Better performance is given by dynamic allocation methods over static methods as in dynamic methods, the distribution configuration changes with change in system, but it results in complicated algorithms [8,9,10,11].

A various number of methods are available for task distribution in distributed environment. One of the techniques is branch and bound technique as stated in [12,13,14]. Another method is integer programming which is a mathematical optimization technique where some variables are restricted to be integers. For task allocation problems, integer programming is simple in application. Another method for task distribution, which gives a near optimal solution is Genetic Algorithm (GA) which fosters a population of strings (chromosomes) using predefined genetic operators [15, 16]. The process of selection, crossover and mutation is repeated until the condition for termination is satisfied.

1.1 Preliminaries

  • Fuzzy Execution Time (FET): The execution time, \(\tilde{e}_{ij} ,\) is the amount of time taken by task \(t_{i}\), which is to be executed on the processor \(p_{j}\), where \(1 \le i \le m , 1 \le j \le n\). If a task \(t_{i}\) is assigned to a processor \(p_{j}\) but is not executed due to absence of some resources, then \(\tilde{e}_{ij}\) of the task on the processor is taken to be zero [17].

  • Fuzzy Inter Task Communication Time (FITCT): The Fuzzy Inter Task Communication Time, \(\tilde{c}_{ik}\), is the amount of time incurred due to the data units exchanged between the tasks \(t_{i}\) and \(t_{k}\) if they are executed on different processors. When some tasks are assigned to same processor, then \(\tilde{c}_{ik} = 0\). Fuzzy Inter-Task Communication Times for processor \(P_{j}\) is calculated by using Eq. (1) given as follows [17]:

    $$FITCT_{j} = \mathop \sum \limits_{i \ne k} \left[ {\tilde{c}_{ik} } \right], (k = 1,2,3, \ldots ,m),\;\;\;1 \le j \le n.$$
    (1)

  • Triangular Fuzzy Number: A triangular fuzzy number A(x) can be represented by A(a,b,c;1) shown in Fig. 1, with membership function \(\mu (x)\) [18, 19].

    Fig. 1
    figure 1

    Triangular fuzzy number

    Full size image
    $$\mu \left( x \right) = \left\{ {\begin{array}{*{20}c} {\frac{x - a}{b - a} ,} & {a \le x \le b} \\ 1 & {x = b} \\ {\frac{c - x}{c - b} ,} & {b \le x \le c} \\ {0 , } & {Otherwise} \\ \end{array} } \right..$$

  • Trapezoidal Fuzzy Number: A trapezoidal fuzzy number A(x) represented by A(a,b,c,d;1) as shown in Fig. 2, with membership value \(\mu (x)\) [18, 19].

    Fig. 2
    figure 2

    Trapezoidal fuzzy number

    Full size image
    $$\mu \left( x \right) = \left\{ {\begin{array}{*{20}c} {\frac{x - a}{b - a} ,} & {a \le x \le b} \\ 1 & {b \le x \le c} \\ {\frac{d - x}{d - c} ,} & {c \le x \le d} \\ {0 , } & {Otherwise} \\ \end{array} } \right..$$

  • Defuzzification: The method of converting the fuzzy number into crisp value is defuzzification. Here the Fuzzy numbers (triangular/trapezoidal) are converted into crisp values by using Robust Ranking Method (RRM), which is represented by Eq. 2 [20].

    $$a_{ij} = R\left( {\tilde{a}_{ij} } \right) = \frac{1}{2}\mathop \int \limits_{0}^{1} \left( {a_{\alpha }^{L} + a_{\alpha }^{U} } \right)d\alpha .$$
    (2)

2 Proposed algorithm

2.1 Fetch the data set

Fetch the data set in the form of triangular/trapezoidal fuzzy numbers. Inputs are:

  1. 1.

    A program of \(m\) tasks i.e. \(\left\{ {t_{1} ,t_{2} ,t_{3} , \ldots ,t_{m} } \right\}.\)

  2. 2.

    A set of \(n\) processors i.e. \(\left\{ {P_{1} ,P_{2} ,P_{3} , \ldots ,P_{n} } \right\}\).

  3. 3.

    FET \(\left( {\tilde{e}_{ij} } \right)\) and FITCT \(\left( {\tilde{c}_{ik} } \right)\) are in the form of triangular/trapezoidal fuzzy numbers. FET and FITCT are taken in the form of matrices as Fuzzy Execution Time Matrix (FETM) and Fuzzy Inter Task Communication Time Matrix (FITCTM).

2.2 Determination of minimum link (ML)

Find those “n” tasks, which have minimum link with other tasks using Eq. (1). This minimum link is stored in a two dimensional array, Minimum Link (ML), the first column of which represents the task number and second column represents the average minimum link between the tasks. The ML in fuzzy form is defuzzified into crisp values using Robust Ranking Method (RRM). This array is sorted in ascending order by assuming second column as sorting key, to find which tasks are to be allocated first.

2.3 Determination of initial assignment for tasks with minimum execution time using Hungarian method

Select first “n” tasks from minimum linked array and apply Hungarian method to these “n” tasks in FETM, to allocate the tasks to the processors, having minimum execution time. Even if there is tie between two or more tasks in defuzzified ML array, the above mentioned method is used for the assignment of tasks. But now the task is assigned to the processor for which execution time is minimum in FETM. Let \(T_{assgn}\) denotes the set of tasks assigned to processors \(P_{j}^{\prime } s , j = 1,2,3, \ldots ,n\) and \(T_{non - assgn}\) denotes a set of \((m - n)\) task, \(m\; \gg \;n,\) which are not assigned to any of the processors. Then all tasks are given by union of these two as Eq. (3).

$$T = T_{assgn} {\text{U }}T_{non - assgn} .$$
(3)

2.4 Fusion of remaining unassigned tasks

Remaining \(\left( {m - n} \right)\) unassigned tasks are stored in an array \(T_{non - assgn}\). Pick one non assigned task and fuse it with all assigned tasks one by one to calculate Process Response Time (PRT). The Fused Fuzzy Execution Time (FFET) of a task \(t_{a} \in T_{non - assgn}\) with some other task \(t_{i} \in T_{assgn}\) on processor \(P_{j}\) is obtained using Eq. (4).

$$FFET_{ai} = \left[ {\tilde{e}_{aj} \; + \;\tilde{e}_{ij} } \right], 1 \le i \le m , 1 \le j \le n , \left( {m - n} \right) \le a \le m, i \ne a.$$
(4)

Let \(\tilde{c}_{ai}\) be the Fused Fuzzy Inter Task Communication Time (FFITCT) between \(t_{a} \in T_{non - assgn}\) and \(t_{i} \in T_{assgn}\). The FFITCT for \(t_{a} \,with\, t_{i}\) is obtained using Eq. (5).

$$FFITCT_{ai} = \mathop \sum \limits_{{\begin{array}{*{20}c} {t_{i} \in T_{assgn} } \\ {a \ne i} \\ \end{array} }} \left[ {\tilde{c}_{ai} } \right].$$
(5)

Here \(\tilde{c}_{ai} = 0\;\; if \, a = i\) (i.e. if \(t_{a}\) is fused with \(t_{i}\)) and the remaining values of \(\tilde{c}_{ai}\) are added.

2.5 Fused process response time (FPRT)

The Fused Process Response Time (FPRT) is calculated using Eq. (6) as follows:

$$FPRT_{ai} = \hbox{min} \left\{ {(FFET_{a1} + FFITCT_{a1} ), \left( {(FFET_{a2} + FFITCT_{a2} } \right), \ldots ,(FFET_{am} + FFITCT_{am} )} \right\}.$$
(6)

FPRT is in the form of triangular/trapezoidal fuzzy numbers, which is then converted into crisp values using RRM given by Eq. (2). Task \(t_{a} \in T_{non - assgn}\) is assigned to that processor for which FPRT, i.e. \((FFET_{ai} + FFITCT_{ai} )\), is minimum. This process is continued until all the tasks, \(t_{a} \in T_{non - assgn}\, \forall \,(m-n)\leq a \leq m ,\) are fused with the already assigned tasks, \(t_{i} \in T_{assgn}\, \forall \,1 \leq i\leq m\).

2.6 Overall process response time (OPRT)

When the procedure of assigning the tasks to different processors gets over, the OPRT for the distribution is calculated using Eqs. (4) and (5). These values are then converted into crisp values using Eq. (2). The OPRT, after assigning all the tasks, is calculated using Eq. (7) as follows:

$$OPRT = \hbox{max} \left\{ {FFET\left. { +\,\, FFITCT} \right)} \right..$$
(7)

Flow Chart of the algorithm is shown in Fig. 3.

Fig. 3
figure 3

Flowchart showing the sequence of proposed algorithm

Full size image

2.7 Illustrated examples

This section will illustrate the proposed method by using two scenarios:

2.8 Scenario I

In this example triangular fuzzy numbers are taken to test the proposed algorithm:

Consider a fuzzy DCS consists of set \(T = \left\{ {t1,t2,t3,t4,t5} \right\} \;of\; tasks\; m\; = \;5\) and a set \(P = \left\{ {P_{1} ,P_{2} ,P_{3} } \right\}\) of processors \(n = 3\).The execution time of each task on processors and inter task communication time between communicating tasks has been taken in the form of matrix FET \(\left[ {\tilde{e}_{ij} } \right]\) and FITCT \(\left[ {\tilde{c}_{ik} } \right]\) of order \(m \times n\) and \(m \times m\) respectively, whose elements are triangular fuzzy numbers as given in Tables 1 and 2 [17].

Table 1 Fuzzy execution time matrix
Full size table
Table 2 Fuzzy inter task communication time matrix
Full size table

From Table 2, minimum linked tasks are calculated shown in Table 3.These tasks are then converted into crisp values using RRM (Eq. 2) and then arranged in ascending order as shown in Table 4.

Table 3 List of minimum linked task
Full size table
Table 4 Listed minimum linked tasks in ascending order
Full size table

To assign ML tasks to processors, Hungarian method is used and the tasks are allocated as shown in Table 5.

Table 5 Initial assigned tasks on processors (Using Hungarian Method) are as follows:
Full size table

Tasks are assigned by Hungarian Method by considering t1, t4 and t5 vs P2, P3, P1.

$$T_{assgn} = \left\{ {t1,t4,t5} \right\} \to \left( {P2,P3,P1} \right)\;{\text{and}}\;T_{non - assgn} = \{ t2,t3\} .$$

To allocate task t2, it is fused with the already allocated tasks one by one and finally fused with the task having minimum PRT as shown in Table 6:

Table 6 List of fusion of unassigned task t2 with already assigned tasks
Full size table

Minimum cost is (115,180,245). So task t2 is fused with t5 on processor P1.

$$\begin{aligned} T_{assgn} = & \left\{ {t1,t2,t4,t5} \right\} \to (P2,P1,P3,P1) \\ T_{non - assgn} = & \{ t3\} . \\ \end{aligned}$$

The above step is repeated for task t3 as shown in Table 7. Now fusing the remaining task t3 with initially allocated tasks:

Table 7 List of fusion of unassigned task t3 with already assigned tasks
Full size table

Minimum cost is (125,190,260). So task t3 is fused with t5 on processor P1.

Final list of assignment of all tasks on each processor is shown in Table 8.

Table 8 Final list of assigned tasks
Full size table

For Overall Process Response Time (OPRT), the total cost for all distributed tasks is calculated as shown in Table 9:

Table 9 Final allocation task list with calculated OPRT value
Full size table

The maximum of crisp values is OPRT (Overall Process Response Time), which is 166.25 for this scenario-I.

2.9 Scenario II

In this example trapezoidal fuzzy numbers are taken to test the proposed algorithm:

Consider a fuzzy DCS consists of set \(T = \left\{ {t1,t2,t3,t4,t5} \right\}\) of tasks \(m = 6\) and a set \(P = \left\{ {P_{1} ,P_{2} ,P_{3} , P_{4} } \right\}\) of processors \(n = 4\).The execution time of each task on processors and inter task communication time between communicating tasks has been taken in the form of matrix FET \(\left[ {\tilde{e}_{ij} } \right]\) and FITCT \(\left[ {\tilde{c}_{ik} } \right]\) of order \(m \times n\) and \(m \times m\) respectively, whose elements are trapezoidal fuzzy numbers as given in the Tables 10 and 11 [17].

Table 10 Fuzzy execution time matrix
Full size table
Table 11 Fuzzy inter task communication time matrix
Full size table

From Table 11, minimum linked tasks are calculated and converted into crisp values using RRM (Eq. 2) as listed in Table 12 and then arranged in ascending order as shown in Table 13.

Table 12 List of minimum linked tasks
Full size table
Table 13 List of minimum linked tasks in ascending order
Full size table

To assign minimum linked tasks to processors, Hungarian method is used and the tasks are allocated as shown in Table 14.

Table 14 List of initial assigned tasks on processors using Hungarian method
Full size table

Tasks are assigned by Hungarian Method by considering t1, t2, t4, t6 vs P1, P2, P3, P4.

$$T_{assgn} = \left\{ {t1,t2,t4,t6} \right\} \to (P1,P2,P3,P4)\;{\text{and}}\;T_{non - assgn} = \{ t3,t5\} .$$

To allocate task t3, it is fused with the already allocated tasks one by one and finally fused with the task having minimum PRT as shown in Table 15.

Table 15 Fusion of task t3 with already assigned tasks
Full size table

Minimum cost is (44,62,86,112). So task t3 is fused with t4 on processor P3.

$$\begin{aligned} T_{assgn} =\,\, & \left\{ {t1,t2,t3,t4,t6} \right\} \to (P1,P2,P3,P3,P4) \\ T_{non - assgn} =\,\, & \{ t5\} . \\ \end{aligned}$$

The above step is repeated for task t5 as shown in Table 16.

Table 16 Fusion of task t5 with already assigned tasks
Full size table

Minimum cost is (47,62,80,99). So task t5 is fused with t6 on processor P4. The final list of all assigned tasks is shown in Table 17.

Table 17 Final list of assigned task
Full size table

For overall PRT, the total cost for all distributed tasks is calculated as shown in Table 18.

Table 18 Final allocation task list with calculated OPRT value
Full size table

The maximum of crisp values is OPRT (Overall Process Response Time), which is 76 for this problem.

The crisp value of OPRT (Overall Process Response Time) for both the above mentioned problems (166.25 and 76) are less than the OPRT of the paper compared (250 and 119).

“A Task Allocation with Fuzzy Execution and Fuzzy Inter Task Communication Times in a Distributed Computing system”.

“International Journal of Computer Application (0977-8887) Volume 72–No.12, June 2013”.

3 Discussions

The task scheduling in distributed environment is much difficult from the traditional methods. In traditional methods there is only one processor and there is a need for allocation of multiple tasks on it, which is much easier and also various predefined algorithms are present to do this. In distributed environment it becomes difficult because there are more than one processor and large number of tasks are there for allocation. Several studies have been conducted for task scheduling in distributed environment so that total throughput can be reduced. In a study El-Abd [18] reported a fuzzy model for load balancing in distributed system. The author simulated the model and tried to solve the problem of uncertainty in task selection for dynamic load balancing. In a study Sriramdas et al. [19] proposed a model for reliability allocation technique using fuzzy model and an approximation method based on linear programming approach. The model is based on centralized distributed system (DS). In a study Barazandeh et al. [21] proposed an algorithm based on fuzzy logic which works for centralized distributed system. They have considered load, last completed task waiting time as input for fuzzy model and infer specific weights as output variable. They have used MATLAB software for simulation of the model. In a study Park and Kuhl [22] proposed a fuzzy based load balancing consistency model for uncertainty in decision making in a large DS. Also they have simulated the model. In a study Kang et al. [23] proposed an iterative greedy algorithm to maximize the system reliability by considering the wide range of parameters. The model has been simulated using MATLAB. In a study Bey et al. [24] proposed a model which is the combination of Adaptive Network based Fuzzy Inference System (ANFIS) and clustering scheme to estimate the value of CPU load. The proposed study introduces novel algorithm based on fuzzy logic. The proposed algorithm improves an overall process response time by allocating the task on processors. For this purpose Execution Time and Inter Task Communication Time have been taken into consideration. The algorithm uses fuzzy environment and therefore for defuzzification Robust Ranking Method is used, whenever there is a need of crisp values. The proposed algorithm is unique in a way that it uses Hungarian Method for initial allocation of tasks, tasks which are minimally linked, to different processors. From the data sets given in illustrated examples it can be seen that this algorithm improves the total response time in comparison to other methods.

4 Conclusion

In this paper a fuzzy task allocation problem has been formulated and shown in the form of mathematical model. Paper proposes a novel algorithm for allocating the tasks on different processors with the objective of minimum response time by taking Fuzzy Execution Time and Fuzzy Inter Task Communication Time into consideration. The algorithm uses RRM (for defuzzification) and Hungarian method (for initial allocation of tasks). Paper illustrated two scenarios for testing the proposed algorithm which gives PRT values 166.25 for scenario-1 and 76 for scenario-2. The model has potential to minimize the Overall Process Response Time by assigning an approximate balanced load to the processors as per literature studied. The limitation of paper is that it is restricted and focused on static load balancing policy. Although the model presented is efficient enough but leaves a number of situations where further work can be done. In future it can be explored for dynamic load balancing on processors.