The job-shop scheduling problem has attracted many researchers’ attention in the past few decades, and many algorithms based on heuristic algorithms, genetic algorithms, and particle swarm optimization algorithms have been presented to solve it, respectively. Unfortunately, their results have not been satisfied at all yet. In this paper, a new hybrid swarm intelligence algorithm consists of particle swarm optimization, simulated annealing technique and multi-type individual enhancement scheme is presented to solve the job-shop scheduling problem. The experimental results show that the new proposed job-shop scheduling algorithm is more robust and efficient than the existing algorithms.
The job-shop scheduling problem (JSSP) is one of the existing combinatorial optimization problems and it has been demonstrated to be an NP-hard problem (Garey et al., 1976 and Lawer et al., 1993). In the job-shop scheduling problem, each one of n jobs (n⩾1)(n⩾1) must be processed passing through m machines (m⩾1)(m⩾1) in a given sequence. The sequence of m machines is different for each different job and cannot be changed during the processing. When one job was processed on a machine, it can be considered as one operation, each job View the MathML sourcej(1⩽j⩽n) needs a combination of m operations (oj1,oj2,…,ojm)(oj1,oj2,…,ojm) to complete the work. One operation is processed on one of m machines, and just only one operation can be processed at a time. Any job cannot interrupt the machine that is processing one operation of another job. Each machine can process at most one operation at the same time. The main objective of the job-shop scheduling problem is to find a schedule of operations that can minimize the maximum completion time (called makespan) that is the completed time of carrying total operations out in the schedule for n jobs and m machines.
JSSP can be applied to the manufacture processing and effects really the production time and the cost of production for a plant. During the past few decades, JSSP has attracted many researchers to develop algorithms. Because JSSP is an NP-hard problem, it is difficult to develop a perfect algorithm to find a solution within a reasonable time especially for higher dimensions. Recently, many researchers made use of evolution algorithm to solve the problem, such as tabu search method (Nowicki and Smutnicki, 2005 and Ponnambalam et al., 2000), genetic algorithm (Goncalves et al., 2005, Park et al., 2003, Wang and Zheng, 2001 and Watanabe et al., 2005), simulated annealing (Van Laarhoven et al., 1992, Steinhöel et al., 1999 and Suresh and Mohanasundaram, 2005), ant colony (Udomsakdigool and Kachitvichyanukul, 2008 and Zhou et al., 2004) and particle swarm optimization (Ge et al., 2007, Ge et al., 2008 and Lian et al., 2006). In this paper, we focus on exploiting particle swarm optimization algorithm to achieve the better solution for JSSP.
Particle swarm optimization (PSO) is developed by Kennedy and Eberhart (Kennedy & Eberhart, 1995). The position of one particle is corresponding to a solution of the solving problem. Liking a bird that flies to the food, one particle moves its position to a better solution according to the best particle’s experience and its own experience. Every particle moves iteratively until the end of iterations. We call this process as evolution process. At the end of iterations, the position of best particle is the best solution of the solving problem. The original developed PSO is designed to search solution in a continuous space. Because PSO’s local search ability is weaker than global searching ability, in order to get better solution, some local search schemes should be integrated with the PSO. In this paper, we embedded a multi-type individual enhancement scheme (MIE) based on simulated annealing technique into particle swarm optimization (PSO). The proposed algorithm enhances the particle’s searching ability and is suitable to solve the JSSP. The experimental results show that the proposed PSO with multi-type individual enhancement scheme outperforms the original PSO and is more efficient than those of existing meta-heuristics methods such as discrete particle swarm optimization with simulated annealing model (named HEA (Ge et al., 2007)), discrete particle swarm optimization with artificial immune system (named HIA (Ge et al., 2008)) and genetic algorithm (named HGA (Goncalves et al., 2005)) for JSSP scheduling problem, respectively.
The remainder of the paper is organized as follows: an introduction for the job-shop scheduling problem and particle swarm optimization are given in Sections 2 and 3, respectively. Section 4 gives a detailed description of the new proposed job-shop scheduling algorithm. Section 5 discusses the experimental results. Finally, Section 6 summarizes the contribution of this paper.
In this paper, an algorithm called MPSO that combining random-key (RK) encoding scheme, multi-type individual enhancement scheme (MIE), and particle swarm optimization (PSO) is proposed to solve the NP-hard JSSP problem. For combinatorial optimization problems such as JSSP, the search space is a discrete space that used by HIA (Ge et al., 2008) and HEA (Ge et al., 2007). But, MPSO adopts the real space as the search space called random-key (RK) space. In RK space, a position of a particle composed of n×mn×m real numbers can represent the permutation of all operations of all jobs by the encoding scheme. It is very different to most of other proposed algorithms for solving the job shop scheduling problems and is easy to escape the limit of each type of combinatorial optimization problems.
Many pre-proposed evolutionary algorithms for solving JSSP need a heuristic algorithm to initialize a population in order to speed the convergence rate. It has a drawback of increasing the computational load. It need not use any one heuristic algorithm in the proposed MPSO algorithm and can still achieve a better solution. MPSO is tested and approved with 43 instances that are a standard benchmark taken from the OR-Library. According to the experimental results, MPSO can reach the optimal area in the search space with smaller population size and iterations than other existing algorithms achieved. Of course, for another important achievement, combining a multi-type individual enhancement scheme into the PSO can achieve a superior result. For other variant job scheduling, we believe MPSO can easily be applied to solve these problems in the future research.
