The Applications Of Genetic Algorithms And Particle Swarm Optimization In Job-shop Scheduling Problems

Job-Shop scheduling problem is an important topic in combinatorial optimization.There are a lot of Job-Shop Scheduling problem instances in the real world. At the sametime, solving Job-Shop scheduling problem plays an important role in the theoreticalcomputer science. It is proved that exactly solving Job-Shop scheduling problem isNP-complete.Evolutionary algorithms, which simulates natural phenomenon, are randomalgorithms to solve combinatorial optimization problems. Comparing with classicalalgorithms, evolutionary algorithms can escape from local optimization and depend lesson the structure of the instance. So many researchers pay attention to solve Job-ShopScheduling problems by evolutionary algorithms.Firstly, the multi-step crossing genetic algorithm based on the mixing of the classicalgenetic algorithm and local search is used to solve Job-Shop Scheduling problems. In themulti-step crossover genetic algorithm, the parents are the initial values of the localsearch, and the children are the outputs of the local search. Furthermore, the feasiblesolution of the Job-Shop Scheduling problems is encoded by the disjunctive graph, andthe disjunctive distance of the feasible solutions, AS-neighborhood and CB-neighborhoodare defined accordingly.Secondly, the discrete particle swarm optimization algorithm is used to solve theJob-Shop Scheduling problem. In our algorithm, the random factor is introduced in theiterative equations to improve the diversity. The updated equations of the particles simulate the crossover operation and mutation operation of the classical genetic algorithm.Furthermore, the Job-Shop problems are encoded by two vectors.Finally, the classical genetic algorithm, the multi-step crossover genetic algorithmand the discrete swarm particle optimization are compared in terms of the experimentalresults.