An Efficient Approach to Genetic Algorithm for Task Scheduling in Cloud Computing Environment

Published Online September 2012 in MECS DOI: 10.5815/ijitcs.2012.10.09

A cloud is a type of parallel and distributed system a collection of interconnected and virtualized computer that are dynamically provisioned and presented as one or more unified computing resources based on service level agreements established through negotiation between the service providers and consumers. In this information technology oriented growing market of businesses and organizations, cloud computing is an emerging and attractive alternative to satisfy their day by day increasing needs. It provides virtual resources that are dynamically scalable. It describes virtualized resources, software, platforms, applications, computations and storage to be scalable and provided to users instantly on payment for only what they use [1].

Cloud ecosystem comprises of three main entities: Cloud consumers, cloud service providers, and cloud services. Cloud consumers consume cloud services provided by the cloud service provider. These services may be hosted on the service provider’s own infrastructure or on the third party cloud infrastructure providers [2].

1.1    Cloud Computing Service Models

It provides three service models which are - Cloud Infrastructure as a Service (IaaS), Cloud Platform as Service (PaaS) and Cloud Software as a Service (SaaS) . Cloud IaaS provides consumer the processing, storage, networks and other fundamental computing resources where the consumer is able to deploy and run arbitrary software, which can include operating system and applications. On the basis of consumers specified hardware (number of CPU cores, physical memory size etc) and software stack (operating system, middleware and application software) is immediately made available by clouds IaaS providers. Cloud PaaS service facilitates developers with providers. Cloud PaaS service facilitate developers with provider specific programming language and tools to develop the applications. Cloud SaaS provides the capability to users to use the provider’s application running on cloud infrastructures. The applications are accessible from various client devices through a thin client interface such as web browsers ^[3]. Sales force Relationships Management (CRM) ^[4] system and Google Apps ^[5] are two examples of SaaS. All organizations and business enterprises are taking the full benefits of Cloud computing to reduce the cost and to grow their business quickly. Hence efficient task scheduling is must to influence the decision of service provider for cost benefit of this computing paradigm.

Cloud Computing

Fig. 1: Service Models

1.2    Problem issues in Clouds

Cloud computing is recently a booming area and has been emerging as an commercial reality in the information technology domain. However the technology is still not fully developed. There are still some areas that are needed to be focused on.

• •    Resource management

• •    Task scheduling

Task scheduling and provision of resources are main problem areas in both Grid as well as in cloud computing. Cloud computing is emerging technology in IT domain. The scheduling of the cloud services to the consumers by service providers influences the cost benefit of these computing paradigms. However, there are so many algorithms are given by various researchers for task scheduling, which are discussed in related work.

The remainder of this paper is organized as follows: Section 2 gives related work regarding task scheduling problem in cloud computing technology. Section 3 describes the problem still existing with the in scheduling the tasks in cloud environment. Section 4 presents the implementation of problem. Section 5 presents results and discussions. Conclusion and future work are given in the final section.

II.    Related Work

III.    Problem formulation

Task scheduling and provision of resources are main problem areas in both Grid as well as in cloud computing. From the study of related work, we concluded that the existing scheduling strategies in clouds are based on the approaches developed in related areas such as distributed systems and Grids. Scheduling in these areas is mainly tailored toward ensuring single application Service Level Agreement (SLA) objectives. In cloud environment on the other hand require guarantying numerous SLA objectives and quality of service. There are many algorithms like Min-Min, Max-Min, Suffrage, Shortest Cloudlet to Fastest Processor (SCFP), Longest Cloudlet to Fastest Processor (LCFP) and some meta-heuristics like Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant-Colony Optimization (ACO) and Simulated Annealing (SA) already existing for task scheduling. However, there are so many algorithms are given by various researchers for clouds, But, none of the above existing algorithms have considered the

• •    computational complexity(job length, processing power)

• •    computing cost(processor cost)

4.1    Existing Algorithm

Our proposed work focuses on optimizing the task scheduling algorithms with meta-heuristic algorithms that is Genetic Algorithm (GA) in a private cloud environment. With the combination of SCFP, LCFP and a meta-heuristic GA as an optimization method, we propose to developed a new approach Modified Genetic Algorithm (MGA) for task scheduling. MGA is developed by modifying the initial population with LCFP, SCFP and by controlling the stochastic operators of standard genetic algorithm which lead to achieve a very good results and better efficiency of the algorithm than the standard genetic algorithm. This is for single user jobs in which the fitness will be developed to encourage the formation of solutions to achieve time minimization.

IV.    Algorithm Descritption

Our main purpose is to schedule tasks to the adaptable resources in accordance with adaptable time, which involves finding out a proper sequence in which all the tasks can be executed such that execution time and execution cost can be minimized. Cost is also an important parameter as the cloud computing services by service providers to service consumers are provided on internet on pay as per usage basis.

For time minimization, the Genetic Algorithm is a flexible approach enabling, for the same problem, different individual representations and algorithm implementations to select individuals and perform crossover and mutation. A Genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover. However, the appropriate representation of potential solutions is crucial to ensure that the mutation of any pair of individual (i.e. chromosome) will result in new valid and meaningful individual for the problem. An output schedule of tasks is an array list of population (called chromosomes or the genotype of the genome), which encode candidate solutions to an optimization problem, evolves toward better solutions. Time minimization will give profit to service provider and less maintenance cost to the resources. It will also provide benefit to cloud’s service users as their application will be executed at reduced cost.

Standard Genetic Algorithm (SGA)

• •    Produce an initial population by randomly generated individuals

• •    Evaluate the fitness of all individuals

• •    while termination condition not met do

o   select fitter individuals for reproduction o  crossover between individuals o mutate individuals o evaluate the fitness of the modified individuals o Generate a new population

• •    End while

  

  Fig. 2: Flow Chart- Standard Genetic Algorithm (SGA)

  
  

• 1.    For each processor Pi , construct the sequence Si of task assigned to it.

• 2.    Concatenate sequences   Si .  The resulting

• 4.2.2 Initial Population:

sequence is a permutation of tasks assigned to processors.   This representation   requires maintaining additional information on the number of tasks assigned to each processor.

We have merged LCFP, SCFP and 8 Random Solutions to generate the initial population of metaheuristic which encode candidate solutions to an optimization problem, evolves toward better solutions.

chromosome

X11 X12 XU ХУ XV gene

4.2 Proposed Algorithm

Modified Genetic Algorithm (MGA)

• •    Generate an initial population of individuals with output schedules of algorithms Longest Cloudlet to Fastest Processor  (LCFP),

Smallest Cloudlet to Fastest Processor (SCFP) and 8 Random Schedules.

• •    Evaluate the fitness of all individuals

• •    while termination condition not met do

o Select fitter individuals for reproduction with minimum execution time.

o Crossover between individuals by two-point crossover.

o Mutate individuals by simple swap operator.

o Evaluate the fitness of the modified individuals having relevant fitness.

o Generate a new population

• •    End while

• 4.2.1    Schedule Encodings

Here, Cloudlets refer to user jobs in Cloud Computing.

For schedule encoding we used Permutation-based representation. In this representation each processor must be present only once. This kind of representation is especially useful in sequence based problems, thus it is also interesting for scheduling problems. For the task scheduling problem this representation is obtained in two steps:

Fig. 3: Chromosome Representation

• •    Job – an array list to store job length.

• •    Processor- an array list to store processor speed.

• •    Best Solution- an array list to hold best

solution so far.

• •    Cost & Time are two characteristics of a

genome.

• a)    LCFP (Longest Cloudlet to Fastest Processor)

• 1.    Sort the cloudlets in descending order of length.

• 2.    Sort the processors in descending order of processing power.

• 3.    Map the cloudlets from sorted list to the sorted list of processors on one-to-one mapping basis.

• b)    SCFP (Smallest Cloudlet to Fastest Processor)

• 1.    Sort the cloudlets in ascending order of length.

• 2.    Sort the processors in descending order of processing power.

• 3.    Map the jobs from sorted list to the sorted list of processors on one-to-one mapping basis.

• 4.2.3    Crossover

• 4.2.4    Mutation

• 4.2.5    Evaluation

• 4.2.6    Termination Condition

The crossover operators are the most important ingredient of any evolutionary-like algorithm. Indeed, by selecting individuals from the parental generation and interchanging their genes, new individuals (descendants) are obtained. The aim is to obtain descendants of better quality that will feed the next generation and enable the search to explore new regions of solution space not explored yet. There are so many crossover operators which can be used to get the better results. In our case we have chosen the two-point crossover.

Evaluation is based on the execution time and execution cost. Those schedules will be selected for next generation whose makespan( execution time of all cloudlets) and execution cost is less than the standard genetic algorithm (SGA)

Genetic Algorithm gets terminated after user specified number of generations. We generated 30 evolutions of genetic algorithm to get the better results from SGA.

The two algorithms are implemented on Intel core i5 machine with 500 GB HDD and 4 GB RAM on Windows 7 OS, Eclipse with Java version 1.6, with the help of JGAP (Java based Genetic Algorithm Package)

• 1.   Standard Genetic Algorithm (SGA)

• 2.   Modified Genetic Algorithm (MGA)

A good scheduling algorithm is that which leads to better resource utilization, less average Make-span and better system throughput. Make-span refers to the completion time of all cloudlets in the list. To formulate the problem we considered cloudlets ( C1, C2,C3…..C n ) run on processors (P1, P2, P3…..P n ). . Our objective is to minimize Make-span. The speed of processors is expressed in MIPS (Million instructions per second) and length of job can be expressed as number of instructions to be executed. Each processor is assigned varying processing power and respective cost in Indian rupees. We have computed the make-span (completion time of cloudlets) and the corresponding cost of output schedules of above two algorithms and compared them.

All the algorithms are tested by:

• •    Varying the number of cloudlets.

• •    Randomly varying the length of cloudlets.

Experimental results show that under heavy loads our proposed algorithm that is modified Genetic Algorithm exhibits a very good performance.

Table 1: GA Parameters

Parameter	Value
Number of Cloudlets	10-30
Number of Processors	5
Number of Iterations	30
Population Size	10
Crossover Type	Two-Point Crossover
Crossover Probability	0.5
Mutation Type	Simple Swap
Mutation Probability	0.6
Termination Condition	Number of Iterations

Table 2: List of Processors

Processor Capacity(Mips)	Per Unit Cost
100	15
200	20
300	25
400	30
500	40

The figure 4 shows the Makespan refers to execution time calculated in seconds of all cloudlets in each of two algorithms. Experimental resulting values show that our proposed algorithm takes less execution time as compared to existing SGA which is based on the random generation of schedules. By modifying the

SGA with stochastic operators we got the better results and better resource utilization as cloudlet load is shared equally on all processors

Average Makespan vs. Number of Cloudlets

SGA и MGA

Number of Cloudlets

Fig. 4: Shows Average Makespan vs. Number of Cloudlets

Execution cost vs Number of Cloudlets

Fig. 5: Shows Average Execution Cost vs. Number of Cloudlets

Above figure compared the execution cost of two algorithms. Resulting values show that performance of proposed algorithm is better than the existing algorithm and keep on increasing with increase in workloads.

VI.    Conclusion and Future Work

Clouds enable the users to use utility services. Users are required to pay for access to the services based on their usage and level of quality of service required. In this research we have proposed a modified genetic algorithm for single user jobs in which the fitness is developed to encourage the formation of solutions to achieve the time minimization and compared it with existing heuristics. Experimental results show that, under the heavy loads, the proposed algorithm exhibits a good performance.

In future, we will be further enhancing our algorithm by supporting runtime scheduling and also considering the user’s quality of service and priority of jobs for multiple users.