Solving Job Shop Scheduling Problems Using Particle Swarm Optimization And Artificial Immune System

The job shop scheduling problem (JSSP) is a very important practicalproblem in both fields of production management and combinatorialoptimization. Efficient methods for arranging production and scheduling arevery important for increasing production efficiency, reducing cost andimproving product quality. JSSP is among the worst members of class ofNP-complete, the study of it started from the year 1954, so far, there havebeen many methods for solving it, such as branch and bound, dynamicprogramming, dispatching priority rules, shifting bottleneck, Lagrangianrelaxation and tabu search. In this paper, we propose a PSO-AIS-basedhybrid intelligent algorithm for job shop scheduling problem.In this paper, we begin with the introduction of job shop schedulingproblem, and then analyses its complexity. After studying and examining theproblem carefully, we give a conceptual model of it. Before solving JSSP, wedescribe a proper representation for the solution of the problem, namelyencode and decode, which is used in the proposed algorithms. After decodingthe code of a solution, we get a complete scheduling of the solution.According the scheduling of the solution, we can calculate the finishing timeof all the operations, namely makespan. We makeup a fitness value of thesolution with makespan, which is used for evaluate the solution.After we get an initial population of the solution code, our emphaseswork is perform PSO and AIS operations on the colony, and then get a bestscheduling.The brief outline of the PSO for JSSP is as follows: each individual inthe colony can be taken as a particle, which is evaluated by its fitness value.Each particle can change its position according its experience and otherparticle's experience. The effect is that they can find the best solution after acertain time. The conventional PSO cannot be applied to JSSP directly. In thispaper, we extend the concept of distance and velocity. Distance between twoparticles can be defined as the difference of them. And the velocity of eachparticle can be defined as times of adjust operation towards its previous bestposition and the best position among all the particles. Each particle adjusts itsvelocity according to its own velocity, the distance with its previous bestparticle and the best one among all the particles. It also adjusts it positionaccording to its velocity. After a certain time we can get a best solution.The outline of AIS for JSSP can be described as follows: consider thebest solution as antigen and consider each candidate solution as antibody.Calculate the fitness value of each antibody and then calculate the density ofit. We can get the affinity of each antibody with the fitness value and density,the higher the fitness value, the higher affinity;the higher density, the loweraffinity. According to the clone selection principle, the higher affinity anantibody has, the higher selection chance to the clone library. And thenperform high rate mutation operations at the clone library individuals. Afterthat we replace the worst ones in the initial colony by the best ones in theclone library. Because the room of searching space is very large, we maysearch the best solution in the wrong direction. Considering this, we adopt theimmune memory mechanism. The brief outline is as follows: set up a new setwhich contains the best antibodies in the colony. Examine the best antibody'sfitness value after certain iterations. If there is improvement of it, replace theantibodies in the set by the best ones of the colony. If there isn't anyimprovement of it, replace the worst antibodies in the colony by theantibodies in the set.When solving JSSP by the hybrid intelligent algorithm, we first proposea new scheduling initialization algorithm based on the well known algorithmof Giffler and Thompson. PSO operations and AIS operations are performedon the same colony. Each individual in the colony is called a particle in thePSO model and also called an antibody in the AIS model. We adopt the samefitness value in the two models and perform PSO operation and then AISoperation each time.The performance of proposed PSO-AIS-based algorithm is examined byusing 43 test problems taken from the OR-Library. The proposed algorithm isable to find the best known solution for 32 instances. From simulation resultsit can be concluded that the proposed hybrid algorithm solves the JSSP fairlyefficiently.