Fuzzy Based Evaluation of Optimal Service Time Using Execution/Communication Time and Clustering

INTRODUCTION

Various applications of assignment problem (AP) exist in the real world. Extensive examples can be seen in various areas of the assignment problem such as industry, commerce, technology, management science, etc. Real-life problems cannot be successfully solved by the classical optimal assignment problem. Fuzzy assignment problem (FAP) is more appropriate in today’s context. The theory of fuzzy sets was given in 1965 by Lofty A. Jadeh. This theory represents impurity or uncertainty in daily life. With the increase in computer processing, the need for competencies in technology has increased even more rapidly. Expected handling effectiveness for special applications cannot be attained with a monotonous processing framework. These problems can be solved by distributed processing systems (DPS). The division and allocation of work are important in building DPS. If these steps are not executed properly, the structure of DPS increases the number of promoters that can reduce the overall flow of the structure. With advances in distributed systems, the assignment problem has turned into an important consideration. There is a need to improve efficiency for computing scheduling in broadcasting work. The most important topic when structuring any task algorithm is to minimize the extra time as much as possible.

An optimal solution is obtained by calculating a fuzzy mean service rate using the task allocation technique (Khandelwal, 2019) with the idea of fuzzy communication time. The author (Yadav et al„ 2019) has allocated the processors efficiently on different nodes by balancing the load between them. In this process, care has also been taken to reduce execution and response time. An optimal solution to the TFA problem has been achieved using the centroid ranking technique (Mary and Selvi, 2018). In addition, it uses the Euclidean separation strategy to analyze the fuzzy value and its rank. Many researchers have solved the fuzzy assignment problem through a genetic algorithm approach. Through the genetic algorithm approach, each individual with cost (time) has been organized for only one task (Muruganandam and Hema, 2018) and is presented as an invariant number. In addition to the genetic algorithm approach here, crisp values have been derived by the Yager ranking method to obtain an optimal solution to the fuzzy assignment problem.

In various research papers, the defuzzification concept (Sharma, 2018. Kumar et al„ 2013, Gani and Mohamed, 2013 and Yadav et ah, 2011) is envisaged by the robust ranking method, wherein the fuzzy value is changed to one, i.e., crisp number one. In defuzzification, a mathematical model is formed to determine the correct response time of the system using triangular/trapezoidal fuzzy execution time and triangu- lar/trapezoidal fuzzy intertask communication time. Fuzzy assignment problem is important in solving the real-life problem. In the real-life problem (Thakre et ah, 2018, Selvi et ah, 2017), the fuzzy assignment problem has been resolved through the example of four candidates/designations at Life Insurance Corporation (LIC). In this the solution of this problem is represented by the fuzzy triangular magnitude ranking method, Hungarian method, MOA and direct method. A diffusion strategy (Neelakantan and Sreekanth, 2016) has been proposed to accommodate tasks between different computers in the context of a problem. In this, the response time of assignment to a processor is limited from moving the overload computer to the low-load computer to using the load adjustment system from the computer. To assess the performance of the system, the load on the system is calculated by fluctuating the average differential arrival time of the tasks on each computer.

PROBLEM STATEMENT

Fuzzy Assignment Problem (FAP) is more appropriate for today’s real-life problems. Here, we have a fuzzy assignment problem (FAP). The purpose of this fuzzy assignment problem is to allocate a set of processors F: [pj} on a set of tasks F: {f,} in such a way that the total impedance time is minimized. For the solution of the fuzzy assignment problem here we convert the fuzzy impedance time coefficients by using the fuzzy ranking method and then formed clusters of tasks by using K-means clustering technique.

Here, execution time, communication time, total response (impedance) time, defuzzification, and fuzzy mean service rate (Khandelwal, 2019) have been solved by using the following formulae.

• Fuzzy Execution Time:

• Fuzzy Communication Time:

• Fuzzy Total Response Time:

• Defuzzification:

• Clustering Technique: Clustering technique aims to partition m tasks into n cluster (m > n) in which each task belongs to the cluster with the adjacent mean. This technique produces exactly n different clusters of greatest possible discrepancy.

• Fuzzy Mean Service Rate:

COMPUTATIONAL ALGORITHM

The mapping between the tasks and processors is defined by (p: N —» M. A task may be a data file or code which is to be executed on different processors having different processing capabilities. Assume that number of tasks is more than the number of processors (m > n) as normally seen in real life. Also it is assumed that the execution time of a task on each processor and intertask communication time is known. The intertask communication time between the same tasks is zero.

Step 1: Set Fuzzy quantitative problem of m tasks F- {f, j for l

Step 2: Set Fuzzy quantitative problem of n processors F: {p,} for 1< j < n, le.,{p,,p2,p3}

Step 3: Set F: {/f7(cTv )}and F, {CT(ctik)} in the form of fuzzy triangular number. F- {£T(et,y)}and F- {C7(c?rt)}are taken in the form of matrices as Fuzzy Execution Time Matrix and Fuzzy Intertask Communication Time Matrix.

Step 4: Determine Defuzzified Crisp Value for F; {ETfc^)}by using Eq. (11.4).

Step 5: Determine sum of each task processor-wise and stored in Fuzzy Sum Array FZ{ETS,U„_«„*{}}.

Step 6: Cluster the task into n processor.

Step 7: Select n points randomly as cluster centre and calculate the squared error function using Eq. (11.5).

Step 8: Assign task to their closest cluster centre.

Step 9: Calculate mean of all tasks in each cluster.

Step 10: Repeat steps 7. 8 and 9 until the same points are assigned to each cluster in consecutive rounds.

Step 11: Apply basic assignment method on these clusters so formed in step 10 and allocate these tasks clusters on different processors.

Step 12: Let tasks allocated to processors is denoted by F- CTET(ety)} = Ta,,„cah.. Calculate Total Fuzzy Execution Time F- {ET}, Total Fuzzy Communication Time F-{CT} and Total Fuzzy Task Response Time F-{TRT}using Eqs.

(11.1), (11.2), and (11.3).

Step 13: Convert Total Task Response Time into crisp values once using step-4 because it is fuzzy quantitative number.

Step 14: Now' calculate the Overall Task Response Time for all tasks allocated in all different processors and Fuzzy Mean Service Rate for each Processor F:{MSR(,)}

Step 15: Stop.

PSEUDOCODE FOR METHOD

Begin

  • • Set Fz {tijwhere 1 < i < m and Fz denotes fuzzy allocation for task {ti}
  • • Set Fz {pj} where 1 < j < n
  • • Set Fuzzy Triangular Number Fz {ET(eti;()} and Fz {CT(ctlk)}
  • • Represent Fz {ET(eti;l)} and Fz {CT(ctiic)} in rectangular matrix form (m > n)
  • • for i: =1 to m inclusive do

for j:=1 to n inclusive do

1 .

Calculate, R(Cj,) = — (a + 3aa)f(k)dk

2 Jo

Fz {ET(et1;)} <- Mag(,Cij) end for end for

• Step5: sum = 0, a =

for i:=1 to m inclusive do for j:=1 to n inclusive do

if (((i % 2==0)| |(i % 2==l)) && (j<=n)) then sum = et[i] [j]+sum end if end for suma = sum

sum = 0

a = a + 1

end for

• for i: =1 to m inclusive do

for j:=1 to n inclusive do T(i, j) = (tj % Cj) end for end for

for i:=1 to m inclusive do T(i)T(i)array)min

Cl] = compare [diff(Tkk+lk+rm.ni where k + r=j, 1 < j < n;

r = 0,1, 2,...

then again

( (C* ^ T(i)k + lminm2n.......I |(Cfc+r ^ IX-iJmin

end for

  • • Calculate mean of all tasks {ti}in each cluster {Clj}
  • • Repeat steps 5, 6 and 7 until the same points are assigned to same cluster {Clj} in consecutive rounds.
  • • Apply Hungarian method on these clusters so formed in step 8 and allocate

{Pj} <- (tj(Clj) }.

  • • Set Fz )| = ^2locate * {ti(Clj) }
  • • Calculate Total Fuzzy Execution Time, fz {et(c)} =

Total Fuzzy Communication Time, lsism

Fz {cr (c)} = {ctiit} , к = 1, 2, 3, . . . , Ш ; 1 < j < n

i=j*k

Calculate overall FTRT for all tasks,

Fz {trt(c)} = max (Fz {et(c)} + Fz {CT(c)})

  • 1
  • • Convert, fz {trt(c)} <- i J(a + 3a0 - a)f(k)dk
  • 0

^TtA

  • • Calculate, fz {MSR(j)} = --———-
  • 1 J ' Fz{ET(etj) }

End

MATHEMATICAL IMPLEMENTATION

Steps 1-3: Set Fuzzy numerical problem for m tasks for 1

i.e., {fj,T2}and n processors F;{/ty} for 1< j i.e., {/?i,/?2,/b}in matrix form. Also set fuzzy execution time (Table 11.1) (F;{£T(e%)}/ fuzzy communication time (Table 11.2) F: {CF(cf,*)} in the form of FTN in matrix form.

TABLE 11.1

Fuzzy Execution Time Matrix

(5,10.20)

(10,15.20)

(10,20,30)

(5.10,20)

(5,10,15)

(5,10.15)

(10,20,30)

(10,15.25)

(10,15.20)

(5,10,20)

(10,15,20)

(10,15,25)

(10.15,20)

(5,10,15)

(5,15.20)

TABLE 11.2 Fuzzy Communication Time Matrix

(0,0,0)

17.5

10

31.25

6.25

17.5

(0,0,0)

32.5

10

25

10

32.5

(0,0,0)

10

10

31.25

10

10

(0,0,0)

12.5

6.25

25

10

12.5

(0,0,0)

Step 4: Using Ranking Method find Crisp Value for F- {/:T((?/,;)}obtained in Table 11.3.

TABLE 11.3

Defuzzified Crisp Values

6.25

8.75

10

6.25

5

5

10

10

8.75

6.25

8.75

10

8.75

5

5

Step 5: Determine sum of each task (processorwise) and stored in Fuzzy Sum Array F- {ETSum Row| shown in Table 11.4.

TABLE 11.4

Fuzzy Task_Sum Array

Task

Crisp Value

20

28.75

28.75

20

16.25

Step 6: Cluster the task into three processors.

Steps 7-10: Select three points {18,22,26} randomly as cluster centre and calculate the squared error function (by Eq. [11.5]). Tables 11.5-11.7 representing the stepwise clustering iterations.

TABLE 11.5

Centred Mean Value in Three Different Iterations

18/18.125/16.25

22 / 20,.з

26 / 28.752

18/18.125/16.25

22 / 20,.з

26 / 28.752

18/18.125/16.25

22 / 202,з

26 / 28.752

18/18.125/16.25

22 / 202,з

26/28.752

18/18.125/16.25

22 / 202.з

26/28.752

TABLE 11.6

Deviation During Clustering in Three Different Iterations

2/1.875/3.75

2 / 02

6/8.752

10.75/10.625/12.25

6.75/8.752.3

2.75 / 02

10.75/10.625/12.25

6.75/8.752.3

2.75 / 02

2/1.875/3.75

2 / 02

6/8.752.3

1.75/1.875/0

5.75/3.752

9.75 / 12.52

TABLE 11.7

Nearest Cluster with New Centroid Value in Different Iterations

Nearest Cluster

NewCentroid

x/2/2

20/20*/20*

3/3/3

28.75“ / 28.75“ / 28.75“

3/3/3

3/3/3

18.125 /* /*/

1/1/1

18.125“ /* /16.25

In 2nd and 3rd iteration same points are assigned to each cluster. Hence tasks clustered on three processors as |/: ®/4},{/2 Ф/,}{/5} in three consecutive rounds.

Step 11: Apply basic Assignment procedure to allocate clustered tasks on the different processors. It is shown in Table 11.8.

TABLE 11.8

Assignment Method on Cluster

12.5

18.75

5

13.75

20

6.25

13.75

18.75

5

Steps 12-14: Evaluate F- {£T}, F: {C71} and Fz {ТЯГ} using Eqs. (11.1), (11.2), and (11.3). Also Evaluate Fuzzy F- {MS/?(,)}fcr each Processor. These values are show n in Table 11.9.

Step 15: Stop

TABLE 11.9

Fuzzy Total Response Time and Mean Service Rate

Processor

Tasks

12.5

(70,120.175)

(80,140,215)

78.5

0.0254

6.25

(60,95,130)

(65,105,145)

58.75

0.0170

18.75

(90,145,205)

(110,180.255)

101.25

0.0197

CONCLUSION AND DISCUSSION

In this research problem, we have established a fuzzy system using fuzzy execution time and fuzzy intertask communication time through which the optimal value of the mechanism can be obtained. Here, tasks are moved from overload processors to underload processors using a mixture of functions to reduce the average service rate of tasks. To estimate the optimal value of the system according to the process, different tasks have been allocated according to the average service rate of the tasks on each processor. Compared to existing approaches, the proposed technique has yielded the optimal value minimum. The proposed approach reduces the average service rate of the system for an effective mix of tasks and optimal allocation, which is an important part of this technique. According to the approach proposed here the optimum value is 101.25 w'hich is lower than the 66.83 and 65.16 values as compared to the existing approaches.

The methodology proposed in this chapter qualifies for the allocation of the processor’s functions and provides optimal values, but we cannot say that this currently existing technique provides perfection to this mechanism. We can use various other methods of solving various technology in this field. Here, we have only focused on reducing the average service rate of the model, but this may also apply to load balancing problems w'ith different models of phased technology in the future.

REFERENCES

Gani A. N. and V. N. Mohamed. 2013. Solution of a Fuzzy Assignment Problem by Using a New Ranking Method, International Journal of Fuzzv Mathematical Archive, 2. 8-16, ISSN: 2320 -3242 (P). 2320 -3250 (online).

Khandelwal A. 2019. Fuzzy Based Amalgamated Technique for Optimal Service Time in Distributed Computing System, International Journal of Recent Technology and Engineering, 8(3), 6763-6768, ISSN: 2277-3878.

Kumar H., M. P. Singh and Pradeep Kumar Yadav. 2013. A Tasks Allocation Model with Fuzzy Execution and Fuzzy Inter-Tasks Communication Times in a Distributed Computing System, International Journal of Computer Applications, 72(12), 24-31, ISSN: 0975-8887.

Mary R. Q. and D. Selvi. 2018. Solving Fuzzy Assignment Problem Using Centroid Ranking Method. International Journal of Mathematics and its Applications, 6(3), 9-16, ISSN: 2347-1557.

Muruganandam S. and K. Hema. 2018. A Method of Solution to Fuzzy Assignment Problem Using Genetic Algorithm, Global Journal for Research Analysis, 7(4), 154-157, https:// www.doi.org/10.36106/gjra, ISSN: 2277-8160.

Neelakantan P. and S. Sreekanth. 2016. Task Allocation in Distributed Systems, Indian Journal of Science and Technology, 9(31), DOI: 10.17485/ijst/2016/v9i31/89615.

Selvi D„ R. Queen Mary and G. Velammal. 2017. Method For Solving Fuzzy Assignment Problem Using Magnitude Ranking Technique. International Journal of Applied and Advanced Scientific Research, Special Issue. 16-20, ISSN: 2456-3080.

Sharma A. 2018. Time Optimization Model with Defuzzification for the Task Allocation in Distributed Computing System, International Journal of Electronics Engineering, 10(2), 492-501, ISSN: 0973-7383.

Thakre T. A.. Onkar К Chaudhari and Nita R Dhawade. 2018. Placement of Staff in LIC Using Fuzzy Assignment Problem. International Journal of Mathematics Trends and Technology (IJMTT), 53(4). 259-266, ISSN: 2231-5373.

Yadav P. К.. P. Pradhan and Preet Pal Singh. 2011. A Fuzzy Clustering Method to Minimize the Inter Task Communication Effect for Optimal Utilization of Processor’s Capacity in Distributed Real Time Systems, Proceedings of the International Conference on SocProS. K. Deep et al. (Eds.), springerlink.com. AISC 130, 159-168.

Yadav S„ Rakesh Mohan and P. K. Yadav 2019. Fuzzy Based Task Allocation Technique in Distributed Computing System, International Journal of Information Technology, 11(1), 13-20, https://doi.org/10.1007/s41870-018-0172-6.

 
Source
< Prev   CONTENTS   Source   Next >