PREDICTIVE JOB SCHEDULING IN A CONNECTION LIMITED SYSTEM USING PARALLEL GENETIC ALGORITHM

PREDICTIVE JOB SCHEDULING IN A CONNECTION LIMITED SYSTEM USING PARALLEL GENETIC ALGORITHM

Abstract:

Job scheduling is the key feature of any computing environment and the efficiency of computing depends largely on the scheduling technique used. Intelligence is the key factor which is lacking in the job scheduling techniques of today. Genetic algorithms are powerful search techniques based on the mechanisms of natural selection and natural genetics. Multiple jobs are handled by the scheduler and the resource the job needs are in remote locations. Here we assume that the resource a job needs are in a location and not split over nodes and each node that has a resource runs a fixed number of jobs. The existing algorithms used are non predictive and employs greedy based algorithms or a variant of it. The efficiency of the job scheduling process would increase if previous experience and the genetic algorithms are used. In this study, a new technique is proposed as a model of the scheduling algorithm where the scheduler can learn from previous experiences and an effective job scheduling is achieved as time progresses.

CHAPTER ONE

INTRODUCTION

• Background of the study

Predictive job scheduling system is a model of the scheduling algorithm. The scheduler can learn from the previous experiences. Selection and crossover are considered in the entire population; each individual may compete and mate. A binary encoding is used to convert the scheduling problem to chromosomes. Each chromosome has genes. The efficiency may be high if the same jobs have to be scheduled. The scheduler starts with no prior information about the jobs at first. After each allocation the information is stored to the history base. The job of specific requirement comes again a different combination is tried according to the resource availability if the execution time is lower then it is recorded. This is called the learning phase. If a new job which has not yet scheduled by the scheduler, then the system is put to a brief learning phase again. The encoding process is done by assuming that a chromosome has the following gene structure. Chromosome {gene1, gene2, gene3}; Gene1 is the job identifier; Gene2 is the resource identifier and Gene3 is the node identifier.

The fitness function f is the execution time of that job at the node. The population generation is done by assigning binary set values for each of the genes. Job A may be encoded as 00 and job B may be encoded as 01 and so on. The same method can be used to represent all genes. The sample population may have individuals such as 00 01 10. After the population is built in the learning phase, the fitness of the individual is recorded as the execution time of the job at the node. The next time the same job is to be scheduled the history information is checked. a new gene combination is found and job  scheduled and the fitness recorded.  After time T the genetic operator of crossover is applied and the individuals of the same job type are selected for crossover.

The proposed algorithm procedure for the learning phase is by creating the population by encoding the problem.  Add chromosome to the history if it does not exist in the history, else, try a different combination of genes} If job details available in history.  Then, if the resource is available, then send the job to the node; else try a different resource if it is available. Initiate the learning procedure after time T apply the Genetic Operators on the history information. The Genetic Algorithm Scheduling increase execution time at first and then, improved as time progressed. The future work may involve the different and more efficient methods of encoding a problem and different genetic operators and methods.

The Genetic algorithm (GA) is a stochastic search algorithm based on the principle of natural selection and recombination [1] . It is a kind of evolutionary algorithm and has been successfully applied to solve many optimization problems, e.g., knapsack problems, shop scheduling problems or travelling salesman problems [2] [3] [4] . Nevertheless, when GAs are applied to more complex and larger problems, the required time to find adequate solutions is increased. Particularly, repeated fitness function evaluation is often the most prohibitive and limiting segment when GAs are hired to find an optimal solution for high-dimensional or multimodal implementations. Meanwhile, GAs also suffers from the problem of a tendency to converge towards local optima rather than the global optimum. Previous works in this area suggest enlarging population size, increasing mutation rate or hiring niche penalty in selection to keep the diversity of GAs. However, any of them may raise the complexity of the algorithm and lead to more time consumption.

No doubt, parallel implementation is considered as one of the most promising choices to make GAs work faster. There are different ways of exploiting parallelism in GAs [5] : master-slave models, fine-grained models, island models and hybrid models. The master-slave model is the only one that does not affect the behavior of the algorithm by distributing the evaluation of fitness function to slaves. The fine-grained model works with a large spatially population. The evolution operations are restricted to a small neighborhood with some interactions by overlap structure. The island model divides populations into subpopulations. Subpopulations on the islands are free to converge towards different sub-optima and a migration operator can help mix good features that emerge from the local island. The hybrid model combines any two of the above methods.

Powerful search technique based on mechanics of biological evolution is used to solve a difficult problem in many disciplines can provide efficient and effectives techniques for optimization and machine leaning applications. In GA, It is necessary to select a specific number of inputs.  For instance, x1, x2 … xn which belong to the input space X. Each input in the GA terminology called an organism or chromosome. The set of chromosomes is designated as a colony or population. Computation is done over epochs. In each epoch the colony will evolve according to specific rules reminiscent of biological evolution. G.A phases include: Initial Population; Evaluation of fitness function; Parent selection; Crossover operation and Mutation. G.A begins with a set of k randomly generated states. These states are satisfactory to the problem. The representation of solutions should be encoded as; Real numbers   (1,2,….9); Binary encoding    (0s,1s) and List of rules    (R1,R2,R3). Evaluation of fitness function, to each chromosome xi, we assign a fitness value that is the function of xi (f (xi); Fitness: string value; Properties: best string highest fitness function, if s1 is better than s2, then f (s1)> f (s2).   Stronger individual chromosomes with fitness values closer to the colony optimal will have greater chance to survive across epochs and to reproduce than weaker individuals which will tend to die. The important step in the algorithm is reproduction or breeding which happens once per epoch. The content of the two chromosomes participating in reproduction are literally merged together to form a new chromosome that a child. This heuristic allows us to possibly combine the best of both individuals to yield a better one. On mutation, perform exploitation on the current best strings (performs random local search). Let e an element of the string

e

10011010

The value of e, ᵾ e € string is changed with some probability p (usually low)

10001010

Genetic Algorithm application level scheduling algorithm generates the initial population, evaluates each individual’s fitness, and performs genetic operations on the Individuals with high fitness such copying, crossover and mutation, to generate a new population. The genetic process continues with the new population until a nearly optimal jobs assignment strategy is obtained. Finally, the jobs are assigned to each node based on the strategy. Total execution time is the time between the beginning of execution of the first job of a series and completion of the last job. Average turnaround time is the average, for each job from when the job arrives to when the job finished. Parallel implementation of GA provides considerable gains in terms of performance and scalability. It can easily implemented on network of heterogeneous computers or in parallel mainframes.

1.2              Statement of the Problem

The predictive job shop scheduling problem is one of the best known combinatorial optimization problems where jobs are assigned to machines at particular times. The use of evolutionary algorithms for shop scheduling problems started around 1980 [6] . There have been a huge number of publications dealing with GAs for shop scheduling problems. Due to the NP hardness, the time cost to obtain an adequate solution by the serial GA is always heavy. With the development of high performance computing (HPC) in last decades, the implementation of parallel GAs to shop scheduling problems has been extensively studied. The purpose of this paper is to give a tutorial survey of recent works on solving scheduling problems in manufacturing systems using parallel GAs. There are three ways to classify the scheduling problem in manufacturing systems by the machine environment, the job characteristics and the optimization criterion [7] . Most of the works concern on the three basic types: a flow-shop, a job-shop and an open-shop. In a flow-shop, each job passes through the machines with the same order whereas a job-shop enables specified jobs have possibly different machine orderings. In an open-shop, there is no particular route imposed on jobs. In addition to theses three types, flexible shops also catch a lot of attentions. It is a combination of a shop scheduling problem and a parallel machine scheduling problem, in which at least one stage consists of several parallel machines [6] . Most of the works considered are the flexible flow shop or the flexible job shop.

1.3     Objectives of the study

The general objective of this study is to design and implement predictive job scheduling in a connection limited system using parallel genetic algorithm. The scheduling system will analyze load situation of each node and choose one node to run the task.  The scheduling system has to realize the load balancing and increase the throughput and resource utilization under restricted condition, when the system is heavily loaded.

• Significance of the study

The significant of this study includes the following: If multiple tasks arrive during a unit scheduling time slot, then scheduling system will be responsible to allocate an appropriate number of jobs to each node in order to finish these jobs under a defined intent. The benefit is usually the minimal average execution time. This scheduling policy is application- oriented. So, this schedule is called application level scheduling.