Dynamic Tasks Scheduling Algorithm for Distributed Computing Systems under Fuzzy Environment

Dynamic Tasks Scheduling Algorithm for Distributed Computing Systems under Fuzzy Environment

Harendra Kumar (Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar, Uttarakhand, India), Nutan Kumari Chauhan (Department of Mathematics and Statistics, Gurukula Kangri University, Haridwar, Uttarakhand, India) and Pradeep Kumar Yadav (Department of Research Planning and Business Development, Central Building Research Institute, Roorkee, Uttarakhand, India)
Copyright: © 2016 |Pages: 19
DOI: 10.4018/IJFSA.2016100104
OnDemand PDF Download:
List Price: $37.50


Distributed computing systems [DCS] offer the potential for allocating a number of tasks to different processors for execution. It is desired to assign the tasks dynamically to that processor whose characteristics are most appropriate for the execution in order to make the best use of the computational power available. This paper proposes a new mathematical model for allocating the tasks of distributed program to multiple processors in order to achieve optimal cost and optimal reliability of the system. Phase-wise execution cost, residence cost of each task on different processors, inter task communication cost and relocation cost for each task have been considered as a fuzzy number which is more realistic and general in nature. The fuzzy problem has been transformed into crisp one by using the defuzzification method. The present algorithm is formulated and applied to numerical examples to demonstrate its effectiveness. The present model is suitable for arbitrary number of phases and processors with random program structure.
Article Preview

1. Introduction

The fuzzy set theory introduced by Zadeh in 1965 has been applied successfully in various fields and distributed computing system is one of them. DCS is used to describe a system whenever there are several computers interacted in some fashion so that a program runs on a system with multiple processors.DCS provides faster computation by facilitating parallel execution of tasks of a program. Program partitioning into the tasks and their allocations are two major steps in designing of DCS. If these steps are not done properly, an increase in the number of processor in the system may actually result in the decreases of the total throughput due to the saturation effect that arises from excessive inter-processor communication. The excessive inter-processor communication is always costliest and least reliable factor in DCS. Therefore, an efficient task allocation strategy is required for the proper utilization of computational resources and minimization of inter-processor communication that arises when the interacting tasks reside on different processors.

Task allocation policy can be static or dynamic, depending upon the time at which the allocation decisions are made. Dynamic algorithms are employed more frequently because they offer a better efficiency, having the flexibility of tasks migration. In addition, usually dynamic algorithms are neither very complicated to construct nor costly to run. Hence dynamic algorithms have the potential to outperform static algorithms in general. Stone (1977) has suggested an efficient optimal algorithm for the problem of assigning tasks to two processors by making the best use of the well-known network flow algorithm in the related two-terminal network graph. A shortest tree algorithm for optimal assignment of the tasks has been developed by Bokhari (1981). Towsley (1986) generalized the result of Bokhari to the case of series parallel structures. Bokhari (1979) analyzed the problem of dynamic assignment in a two processors system, which permits relocation of tasks from one processor to the other at some points during the execution of the program. Yadav et al. (2008) generalized the result of Bokhari (1979) for NP- hard system.

In a linear array network when any two non-adjacent processors communicate with each other, the inter-mediate processor must participate in the communication. Thus the communication cost per unit information transferred between any two processors increases linearly as the distance between them increases. Cho et al. (1994) generalized the result of C. H. Lee et al. (1992) for the general structure problem in a linear array network with any number of machines. In Sinclayer (1988), Rotithor (1994), Vidyarthi and Tripathi (2001), and Yadav, Singh, and Pradhan (2012), several approaches are used to find the tasks assignment for minimizing the total cost of running program. V. Sriramdas et al. (2014) developed a tasks allocation model treating allocation factors as fuzzy numbers. Recently Kumar (2015) has developed an effective tool for handling the fuzzy tasks allocation problem. The system reliability of a DCS can be measured by probability of the successful execution of its tasks. A model for allocating the tasks to processors in heterogeneous DCS with the goal of maximizing the system reliability has been developed in Kang, He, and Wei (2013).

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 7: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 6: 4 Issues (2017)
Volume 5: 4 Issues (2016)
Volume 4: 4 Issues (2015)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing