ترکیبی از الگوریتم ژنتیک و تغییر گلوگاه برای مشکلات برنامه ریزی تولید کارگاهی انعطاف پذیر چند هدفه

Flexible job shop scheduling problem (fJSP) is an extension of the classical job shop scheduling problem, which provides a closer approximation to real scheduling problems. This paper addresses the fJSP problem with three objectives: min makespan, min maximal machine workload and min total workload. We develop a new genetic algorithm hybridized with an innovative local search procedure (bottleneck shifting) for the problem. The genetic algorithm uses two representation methods to depict solution candidates of the fJSP problem. Advanced crossover and mutation operators are proposed to adapt to the special chromosome structures and the characteristics of the problem. The bottleneck shifting works over two kinds of effective neighborhood, which use interchange of operation sequences and assignment of new machines for operations on the critical path. In order to strengthen search ability, the neighborhood structure can be adjusted dynamically in the local search procedure. The performance of the proposed method is tested by numerical experiments on a large number of representative problems.

Flexible job shop is a generalization of the job shop and the parallel machine environment, which provides a closer approximation to a wide range of real manufacturing systems. In particular, there are a set of work centers in a flexible job shop. Each work center has a set of parallel machines with possibly different efficiency. An operation can be performed by any machine in a work center. Consequently, this results in two problems. The first one is the routing problem (i.e., the assignment of operations to machines), and the second one is the scheduling problem (i.e., determining the starting time of each operation). The combination of the two decisions presents additional complexity and a new problem called flexible job shop scheduling problem (fJSP). The fJSP problem is NP-hard since it is an extension of the job shop scheduling problem (JSP) that has been proven to be NP-hard (Garey, Johmson, & Sethi, 1976). Bruker and Schlie (1990) developed a polynomial algorithm for solving the flexible job shop scheduling problem with two jobs. Chambers (1996) developed a tabu search algorithm to solve the problem. Mastrolilli and Gambardella (2000) proposed two neighborhood functions for the fJSP problem. Yang (2001) presented a new genetic algorithm (GA)-based discrete dynamic programming approach. Kacem, Hammadi, and Borne (2002a) proposed the approach by localization to solve the resource assignment problem, and an evolutionary approach controlled by the assignment model for the fJSP problem. Wu and Weng (2005) considered the problem with job earliness and tardiness objectives, and proposed a multiagent scheduling method. Xia and Wu (2005) treated this problem with a hybrid of particle swarm optimization and simulated annealing as a local search algorithm. Zhang and Gen (2005) proposed a multistage operation-based genetic algorithm to deal with the fJSP problem from a point view of dynamic programming. In this paper, a hybrid genetic algorithm (hGA) is used to solve the fJSP problem. The genetic algorithm uses two representation methods. One is used in initialization and mutation, and the other is used for crossover operation. In order to strengthen the search ability, bottleneck shifting serves as a kind of local search method under the framework of GA. The local search only investigates neighbor solutions that have possibilities to improve the incumbent one. The fJSP problem is described in Section 2. Section 3 presents the representation method, decoding procedure and genetic operators of the proposed GA. The details of the bottleneck shifting are presented in Section 4. In Section 5, we present computational study on a number of well-known fJSP benchmark problems and compare our results with those obtained by previous authors. Some final concluding remarks and future research directions are given in Section 6.

We developed a new approach hybridizing genetic algorithm with bottleneck shifting to fully exploit the “global search ability” of genetic algorithm and “the local search ability” of bottleneck shifting for solving multiobjective flexible job shop scheduling problems. An innovative two-vector Gen et al.’s representation scheme is proposed and an effective decoding method is used to interpret each chromosome into an active schedule. The initialization and mutation operations operate chromosomes of the two-vector Gen et al.’s representation. However, in order to enhance the heritability of crossover operation, chromosomes of the two-vector Gen et al.’s representation are transformed into the format of the two-vector permutation representation, and then an enhanced order crossover is proposed. Two kinds of neighborhood are defined based on the concept of critical path for the fJSP problem. The two kinds of neighborhood are quite effective in that they only contain solutions that are likely to improve the incumbent one. The number of critical paths serves as an additional intermediate objective besides the three original criteria in order to guide the local search to the most promising areas. In the local search, the neighborhood structure can be dynamically adjusted so that the quality of the local optima can be improved without incurring too much computational load. Well-known benchmark problems of different scales are solved by the proposed algorithm. The simulation results obtained in this study are compared with those obtained by other methods. We found better solutions for four instances and found the same good solutions for the rest instances as those obtained by the combined efforts of previous works. There are a number of research directions that can be considered as useful extensions of this approach. The balance between genetic search and local search, as well as the balance between depth search and broadness search within the bottleneck shifting, seem to be promising in improving the performance and efficiency of the hybrid algorithm. Research on these balancing problems should be interesting subjects.