Heuristic Algorithms for Task Scheduling in Cloud Computing: A Survey

Published Online August 2017 in MECS DOI: 10.5815/ijcnis.2017.08.03

Type Cloud has brought a fundamental difference with traditional Information Technology. By sharing resources cloud is capable of serving user requests cost-effectively and affordably. To achieve maximum benefit for provider and increasing the quality of service (QoS), it should ideally be scheduled. Cloud computing has changed the network and architecture of computer systems. Companies can lower costs, save energy, and automatically upgrade their systems by replacing traditional computer systems and equipment with cloud computing services [1] .

Schedule tasks to determine how to allocate users to virtual machines and critical role in the effectiveness and efficiency of the system's which aims to complete the task in minimum time with maximum utility or standard. Intelligent scheduling algorithms designed to overcome the problems and limitations of the delivery of services on the network are necessary. Cloud computing has many benefits, which are listed below. Google, Amazon and Microsoft are sample of public cloud providers who recommend their services to the general public. Data created and submitted by consumers are usually stored on the servers of the third party provider[2].

• A. The advantages of cloud computing

• -    Lower cost: applications are provided in cloud. As result, there is no need to exorbitant cost for buying equipped computer systems, because only by using web browsers, users can access resources whenever and wherever they are. Cloud reduce small and medium companies’ cost considerably.

• -    Immediate access: cloud can provide fast access to hardware resources and reduce cost for large companies. Its infrastructures are available simultaneously for cloud users who are separated from each other. Users do not depend on their systems and if they use another computer they can continue using the same resources [3] .

• -    More security: if the data are stored in your own computer system they may be lost in case the storage device be damaged. Although. In cloud computing, this is not the case and the deterioration of computer system does not affect your information.

• -    Non-stop services: cloud must be always available such that users can access their resources and information at any time.

Although, several failures of connection has happened in cloud by now. For instance, connection failure of twitter for 24 hours in 2010, Gmail and google app store for 2.5 hours in 2009 and Microsoft Azure for 22 hours in 2008. This is a disadvantage which must be fixed [4] .

• II.  Cloud Computing

Cloud computing is a product of technology development and social needs. Cloud introduces a fundamental difference with traditional information technology [5] . Cloud is able to service users as quickly as possible in a cost-efficient way. In fact, it is some kind of repository of computers, databases and servers, which is accessible through the Internet in order to decrease the users’ need for hardware equipment and personal storage devices [6] . These resources are available on one or more data centers. Users can access these resources on-demand and by sending the request to the server. Hardware and access detail are hidden from the customer and just servers are aware of them, such that at first users send their request to servers by cloud applications, then servers buffer requests and send their request for schedule and respond it with the appropriate virtual machines (VM) that could run user request and run that VM on best physical machine (PM) with best available resources.

Users and companies can access this resources wherever in the world on-demand. These resources can be provided distributed, parallel or dynamically for users and these are presented based on user service level agreement (SLA).

• A. Cloud Resource Layers

Based on resource distribution type, cloud computing is composed of three layers- infrastructure as a service(IaaS), platform as a service(PaaS) and software as a service(SaaS)- and in this way services are presented for users [7] .

• -    IaaS: This layer is in the lower level and supports the needed infrastructure for servers like processors, storage and hardware Equipment. So users do not need to buy server, data center and network resources anymore. In addition, costs are paid based on the duration of using them. On the whole, it is possible to say resource management is done in this level; such as Amazon EC2 [8] .

• -    PaaS: This is the middle layer of needed software and supporting them. This layer is a hosting for various environments offering services which are provided Package; such as Microsoft Azure, Google application engine.

• -    SaaS: This is related to online software, such as an online office or Google Doc, which resolves various problems of traditional software like updating and deployment. In addition, it is useful for reducing costs. For instance, Sale force CRM is a software on cloud.

Scheduling can be built in different layers of the service heap. As you can see in Fig.1, in different layers cloud has its own strategy. Accordingly, the architecture composed of the SaaS, PaaS, IaaS heaps can be used to categorize scheduling problems into software layer, platform layer and infrastructure layer. Scheduling in SaaS is to scheduled VMs to task, job, user applications, etc.,

Scheduling in PaaS is scheduled VMs to physical resources and Scheduling in IaaS is ordered to deliver the infrastructure, that is , IaaS, to users, providers need to make clusters of servers of cloud centers located across the whole world to serve worldwide users [9] . This paper has focused on scheduling algorithms in SaaS layer to observe the QoS for users, Problems do not only come from the time and cost Limitations of the user, but also come from the provider in that the resources need to be used with balance or a maximum utility. So, this class is divided into three sub-directory names user QoS, performance provider and combine of both. in this part of scheduling, utilization of user`s QoS is the point which is discussed by the use of heuristic algorithms.

Fig.1. Scheduling in Different Layers

• III.    Task Scheduling

The scheduling is defined into two levels of host and virtual machine (VM). In virtual machine level, the tasks are allocated to virtual machines, and in host level, the virtual machines to the hosts.

The optimization of tasks performance is one the most important subjects in cloud environments. One of the Problems is when a great number of users ask cloud resources at the same time; these difficulties could be solved by correct task scheduling to the available VMs. The aim of scheduling is usually loading distribution on VMs based on parameters like cost, response time, reliability, speed, utility, scheduling successful rate, deadline time, etc. Generally, in scheduling algorithms, there is a list of tasks attributed to all tasks made on the base of their priorities. The tasks are chosen based on their priorities and are allocated to the VMs[10].

• A.    Data in Task Scheduling

The tasks in cloud computing are two kinds of workload and workflow. In workload, the data are not dependent on one another. The tasks are usually taken from real data and are performed independently. The data is composed of an ID, Task Length, input file, output file, and finally, the number of required processes of each of tasks but the tasks in the workflow are performed continues and dependently. Consider them as a graph in which first the parents and then the children must be performed, since they are considered as a collection of different tasks for achieving a particular result.

• B.    Dependent parameters in scheduling

To evaluate each algorithm or scheduling, different parameters and variables could be taken into account, such as:

• -    Waiting time: the sum of elapsed time of a task in waiting line.

• -    Response time: the time of response is calculated from the time of task entering to system until the time of its exiting.

• -    Make span: it is the subtraction time of finish time of the last VM from the start time of the first VM.

• -    Cost: the cost that each client pays for the time use of VM.

• -    Throughput: the number of task done in the unit of the time [11] .

• -    Utility: the duration of task execution in each of VM in proportion to time of total execution.

• -    Time execution: the duration when the users use VMs.

• -    Deadline: the time limit for performing the task and if this limit is not observed the Provider have to pay fine.

• -    CPU idle time: the duration when the CPU is idle and has no task to do.

All of these methods and parameters are taken in algorithms to have a schedule in which the most utility be met in VMs.

• C.    Different kinds of scheduling regarding tasks Behavior

There are two kinds of scheduling called static and dynamic. In static scheduling, there is the required data about all resources in scheduling moment, therefore the Time execution could be estimated and scheduling is done once. In contrast, in dynamic scheduling, the main idea is allocation of tasks in Time execution, there is no information about task performance duration or other and it is performed at the Time execution and different duration of time efficiency the scheduling is repeated in Time execution for several times. For example, every 5 seconds the scheduling is repeated when the new tasks enter[12].

• IV.    Task Scheduling Algorithms

Since the task scheduling is of NP-hard kind, the heuristic techniques, powerful and flexible method for problem solving, were applied to solve the problems. They examine the whole environment and return the best response. Their aim is to find the best and the most acceptable responses according to the problem requirements.

• A. Heuristic Algorithms

The heuristic algorithms are dependent on the problem and they try to find the solutions by applying problem features in a complete way. Their solution is based on learning and exploration in which a comprehensive and scientific search for finding an optimal response and speeding to response process is applied. However, they are very greedy and they are usually trapped in local optimal, moreover, they may defeat in getting widespread optimal solution.

The existing solutions for task scheduling through heuristic are shown in Table 1. This table presents method, scheduling parameters, description, evaluation tool, experiment size of simulation in order to existing solution, finally explain their results that they found. The heuristic algorithms used in this paper include [13, 14] :

• -    Heterogeneous-Earliest-Finish-Time      algorithm

(HEFT) presented two novel heuristic for task scheduling, first heuristic for directed acyclic graph (DAG) scheduling, and another for scheduling independent tasks. In order to reduce Makespan, both heuristics have suitable performance behavior.

• -    Multiple QoS Constrained Scheduling Strategy of Multi-Workflows (MQMW) proposed three items include: Preprocessor, Scheduler and Executor. Preprocessor computes the time and cost of the Workflow and after that it sends the ready tasks the Scheduler queue, Then sort all task according their strategy. Finally The Executor selects best service to sequential execute tasks. Finally, Executor notifies to Preprocessor in order to completion status.

• -    Resource-Aware-Scheduling algorithm (RASA) composed of the advantages of Max-Min and MinMin and solves their disadvantage.

• -    A compromised-Time-Cost (CTC) considers the specifications of cloud to adjustment instance intensive cost-constrained workflows via reaching an agreement execution time and cost with customer input on the fly.

• -    Optimal Workflow Scheduling (OWS) focuses on scheduling cloud workflows. First, the discovery algorithm, lists all the resources and allocation workflow to free resources by considering QoS parameters (execution time, reliability, monetary cost etc.).

• -    Scalable-Heterogeneous-Earliest-Finish-      Time

algorithm (SHEFT) presented classify all resources into some clusters after that a weighted directed acyclic graph is modeled to demonstrate a workflow in a cloud.

• -    Integer linear program (ILP) has two level of Service Level Agreements (SLA) that consider user

and provider. First notation and problem modeling, second formulation of the integer linear program.

• -    SaaS Cloud-Partial Critical Paths (SC-PCP) recursively schedules the partial critical paths ending at previously scheduled workflow.

• -    Concurrent Level based Workflow Scheduling (CLWS) consider all the tasks according to the agreement between tasks during the real workflow execution.

• -    Enhanced IC-PCP with Replication (EIPR) uses idle time and cost of workflow In order to reduce the impact of performance variation of Cloud resources by consider the deadlines of workflows.

  Table 1. Examining Heuristic Algorithms

  Algor ithm	Ref	Scheduling Parameters	Description	Evalu ation Tool	Compared with	Experiment size	Finding
  HEFT	[15] 2004	Makespan	The algorithm calculates the first run time And is ranked in descending order, A task that has the highest value is selected to run first.	Gridsi m	FCP, CPOP, MinMin, LMT, Hyb.BMCT, DLS	Random graphs: 25100   tasks,   FFT graphs:      15-223 tasks,      Fork-join graphs: 7-229 tasks, Laplace graphs: 25225 tasks, 3-8 machines, 100 runs	Lower Makespan
  MQM W	[16] 2009	Scheduling success rate, cost, time, make span	This strategy can be any time started several workflows that considers quality of service, is scheduled, They are four factors at the beginning and end of tasks, and costs have a significant impact on the workflow used to have.	Cloud sim	RANK_HYBD	5 set of Workflows, 20 machine, 5-25 users	Improve the success rate of 22.7%
  RAS A	[17] 2009	Make span	This algorithm with min-min and max-min thorough analysis, as well as the advantages and disadvantages of the two algorithms are proposed. By using algorithm min-min runs the small tasks And max-min to avoid delays in the big tasks.	GridS im	Max-min, Minmin, opportunistic load balancing (OLB)	200-5000 task, 10 11 grid resources	lower Makespan
  CTC	[18] 2010	Cost, execution time	In this paper, used CTC algorithms in reducing the time and cost of the customer That reduces the cost of 15 percent and 20 percent of time is run.	Swin DeW-C	Deadline-MDP	creates 1,000 instances per second and a total number 1,000,000 instances, 4 machine	Reduce cost by 15% and time by 20%
  OWS	[19] 2011	CPU utilization, Execution time	The algorithm consists of two main phases, the first phase of the algorithm to discover the Resources of all Resources identified and labeled, and each of the node's parent node. These phase II data with quality of service (QoS) take resources.	Open nebul a	Backfilling, FCFS	NA	The scheduling algorithm finds a solution that meets all user preferred QoS constraints AND improvement in CPU utilization
  SHEF T	[20] 2011	Scalability, Execution time	In this paper, By using scheduling algorithm and parameters SHEFT, nearest end time, remaining time and the closest starting to do a task scheduled performs.	Cloud Sim	HEFT	generator randomly generates 50, 000 workflow graphs and use 2-300 task	Optimizing execution time and enables resources to scale elastically during workflow execution
  ILP	[21] 2012	Makespan, Cost, Time	ILP for workflow scheduling clients SaaS and multiple provider IaaS where Service Level Agreement for both exist.	self-simul ator with Java	Begin-minimum time (BMT), begin-minimum endmaximum times (BMEMT).	3 IaaS providers, 4VM for IaaS(A), 7VM for IaaS(B), 2VM for IaaS(C)-20 RUN, Fork-Join AND Montage DAG	low-cost solutions with shorter deadlines

  
  

  SC-PCP	[23] 2012	Cost, Deadline	A new workflow scheduling algorithm based on the QoS on the novel concepts of the Partial Critical Paths (PCP) is called. This algorithm is the first tasks assigned to track and act recursively.	self-simul ator with Java	Deadline-MDP	different sizes for each workflow(30-1000   task)   from CyberShake, Epigenomics, LIGO, Montage, SIPHT [22]	the computation time of the algorithm is very low for the Decrease Cost and the Fair policies, but is much longer for the Optimized policy
  CLW S	[24] 2014	Cost with user designated	In This algorithm that determined the levels of their duties and the Markov Decision Process (MDP) algorithm for scheduling tasks is dependent that this algorithm not only on reducing the total cost of execution as well as time.	Self-simul ator	Bottom Level denoted (DBL), MinCost,	100 task	Decrease the time and optimize the total executing cost
  EIPR	[25] 2014	Deadline, total cost	This paper is for task scheduling to reduce cost by Considering deadline focused and ultimately the improvement was 59 percent of the algorithm IC-PCP.	Cloud sim	IC-PCP	500   host,   Four workflow(50-1000 TASK):  Montage, Cyber-Shake, LIGO, SIPHT- 50 RUN, VM  types  used: Memory[1.7-30], Core speed[1-3.25], Cores[1-8]	Reduce execution time by 59%

  
  

• V.    Scheduling Algorithm Evaluation

To evaluate and compare algorithms, they can be simulated with some tools or performed in real environment. For simulations, there are different tools as described below

• A.    Cloudsim

To evaluate and compare algorithms they can be simulated with the tools or be performed in real environment. For simulations there are different tools including Cloudsim. Cloudsim is a general and developable simulation framework which makes an integrated modeling, simulation, trying out application services, appearing cloud computing infrastructures possible. Cloudsim supports system simulation in big scale and network connections within the elements of simulated network, compositional cloud computing, and structuring and configuration of cloud environment, etc. Cloudsim starts with a network of nodes. A main node consists of data center, a host, and a broker. The data center (source provider) is created first with defining features like operating system, memory, bandwidth, saving and so one. After that, one or some hosts on data center with RAM special features, saving, bandwidth, process elements, and choosing scheduling algorithm for scheduling virtual machine in host are made. Process elements are known as the core or CPU that in them each process element is given measured process power in MIPS (Million Instructions per Second). The hosts are directed by data center so that every data center may direct one or some hosts. The cloud broker (an entity which creates and maintains relation among several service providers) is also created to distribute the jobs among available data centers or cloud services[26, 27]. The cloud broker is a firmware between the users and cloud service provider. After creating all nodes of the network, Cloudsim create virtual machines on defined hosts for performance. Features of every virtual machine are determined by parameters like process power in million instructions per second, RAM in MB, bandwidth and so on. Although the implementation in real environment is better and exacter and other tools like Workflowsim, Matlab, Java and so are available too, the researchers can test and evaluate their proposed model before implementation in a variable environment. For implementation cloud system providers' sites like Amazon can be used as well.

• B.    Gridsim

Computational resources of network are distributed across geographical locations increasingly and heterogeneously; thereby, we need simulation tools to estimate and evaluate their performance. The grid system is a tool for estimation and simulation of network’s computational models in a distributed environment by the use of Java programming language, which is based on the SIMJAVA itself [28] . This tool allows the user to simulate grid resource attributes and various configurations. From the hardware point of view, it has a layered structure and modular packaging. As a powerful and advanced tool, the grid system is appropriate for modeling a variety of resources, supporting network systems and heterogeneous systems in distributed environments, supporting the shared-time and colocation models, supporting the static and dynamic scheduled and supporting resource-allocation scheduling algorithms [29, 30] . In addition, it is capable of reading data that are obtained from actual environments, and it has flexibility in computational network model with a variety of subjects. The grid system is prospered for grid environments, although for cloud environments as a part of the distributed networks, the Cloudsim tool has been introduced.

• VI.  Conclusions

In recent years, applying cloud computing has been developed all over the world and it has been matured and has been an opportunity for companies to save the cost and compute. Based on more source usage and demands, one of the most important tasks of cloud is more utility which needs appropriate source management. The tasks are directed by scheduling. The present study reviewed on task scheduling algorithms. Moreover, the present study classified and compared required parameters for scheduling, applied functions in these algorithms, and the tools and their details of each. There have been great improvements and developments in task scheduling, source utility, and expense reductions but they still need further developments for the future:

• 1.    Complementing and improving simulations tools

• 2.    Introducing new multi-dimensions, parameters with considering users’ interests, services, energy reduction, network traffic reduction and all involved.

• 3.    Presenting more efficient algorithms on crossing multi-objectives scheduling.

• 4.    More focus on dynamic scheduling for their similarity to the real world.

The review of the study is stated in Fig 2.

SwinDeW-C

Gridsim

Cloudsim simulator Matlab

Open nebulae Workflowsim

Task Scheduling Optimization Is One Of The Main Challenges Of Cloud Computing

Server Utilization earliest finish time waiting makespan finishing time deadline

Reliability

Power

Consumption

Length of VM task

^gueucs

Scheduling Success

Fig.2. Mind Map for Task Scheduling in Cloud Computing Environment

Scalability computation cost transmission cost

Performance

^CPU idle time