An Improved Task Scheduling Mechanism Using Multi-Criteria Decision Making in Cloud Computing

An Improved Task Scheduling Mechanism Using Multi-Criteria Decision Making in Cloud Computing

Suvendu Chandan Nayak (Veer Surendra Sai University of Technology, Sambalpur, India) and Chitaranjan Tripathy (Veer Surendra Sai University of Technology, Sambalpur, India)
DOI: 10.4018/IJITWE.2019040106


In this work, the authors propose Multi-criteria Decision-making to schedule deadline based tasks in cloud computing. The existing backfilling task scheduling algorithm could not handle similar tasks for scheduling. In backfilling algorithm, tasks are backfilled to provide ideal resources to schedule other deadline sensitive tasks. However, the task to be backfilled is selected on first come, first serve (FCFS) basis from scheduling queue. The scheduling performances require to be improved when, there are similar tasks. In this proposed work, the authors propose to implement MCDM technique, TOPSIS (Technique for Order Preference by Similarity to Ideal Solution) to improve the performance of the backfilling algorithm through scheduling deadline sensitive tasks in cloud computing. It resolves the conflicts among the similar tasks that is used as a decision support system. The work is simulated with synthetic data sets based on slack values of the tasks. The performance results affirm the task completion and reduction in task rejection compared to the existing backfilling algorithm.
Article Preview

1. Introduction

Multi-criteria Decision-making is the technique of evaluating the best course of action from pool of the available alternatives (Chen, Kilgour and Hipel, 2008). The computation is carried out by analyzing multiple criteria. MCDM is a growning up branch of operation research which supports to evaluate a number of alternative decisions based on performance criteria (Yue, 2011). Suppose there is k-dimension decision variable consists of K decision variables with m constraints and n objectives can be evaluated mathematically as:

Since 1960s, MCDM techniques have been used to derive different theoretical as well as practical applications in various areas. It has been designed to rank alternatives, classify alternatives, and preferred alternative in a subjective preference order (Chen, Kilgour and Hipel, 2008; Behzadian, Khanmohammadi Otaghsara et al., 2012) . Among rapid development of MCDM methods to solve real-world decisions, TOPSIS shows much attention in diverse application areas (Shidpour, Shahrokhi and Bernard, 2013). Originally, TOPSIS was introduced by Hwang and Yoon in 1981. The idea behind TOPSIS is to rank a preference order with respect to the relative closeness that is evaluated by both positive-ideal-solution (PIS) and negative-ideal-solution (NIS) with a combination of these two distance measures (Olson, 2004; Kao, 2010; Wang and Luo, 2010; Hosseinzadeh Lotfi et al., 2013; Zadeh Sarraf, Mohaghar and Bazargani, 2013). TOPSIS resolves the MCDM decision problems in many application areas (Behzadian, Khanmohammadi Otaghsara, et al., 2012; Bulgurcu, 2012; Aghajani Mir et al., 2016). Still, there is less attention to use MCDM in cloud computing by the researchers.

With rapid change of computing technology and computing a new era of computing is adopted, called cloud computing, in which IaaS (Infrastructure as a Service) model provides on-demand resources to the user on “pay per use” concept (Magalhães et al., 2015). The on-demand resources are in form of CPU, memory, bandwidth of one or more machines into multiple execution units called virtual machine (VM) (Addya et al., 2017; Nayak, Parida and Tripathy, 2018). The cloud service providers intent to achieve better resource utilization. Better resource utilization could be achieved by adoption of new allocation mechanisms or policies. These mechanisms implement different resource models, heuristic mechanisms, optimization techniques and MCDM techniques. Moreover, different mechanisms have been proposed by researchers due to nature of tasks and cloud services (Rodriguez and Buyya, 2014). The nature of task is varied due to requirement of users and cloud service platforms for user applications. Deadline based task is one of them, in which the on-demand resources need to be allocated within a deadline to complete the execution. So, it is more challenging to schedule these tasks within their deadline without rejecting tasks. In this work, we tried to improve the performance of backfilling algorithm that is used to schedule deadline based tasks in cloud computing.

Backfilling algorithm is an optimized First Come First Serve (FCFS) algorithm (Feitelson, 2005; Parida, Nayak and Tripathy, 2015; Nayak and Tripathy, 2016). In backfilling the tasks are sorted according to their start time for scheduling. Some of the tasks need to be backfilled from the scheduling queue to get ideal resources for the new task. The selection of the tasks is purely on FCFS basis. The scheduling performance of backfilling algorithm needs to improve with respect to the number of task scheduled due to conflicts among the similar tasks (Nayak and Tripathy, 2016). The task selection must be carried out through a decision maker due to the presence of different parameters of deadline sensitive tasks such as start time, number of VMs, execution time (duration) and deadline. Therefore, in this work, we consider the conflict among the similar kinds of tasks as a MCMD problem.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 15: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 14: 4 Issues (2019)
Volume 13: 4 Issues (2018)
Volume 12: 4 Issues (2017)
Volume 11: 4 Issues (2016)
Volume 10: 4 Issues (2015)
Volume 9: 4 Issues (2014)
Volume 8: 4 Issues (2013)
Volume 7: 4 Issues (2012)
Volume 6: 4 Issues (2011)
Volume 5: 4 Issues (2010)
Volume 4: 4 Issues (2009)
Volume 3: 4 Issues (2008)
Volume 2: 4 Issues (2007)
Volume 1: 4 Issues (2006)
View Complete Journal Contents Listing