WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba On Performance Analysis of Hybrid Algorithm (Improved PSO with Simulated Annealing) with GA, PSO for Multiprocessor Job Scheduling K.THANUSHKODI Director Akshaya College of Engineering Anna University of Technology, Coimbatore INDIA [email protected] K.DEEBA Associate Professor, Department of Computer Science and Engineering Kalignar Karunanidhi Institute of Technology Anna University of Technology, Coimbatore INDIA [email protected] Abstract: - Particle Swarm Optimization is currently employed in several optimization and search problems due its ease and ability to find solutions successfully. A variant of PSO, called as Improved PSO has been developed in this paper and is hybridized with the simulated annealing approach to achieve better solutions. The hybrid technique has been employed, inorder to improve the performance of improved PSO. This paper shows the application of hybrid improved PSO in Scheduling multiprocessor tasks. A comparative performance study is reported. It is observed that the proposed hybrid approach gives better solution in solving multiprocessor job scheduling. Key-Words: - PSO, Improved PSO, Simulated Annealing, Hybrid Improved PSO, Job Scheduling, Finishing time, waiting time 1 Introduction be Non-deterministic Polynomial (NP) complete except in few cases [1]. Scheduling, in general, is concerned with allocation of limited resources to certain tasks to optimize few performance criterion, like the Several research works has been carried out in completion time, waiting time or cost of the past decades, in the heuristic algorithms for production. Job scheduling problem is a popular job scheduling and generally, since scheduling problem in scheduling area of this kind. The problems are NP- hard i.e., the time required to importance of scheduling has increased in recent complete the problem to optimality increases years due to the extravagant development of exponentially with increasing problem size, the new process and technologies. Scheduling, in requirement of developing algorithms to find multiprocessor architecture, can be defined as solution to these problem is of highly important assigning the tasks of precedence constrained and necessary. Some heuristic methods like task graph onto a set of processors and branch and bound and prime and search [2], determine the sequence of execution of the tasks have been proposed earlier to solve this kind of at each processor. A major factor in the efficient problem. Also, the major set of heuristics for job utilization of multiprocessor systems is the scheduling onto multiprocessor architectures is proper assignment and scheduling of based on list scheduling [3]-[9], [16]. However computational tasks among the processors. This the time complexity increases exponentially for multiprocessor scheduling problem is known to these conventional methods and becomes ISSN: 1109-2750 287 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba excessive for large problems. Then, the job scheduling policy uses the information approximation schemes are often utilized to find associated with requests to decide which request a optimal solution. It has been reported in [3], should be serviced next. All requests waiting to [6] that the critical path list scheduling heuristic be serviced are kept in a list of pending requests. is within 5 % of the optimal solution 90% of the Whenever scheduling is to be performed, the time when the communication cost is ignored, scheduler examines the pending requests and while in the worst case any list scheduling is selects one for servicing. This request is within 50% of the optimal solution. The critical handled over to server. A request leaves the path list scheduling no longer provides 50% server when it completes or when it is performance guarantee in the presence of non- preempted by the scheduler, in which case it is negligible intertask communication delays [3]- put back into the list of pending requests. In [6], [16]. The greedy algorithm is also used for either situation, scheduler performs scheduling solving problem of this kind. In this paper a new to select the next request to be serviced. The hybrid algorithm based on Improved PSO scheduler records the information concerning (ImPSO) and Simulated Annealing is developed each job in its data structure and maintains it all to solve job scheduling in multiprocessor through the life of the request in the system. architecture with the objective of minimizing the The schematic of job scheduling in a job finishing time and waiting time. multiprocessor architecture is shown in Fig.1 Pre- empted job s In the forth coming sections, the proposed algorithms and the scheduling problems are Arriving Scheduled jobs Completed requests/ discussed, followed by the study revealing the jobs improvement of improved PSO. Server jobs Scheduler Pending In the next section, the process of job requests/ jobs scheduling in multiprocessor architecture is discussed. Section 3 will introduce the Fig 1. A Schematic of Job scheduling application of the existing optimization algorithms and proposed improved optimization algorithm for the scheduling problem. Section 4 discusses the concept of simulated annealing, 2.1 Problem Definition section 5 and 6 on both the proposed algorithms The job scheduling problem of a multiprocessor followed by discussion and conclusion. architecture is a scheduling problem to partition the jobs between different processors by attaining minimum finishing time and minimum waiting time simultaneously. If N different processors and M different jobs are considered, the search space is given by equation (1), 2 Job Scheduling in Multiprocessor Architecture ( ) M ×N ! Job scheduling, considered in this paper, is an Size of search space = (1) (N!)M optimization problem in operating system in which the ideal jobs are assigned to resources at particular times which minimizes the total Earlier, Longest Processing Time (LPT), and length of the schedule. Also, multiprocessing is Shortest Processing Time (SPT) and traditional the use of two or more central processing units optimization algorithms was used for solving within a single computer system. This also these type of scheduling problems [10],[18]- refers to the ability of the system to support [21],[27],[29]. When all the jobs are in ready more than one processor and/ or the ability to queue and their respective time slice is allocate tasks between them. In multiprocessor determined, LPT selects the longest job and SPT scheduling, each request is a job or process. A selects the shortest job, thereby having shortest ISSN: 1109-2750 288 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba waiting time. Thus SPT is a typical algorithm problem defined, the fitness function is which minimizes the waiting time. Basically, given by, the total finishing time is defined as the total time taken for the processor to completed its job V−TotalFinishingTime f <V and the waiting time is defined as the average of  F= −βWaitingTime time that each job waits in ready queue. The  objective function defined for this problem 0 f ≥V  using waiting time and finishing time is given by equation (2), (3) m n Minimize ∑ω f (x) (2) n n Where ‘V ‘ should be set to select an n=1 appropriate positive number for ensuring the fitness of all good individuals to be positive in the solution space. 3 Optimization Techniques Several heuristic traditional algorithms were Step3: Perform selection process to select the used for solving the job scheduling in a best individual based on the fitness multiprocessor architecture, which includes evaluated to participate in the next Genetic algorithm (GA), Particle Swarm generation and eliminate the inferior. Optimization (PSO) algorithm. In this paper a The job with the minimal finishing time new hybrid proposed improved PSO with and waiting time is the best individual simulated annealing is suggested for the job corresponding to a particular generation. scheduling NP-hard problem. The following sections discuss on the application of these Step4: For JSP problem, of this type, two – techniques to the considered problem. point crossover is applied to produce a new offspring. Two crossover points are generated uniformly in the mated parents at random, and then the two 3.1 Genetic Algorithm for Scheduling parents exchange the centre portion Genetic algorithms are a kind of random search between these crossover points to create algorithms coming under evolutionary strategies two new children. Newly produced which uses the natural selection and gene children after crossover are passed to mechanism in nature for reference. The key the mutation process. concept of genetic algorithm is based on natural genetic rules and it uses random search space. Step 5: In this step, mutation operation is GA was formulated by J Holland with a key performed to further create new advantage of adopting population search and offsprings, which is necessary for exchanging the information of individuals in adding diversity to the solution set. population [10], [11], [13], [15]-[22]. Here mutation is done, using flipping operation. Generally, mutation is The algorithm used to solve scheduling problem adopted to avoid loss of information is as follows: about the individuals during the process of evolution. In JSP problem, mutation is performed by setting a random Step 1: Initialize the population to start the selected job to a random processor. genetic algorithm Process.For initializing population, it is necessary Step6: Test for the stopping condition. Stopping to input number of processors, condition may be obtaining the best number of jobs and population size. fitness value with minimum finishing time and minimum waiting time for the Step2: Evaluate the fitness function with the given objective function of a JSP generated populations. For the problem or number of generations. ISSN: 1109-2750 289 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba If stopping condition satisfied then goto processors and number of jobs as shown in step 7 else Goto step2 Table. 1 were assigned to each of the processors. Step 7: Declare the best individual in the complete generations. Stop. The flowchart depicting the approach of genetic Table. 1: GA for job scheduling algorithm for JSP is as shown in Fig.2. Processors 2 3 3 4 5 Start No. of 20 20 40 30 45 jobs Initialize the population Input number of processors, Waiting 31.38 47.01 44.31 32.91 38.03 number of jobs and population size time Finishing 61.80 57.23 70.21 74.26 72.65 time Evaluate the fitness function F = V-Total finishing time- β waiting time Perform selection to select best individuals From the Table.1, it can be observed that for from the current population equal no of jobs for different processors, the finishing time has got reduced. The Perform two point crossover finishing time and waiting time is observed based on the number of jobs allocated to each processors. Figure 3 shows the Perform two point crossover variation in finishing time and waiting time for the assigned number of jobs and Termination processors condition No Yes Stop Fig.2 Flowchart for genetic algorithm to JSP Genetic Algorithm was invoked with the number of populations to be 100 and 900 Fig. 3 Chart for job scheduling in multiprocessor with different generations. The crossover rate was 0.1 and the number of processors and different number of jobs using GA mutation rate was 0.01. Randomly the 3.2 Particle Swarm Optimization for populations were generated and for various trials of the number of processors and jobs, the Scheduling completed fitness values of waiting time and The particle swarm optimization (PSO) finishing time as shown in Table.1. The technique appeared as a promising algorithm for experimental set up considered possessed 2-5 handling the optimization problems. PSO is a ISSN: 1109-2750 290 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba population-based stochastic optimization (4) technique, inspired by social behavior of bird flocking or fish schooling [10]-[15], [17]. PSO Using equation (4), a certain velocity that is inspired by the ability of flocks of birds, gradually gets close to pbests and gbest can be calculated. The current position (searching point schools of fish, and herds of animals to adapt to in the solution space) can be modified by the their environment, find rich sources of food, and following equation: avoid predators by implementing an information sharing approach. PSO technique was invented S == S +V (5) in the mid 1990s while attempting to simulate i+1 i i the choreographed, graceful motion of swarms of birds as part of a socio cognitive study Where, Vi : velocity of particle i, Si: current position of the particle, w : inertia weight, investigating the notion of collective intelligence C : cognition acceleration coefficient, C : in biological populations [10]-[15], [17]. 1 2 social acceleration coefficient, Pbest own best i : position of particle i, gbest global best position among the group The basic idea of the PSO is the i : of particles, r r : uniformly distributed mathematical modelling and simulation of the 1, 2 random numbers in the range [0 to 1]. food searching activities of a swarm of birds (particles).In the multi dimensional space where s : current position, s : modified the optimal solution is sought, each particle in i i + 1 position, v : current velocity, v : modified the swarm is moved towards the optimal point i i +1 velocity, v : velocity based on pbest, v : by adding a velocity with its position. The pbest gbest velocity based on gbest . velocity of a particle is influenced by three components, namely, inertial momentum, cognitive, and social. The inertial component simulates the inertial behaviour of the bird to fly in the previous direction. The cognitive component models the memory of the bird about its previous best position, and the social component models the memory of the bird about the best position among the particles. PSO procedures based on the above concept can be described as follows. Namely, Fig. 4 Flow diagram of PSO bird flocking optimizes a certain objective function. Each agent knows its best value so far (pbest) and its XY position. Moreover, each agent knows the best value in the group (gbest) Fig.4 shows the searching point modification of among pbests. Each agent tries to modify its the particles in PSO. The position of each agent position using the current velocity and the is represented by XY-axis position and the distance from the pbest and gbest. Based on the velocity (displacement vector) is expressed by above discussion, the mathematical model for vx (the velocity of X-axis) and vy (the velocity PSO is as follows, of Y-axis). Particle are change their searching point from S to S by adding their updated i i +1 velocity V with current position S. Each i i particle tries to modify its current position and Velocity update equation is given by velocity according to the distance between its current position S and V pbest, and the distance i V = w×V +C ×r ×(P −S )+C ×r ×(g −S ) between its current position S and V gbest . i i 1 1 besti i 2 2 besti i i ISSN: 1109-2750 291 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba The General particle swarm optimization was minimal. first the high temperature accelerates applied to the same set of processors with the the movement of the particles. During the assigned number of jobs, as done in case of cooling time they can find an optimal place genetic algorithm. The number of particles-100, within the crystal structure. While the number of generations=250, the values of temperature is lowered the particles c1=c2=1.5 and ω=0.5. Table.2 shows the subsequently lose the energy they were supplied completed finishing time and waiting time for with in the first stage of the process. Because of the respective number of processors and jobs a thermodynamic, temperature-dependent utilizing PSO. random component some of them can reach a higher energy level regarding the level they Table. 2 : PSO for job scheduling were on before. These local energy fluctuations allow particles to leave local minima and reach a state of lower energy. Processors 2 3 3 4 5 No. of jobs 20 20 40 30 45 Simulated annealing is a relatively straight Waiting 30.10 45.92 42.09 30.65 34.91 forward algorithm through which includes time metropolis Monte Carlo method .the metropolis Monte Carlo algorithm is well suited for Finishing 60.52 56.49 70.01 72.18 70.09 simulated annealing, since only energetically time feasible states will be sampled at any given temperature. The simulated annealing algorithm is therefore a metropolis Monte Carlo simulation that starts at a high temperature. The temperature is slowly reduced so that the search space becomes smaller for the metropolis simulation, and when the temperature is low enough the system will hopefully have settled into the most favorable state. Simulated Annealing can also be used to search for the optimum solution of the problems by properly determining the initial (high) and final (low) effective temperatures which are used in place of kT (where k is a Boltzmann's constant) in the Fig. 5 Chart for job scheduling in multiprocessor with different acceptance checking, and deciding what number of processors and different number of jobs using PSO constitutes a Monte Carlo step [30]-[35]. The initial and final effective temperatures for a given problem can be determined from the It is noted from Table.2 that for the same acceptance probability. In general, if the initial number of processors and jobs , the waiting time Monte Carlo simulation allows an energy (E) and finishing time using PSO has constructively increase of dEi with a probability of Pi, the reduced with less number of generations in initial effective temperature is kTi = -dEi/ln(Pi). comparison with GA. . Fig.5 shows the variation If at the final temperature an increase in the cost in finishing time and waiting time for the of 10 should only be accepted with a probability assigned number of jobs and processors using of 0.05 (5%), the final effective temperature is particle swarm optimization. kTf = -10/ln(0.05) = 3.338. 4. Simulated Annealing 4.1 Algorithm Start with the system in a known configuration, Annealing is an operation in metal processing at known energy E [30]-[35]. Metal is heated up very strongly and T=temperature =hot; frozen=false; then cooled slowly to get a very pure crystal While (! frozen) { structure with a minimum of energy so that the repeat { number of fractures and irregularities becomes ISSN: 1109-2750 292 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba Perturb system slightly (e.g., moves a equation (6) particle) Compute E, change in energy due to perturbation If(∆E < 0 ) Then accept this perturbation, this V = w × V + C × r × (P best – S) × P best i i 1g 1 i i i is the new system config + Else accept maybe, with probability = exp(- C × r × (S –P ) × P 1b 2 i worst i worst i ∆E/KT) + C × r × (Gbest – S) 2 3 i i } until (the system is in thermal (6) equilibrium at this T) If(∆E still decreasing over the last few Where, temperatures) C :acceleration coefficient, which 1g Then T=0.9T //cool the temperature; do accelerate the particle towards its more perturbations best position; Else frozen=true C :acceleration coefficient, which 1b accelerate the particle away from its } worst position; P :worst position of the particle i; return (final configuration as low-energy worst i solution) r r , r : uniformly distributed random 1, 2 3 numbers in the range [0 to 1]; 5. Proposed Improved Particle The positions are updated using equation (5). Swarm Optimization for The inclusion of the worst experience Scheduling component in the behaviour of the particle gives In this new proposed Improved PSO (ImPSO) the additional exploration capacity to the swarm. having better optimization result compare to By using the bad experience component; the general PSO by splitting the cognitive particle can bypass its previous worst position component of the general PSO into two different and try to occupy the better position. Fig.6 component. The first component can be called shows the concept of ImPSO searching points. good experience component. This means the bird has a memory about its previously visited best position. This is similar to the general PSO method. The second component is given the name by bad experience component. The bad experience component helps the particle to remember its previously visited worst position. To calculate the new velocity, the bad experience of the particle also taken into consideration. On including the characteristics of Pbest and Pworst in the velocity updation process along with the difference between the present best particle and current particle respectively, the convergence towards the solution is found to be faster and an optimal solution is reached in comparison with Fig. 6 Concept of Improved Particle Swarm Optimization search conventional PSO approaches. This infers that point including the good experience and bad experience component in the velocity updation also reduces the time taken for convergence. The algorithmic steps for the Improved PSO is The new velocity update equation is given by, as follows: ISSN: 1109-2750 293 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba Step1: Select the number of particles, generations, tuning accelerating coefficients C1g , C1b , and C2 and start random numbers r r , r to start the 1, 2 3 optimal solution searching Initialize the population Input number of processors, number of jobs and population size Step2: Initialize the particle position and Compute the objective function velocity. Invoke ImPSO Step3: Select particles individual best value for each generation. If E < best ‘E’ Step 4: Select the particles global best value, i.e. (P best) so far particle near to the target among all the particles is obtained by comparing all For each generation Search is terminated the individual best values. optimal solution reached For each particle Step 5: Select the particles individual worst value, i.e. particle too away from the Current value = new p best target. Choose the minimum ISE of all particles as the g best Step 6: Update particle individual best (p best), Calculate particle velocity global best (g best), particle worst (P worst) in the velocity equation (6) and obtain the new velocity. Calculate particle position Update memory of each particle Step 7: Update new velocity value in the equation (5) and obtain the position of the particle. End Step 8: Find the optimal solution with minimum ISE by the updated new velocity and End position. The flowchart for the proposed model Return by using ImPSO formulation scheme is shown in Fig.7. stop Fig. 7 Flowchart for job scheduling using Improved PSO The proposed improved particle swarm optimization approach was applied to this multiprocessor scheduling problem. As in this case, the good experience component and the bad experience component are included in the process of velocity updation and the finishing time and waiting time computed are shown in Table. 3. ISSN: 1109-2750 294 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba Table. 3: Proposed Improved PSO for Job scheduling The steps involved in the proposed hybrid algorithm is as follows Processors 2 3 3 4 5 Step1: Initialize temperature T to a particular No. of jobs 20 20 40 30 45 value. Waiting time 29.12 45.00 41.03 29.74 33.65 Step2: Initialize the number of particles N and its value may be generated randomly. Finishing 57.34 54.01 69.04 70.97 69.04 Initialize swarm with random positions time and velocities. Step3: Compute the finishing time for each and every particle using the objective The same number of particles and generations as function and also find the “ pbest “ i.e., in case of general PSO is assigned for Improved PSO also. It is observed in case of proposed If current fitness of particle is better than improved PSO, the finishing time and waiting time has been reduced in comparison with GA “ pbest” the set “ pbest” to current value. and PSO. This is been achieved by the introduction of bad experience and good If “pbest” is better than “gbest then set experience component in the velocity updation “gbest” to current particle fitness value. process. Fig.8 shows the variation in finishing time and waiting time for the assigned number Step4: Select particles individual “pworst” of jobs and processors using improved particle value i.e., particle moving away from swarm optimization. the solution point. Step5: Update velocity and position of particle as per equation ( ). Step6: If best particle is not changed over a period of time, a) find a new particle using temperature. Step7: Accept the new particle as best with probability as exp-(∆E/T). In this case, ∆E is the difference between current best particles fitness and fitness of the new particle. Step8: Reduce the temperature T. Fig.8 Chart for job scheduling in multiprocessor with different number of processors and different number of jobs using ImPSO Step 9: Terminate the process if maximum number of iterations reached or optimal value is obtained . else go to step 3. 6. Proposed Hybrid Algorithm for job scheduling The proposed improved PSO algorithm is independent of the problem and the results The flow chart for the hybrid algorithm obtained using the improved PSO can be is shown in Fig.9 further improved with the simulated annealing. The probability of getting trapped in a local minimum can be simulated annealing. ISSN: 1109-2750 295 Issue 9, Volume 10, September 2011 WSEAS TRANSACTIONS on COMPUTERS K. Thanushkodi, K. Deeba start The proposed hybrid algorithm is applied to the Initialize temperature T multiprocessor scheduling algorithm. In this Initialize the population Input number of algorithm 100 particles are considered as the processors, number of jobs and population size initial population and temperature T as 5000. The values of C1 and C2 is 1.5. The finishing Compute the objective function time and waiting time completed for the random instances of jobs are as shown in Table. 3 Invoke Hybrid algorithm Table 3: Proposed Hybrid algorithm for Job scheduling Search is terminated If E < best optimal solution ‘E’ (P best) reached Processors 2 3 3 4 5 For each generation No. of jobs 20 20 40 30 45 For each particle Waiting time 25.61 40.91 38.45 26.51 30.12 Current value = new p best Finishing 54.23 50.62 65.40 66.29 66.43 Choose the minimum ISE of all particles as the g best time Calculate particle velocity The same number of generations as in the case of improved PSO is assigned for the proposed Calculate particle position hybrid algorithm. It is observed, that in the case of proposed hybrid algorithm, there is a drastic reduction in the finishing time and waiting time Update memory of each particle of the considered processors and respective jobs assigned to the processors in comparison with the general PSO and improved PSO. Thus If best particle is combining the effects of the simulated annealing not changed over a period of and improved PSO, better solutions have been achieved. Fig.10 shows the variation in finishing time and waiting time for the assigned number of jobs and processors using Hybrid algorithm. Find a new particle using Accept new particle as best with probability as exp-(∆E/T) Reduce the temperature T End End Return by using Hybrid Fig. 10 Chart for job scheduling in multiprocessor with different stop number of processors and different number of jobs using Hybrid algorithm(Improved PSO with Simulated Annealing) Fig. 9 Flowchart for job scheduling using Improved PSO ISSN: 1109-2750 296 Issue 9, Volume 10, September 2011