A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the particle position representation, particle movement, and particle velocity to better suit PSO for the JSP. We modified the particle position based on preference list-based representation, particle movement based on swap operator, and particle velocity based on the tabu list concept in our algorithm. Giffler and Thompson’s heuristic is used to decode a particle position into a schedule. Furthermore, we applied tabu search to improve the solution quality. The computational results show that the modified PSO performs better than the original design, and that the hybrid PSO is better than other traditional metaheuristics.
The job shop scheduling problem (JSP) is one of the most difficult combinatorial optimization problems. The JSP can be briefly stated as follows (French’s, 1982 and Gen and Cheng’s, 1997). There are n jobs to be processed through m machines. We shall suppose that each job must pass through each machine once and once only. Each job should be processed through the machines in a particular order, and there are no precedence constraints among different job operations. Each machine can process only one job at a time, and it cannot be interrupted. Furthermore, the processing time is fixed and known. The problem is to find a schedule to minimize the makespan (Cmax), that is, the time required to complete all jobs.
Garey, Johnson, and Sethi (1976) demonstrated that JSP is NP-hard, so it cannot be exactly solved in a reasonable computation time. Many approximate methods have been developed in the last decade to solve JSP, such as simulated annealing (SA) ( Lourenço, 1995), tabu search (TS) ( Nowicki and Smutnicki’s, 1996, Pezzella and Merelli’s, 2000 and Sun et al.’s, 1995), and genetic algorithm (GA) ( Bean’s, 1994, Gonçalves et al.’s, 2005, Kobayashi et al.’s, 1995 and Wang and Zheng’s, 2001). We applied a new evolutionary search technique – particle swarm optimization (PSO) – to solve the JSP in this paper.
The optimal JSP solution should be an active schedule. In an active schedule the processing sequence is such that no operation can be started any earlier without delaying some other operation (French, 1982). To reduce the search solution space, the tabu search proposed by Sun et al. (1995) searches solutions within the set of active schedules. In our algorithm, we applied Giffler and Thompson’s (1960) heuristic to decode a particle position into a schedule. Furthermore, we applied a tabu search to improve the solution quality.
The background of particle swarm optimization (PSO) is introduced in the next section. In Section 3, we propose a hybrid PSO for the JSP. In Section 4, we test the hybrid PSO on Fisher and Thompson’s, 1963, Lawrence’s, 1984 and Taillard’s, 1993 test problems. Finally, conclusions and remarks for further works are given in Section 5.
We have presented a hybrid particle swarm optimization (HPSO) for job shop scheduling problems in this paper. We modified the representation of particle position, particle movement, and particle velocity to better suit it for JSP. We also applied Tabu Search to improve solution quality. The computational results show that HPSO can obtain better solutions than other methods.
For further research, if the HPSO we proposed is implemented to other sequential ordering problems, there are two aspects for discussion: (1) Modify particle position representation for better suitability to the problem. In the original PSO design, the particles search solutions in a continuous solution space. Although most sequential ordering problems can be represented by the priority-based representation, it may not suit the sequential ordering problems that we illustrated in Section 3.1.1. Preference list-based representation or other representations will better suit the algorithm for sequential ordering problems. (2) Design other particle movement methods and particle velocity for the modified particle position representation. Besides, which particle movement method or particle velocity is better could be a further research topic.
