A Hybrid Particle Swarm Optimization Algorithm for Solving Job Shop Scheduling Problems
This paper proposes a new hybrid PSO optimization algorithm, which fuses GA and simulated annealing (SA) into the PSO algorithm. The crossover and mutation mechanism of GA algorithm make the new hybrid algorithm keep the diversity of population and retain
- PDF / 555,781 Bytes
- 8 Pages / 439.37 x 666.14 pts Page_size
- 2 Downloads / 266 Views
)
State CIMS Engineering Research Center at Tsinghua University, Beijing 100084, China [email protected]
Abstract. This paper proposes a new hybrid PSO optimization algorithm, which fuses GA and simulated annealing (SA) into the PSO algorithm. The crossover and mutation mechanism of GA algorithm make the new hybrid algorithm keep the diversity of population and retain the good factors in the population to jump out of local optimum. The sudden jump probability of SA also guarantees the diversity of the population, thus preventing local minimum of the hybrid PSO algorithm. This new hybrid algorithm is used to minimize the maximum comple‐ tion time of the scheduling problems. The simulation results show that the performance of hybrid optimization algorithm outperforms another hybrid PSO algorithm. The hybrid PSO algorithm is not only in the structure of the algorithm, but also the search mechanism provides a powerful way to solve JSSP. Keywords: Job shop scheduling problem · Particle swarm optimization · Simulated annealing · Maximum completion time
1
Introduction
Job Shop scheduling problem (JSSP) is demonstrated to be a classic NP-hard combi‐ natorial optimization problem [1] which plays an important role in computer integrated manufacturing system and has vital effect on production management and control system. As one class of typical production scheduling problems, JSSP has attracted many scholars to study this field for last decades. It consists of a finite jobs set, Ji (i = 1, 2, …, n) to be processed on a finite machine set Mk (k = 1, 2, …, m) [2]. According to its produc‐ tion routine, each job is processed on machines with a given processing time, and each machine can process only one operation for each job [3]. JSSP can be thought of as the allocation of resources over a specified time to perform a predetermined collection of tasks [4]. Many different heuristics algorithms are developed for this problem in last decades. With the development of intelligent technology, more and more evolutionary algorithms have been applied to JSSP and have got many good results. Phanden et al. [5] present a simulation-based genetic algorithm approach for JSSP, with and without restart scheme. Meng and Zhou [6] put forward immune genetic algo‐ rithm adopting timely dynamic vaccination and the shutdown criteria. Sun and Xiong [7] introduced the Metropolis sampling criteria in simulation annealing algorithm into algorithm, and proposed three kinds of hybrid PSO algorithms integrating simulation © Springer Science+Business Media Singapore 2016 L. Zhang et al. (Eds.): AsiaSim 2016/SCS AutumnSim 2016, Part II, CCIS 644, pp. 71–78, 2016. DOI: 10.1007/978-981-10-2666-9_8
72
Q. Meng et al.
annealing to solve part of FT problems and LA problems. Bank et al. [8] studies a permutation flow shop scheduling problem with deteriorating jobs. Gao et al. [9] designs a hybrid intelligence algorithm based on Particle Swarm algorithm and the Taboo Search algorithm (TS-PSO). Through particle swarm and Taboo search algorithm combined, the resul
Data Loading...
