Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.
Job-shop scheduling problem (JSP), which is among the hardest combinatorial optimization problems (Sonmez & Baykasoglu, 1998), is a branch of production scheduling. It is well known that this problem is NP-hard (Garey, Johnson, & Sethi, 1976). The classical JSP schedules a set of jobs on a set of machines with the objective to minimize a certain criterion, subjected to the constraint that each job has a specified processing order through all machines which are fixed and known in advance.
Flexible job-shop problem (FJSP) is an extension of the classical JSP that allows one operation which can be processed on one machine out of a set of alternative machines. It is closer to the real manufacturing situation. Because of the additional needs to determine the assignment of operations on the machines, FJSP is more complex than JSP, and incorporates all the difficulties and complexities of JSP. The problem of scheduling jobs in FJSP could be decomposed into two sub-problems: a routing sub-problem, which is assigning each operation to a machine out of a set of capable machines and a scheduling sub-problem, which is sequencing the assigned operations on all selected machines in order to obtain a feasible schedule with optimized objectives (Xia & Wu, 2005). The scheduling problem in a flexible job shop is at least as hard as the job shop problem, which is considered one of the most difficult problems in combinatorial optimization (Lawler, Lenstra, Rinnooy Kan, & Shmoys, 1993). Although an optimal solution algorithm for the classical JSP has not been developed yet, there is a trend in the research community to model and solve much more complex version of the FJSP (Baykasoglu, Ozbakir, & Sonmez, 2004).
The research on the multi-objective FJSP is much less than the mono-objective FJSP. Brandimarte (1993) was the first to apply the decomposition approach into the FJSP. He solved the routing sub-problem by using some existing dispatching rules and then focused on the scheduling sub-problem, which was solved by using a tabu search heuristic. Hurink, Jurisch, and Thole (1994) proposed a tabu search heuristic. They considered the reassignment and rescheduling as two different types of moves. Mastrolilli and Gambardella (2000) proposed some neighborhood functions for the FJSP, which could be used in meta-heuristic optimization techniques. The most important issue in employing meta-heuristics for combinatorial optimization problems is to develop an effective “problem mapping” and “solution generation” mechanism. If these two mechanisms are devised successfully, it is possible to find good solutions to the given optimization problem in acceptable time. Parsopoulos and Vrahatis (2002) conducted the first research on the particle swarm optimization method in multi-objective optimization problems. Kacem et al., 2002a and Kacem et al., 2002b proposed a genetic algorithm controlled by the assigned model which was generated by the approach of localization (AL) to mono-objective and multi-objective FJSP. They used the integrated approach considering assignment and scheduling at the same time. Rigao (2004) developed two heuristics based on tabu search: a hierarchical procedure and a multiple start procedure. Recently, Xia and Wu (2005) proposed a hybrid algorithm using particle swarm optimization (PSO) assignment and simulated annealing (SA) scheduling to optimize multi-objective FJSP, respectively. To our knowledge, research on multi-objective FJSP is rather limited, and most traditional optimal approaches used only one optimization algorithm for solving multi-objective FJSP.
In this paper, the search mechanism of the particle swarm optimization and tabu search is taken full advantage of. An effective solution approach is proposed for solving multi-objective FJSP. The proposed approach uses PSO to assign operations on machines and to schedule operations on each machine, and TS is applied to local search for the scheduling sub-problem originating from each obtained solution. The objectives which are considered in this paper are to minimize maximal completion time, the workload of the critical machine and the total workload of machines simultaneously.
The remainder of this paper is organized as follows. The formulation and notion of multi-objective FJSP are introduced in Section 2. Section 3 describes the traditional PSO algorithm and summarizes the local search scheme by TS, and then the model of the proposed hybrid algorithm (PSO + TS) is given. At the same time, how to apply it to solve the multi-objective FJSP is described. Section 4 shows the four representative instances of multi-objective FJSP and the corresponding computational results with the proposed hybrid algorithm. Then, the computational results are compared with other heuristic algorithms in this section. Finally, concluding remarks and further research are given in Section 5.
In this paper, an effective hybrid particle swarm optimization algorithm is proposed to solve the multi-objective flexible job-shop scheduling problems. The performance of the presented approach is evaluated in comparison with the results obtained from other authors’ algorithms for four representative instances. The obtained computational results and time demonstrated the effectiveness of the proposed approach. And a more comprehensive computational study should be made to test the efficiency of proposed solution technique.
The future research directions include in the following:
•
designing more efficient information sharing mechanism and more effective local search strategy for solving multi-objective FJSP;
•
developing effective theory and algorithm for this complex combinatorial optimization problem are still needed;
•
applying PSO to other useful extensions research directions.
