This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives – the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing’s algorithm by Xing, Chen, and Yang (2009a) in terms of both solution quality and efficiency.
As a branch of production scheduling problems, the classical job-shop scheduling problem (JSP) has been proven to be an NP-hard problem (Garey, Johnson, & Sethi, 1976). The flexible job-shop scheduling problem (FJSP) is an extension of the classical JSP, which allows one operation to be processed on one machine from a set of alternative machines. Therefore, FJSP is more complex than JSP because of the addition need to determine the assignment of machines for each operation. Flexibility of the FJSP can be generally categorized into partial flexibility and total flexibility. If each operation can be processed on any machine in the system, we have a total FJSP (T-FJSP); otherwise flexibility would be partial (P-FJSP).
The FJSP has recently captured the interests of many researchers. Due to the complexity of the FJSP, meta-heuristic algorithms have become a practical alternative of solving techniques. Brandimarte (1993) proposed a hybrid tabu search algorithm with some existing dispatching rules to solve the single-objective FJSP. Mastrolilli and Gambardella (2000) used local search techniques and developed two neighborhood functions for the problem. The experimental results of Mastrolilli and Gambardella (2000) are considered to be the best results for FJSP by tabu search approach so far (Pezzella, Morganti, & Ciaschetti, 2008). Gao, Peng, Zhou, and Li (2006) presented a general particle swarm optimization (PSO) algorithm to solve the FJSP. Liouane, Saad, Hammadi, and Borne (2007) solved the problem with a hybrid algorithm combining ant colony optimization (ACO) with TS. Saidi-mehrabad and Fattahi (2007) developed an improved TS algorithm for FJSP. Gao, Sun, and Gen (2008) proposed a hybrid genetic algorithm (GA) with a variable neighborhood descent (VND) algorithm to deal with the FJSP while Pezzella et al. (2008) introduced a GA integrating different strategies to generate the initial population for the FJSP.
Although the single-objective FJSP has been widely investigated, the research on the multi-objective FJSP is still considered limited. Kacem et al., 2002a and Kacem et al., 2002b developed an effective evolutionary algorithm controlled by an assigned model based on the approach of localization (AL). Xia and Wu (2005) presented a hierarchical solution approach by using a PSO algorithm to assign operations on machines and a simulated annealing (SA) algorithm to schedule operations on each machine. An algorithm hybridized with evolving dispatching rules and genetic programming was proposed by Tay and Ho (2008). Xing et al. (2009a) gave a simulation model for solving multi-objective FJSP, which is a general framework for the problem and easy to apply different algorithms for it. A local search algorithm was introduced by Xing, Chen, and Yang (2009b) for solving multi-objective T-FJSPs and P-FJSPs. The experimental results show that Xing’s algorithms (Xing et al., 2009a and Xing et al., 2009b) are efficient especially for solving large scale T-FJSP problems. Lastly, Zhang et al. (2009) introduced a hybrid PSO and TS algorithm to solve the multi-objective FJSP.
In this paper, we propose a hybrid tabu search algorithm (HTSA) for the multi-objective flexible job-shop scheduling problem. In the proposed HTSA, two adaptive neighborhood search rules are presented for performing local search in the machine assignment module. Meanwhile, three insert and swap neighborhood structures based on the public critical blocks theory are developed to produce optimal adjustment in the operation scheduling module. In addition, an efficient left-shift function is designed to decode a solution to an active schedule.
The rest of this paper is organized as follows: In Section 2, we briefly describe the problem formulation. Then, the framework of the hybrid algorithm is presented in Section 3. The TS algorithm for the machine assignment component is shown in Section 4 while Section 5 introduces the variable neighborhood search algorithm for the operation scheduling component. Section 6 shows the experimental results and compares with other algorithms in the literature to demonstrate the superiority of the HTSA performance. Finally, the last section presents conclusions of our work.
In this paper, we proposed a hybrid TS algorithm for solving the multi-objective FJSP problems. To construct improved local search in the machine assignment module, an effective neighborhood structure with two adaptive rules was developed in the hybrid algorithm. In addition, a speed-up local search method with three kinds of insert and swap neighborhood structures based on public critical block theory is presented, which dwindled the search space deeply and helped to improve the solution quality as well as the search speed in the operation scheduling module. A well-designed left-shift function is also introduced to decode an encoding solution to an active schedule. The experimental results in Section 6 confirm that HTSA shows its superiority to other competing approaches including the AL + CGA algorithm (Kacem et al., 2002b), the PSO + SA algorithm (Xia & Wu, 2005), the PSO + TS algorithm (Zhang et al., 2009), and the Xing’s algorithm (Xing et al., 2009a and Xing et al., 2009b) for solving both the multi-objective T-FJSPs and the P-FJSPs. The future work is to apply the hybrid algorithm to other kinds of combinatorial optimization problems and develop some other hybrid algorithms for solving the multi-objective FJSP problems.
