Multiobjective Flexible Job Shop Scheduling Using Memetic Algorithms

In this paper, we propose new memetic algorithms (MAs) for the multiobjective flexible job shop scheduling problem (MO-FJSP) with the objectives to minimize the makespan, total workload, and critical workload. The problem is addressed in a Pareto manner, which aims to search for a set of Pareto optimal solutions. First, by using well-designed chromosome encoding/decoding scheme and genetic operators, the nondominated sorting genetic algorithm II (NSGA-II) is adapted for the MO-FJSP. Then, our MAs are developed by incorporating a novel local search algorithm into the adapted NSGA-II, where some good individuals are chosen from the offspring population for local search using a selection mechanism. Furthermore, in the proposed local search, a hierarchical strategy is adopted to handle the three objectives, which mainly considers the minimization of makespan, while the concern of the other two objectives is reflected in the order of trying all the possible actions that could generate the acceptable neighbor. In the experimental studies, the influence of two alternative acceptance rules on the performance of the proposed MAs is first examined. Afterwards, the effectiveness of key components in our MAs is verified, including genetic search, local search, and the hierarchical strategy in local search. Finally, extensive comparisons are carried out with the state-of-the-art methods specially presented for the MO-FJSP on well-known benchmark instances. The results show that the proposed MAs perform much better than all the other algorithms. Note to Practitioners-The flexible job shop scheduling problem (FJSP) has important applications in textile, automobile assembly, semiconductor manufacturing, and many other industries. In the flexible job shop, a group of machines are capable for each operation, which is different from the traditional job shop environment where each operation can be processed by only a single machine. The FJSP is quite challenging, since the decisions include not only operation sequencing but also machine assignment. In the literature, the majority of studies for the FJSP are centered on optimizing the makespan. However, a single objective is deemed as insufficient for real and practical applications. Indeed, in the industry, production managers are usually concerned with more than one objective. This paper aims to simultaneously minimize the makespan, total workload, and critical workload for the FJSP, which can lead to both high throughput and load balance of machines. This problem is solved in the posterior approach, whose goal is to seek for a set of Pareto optimal solutions. We propose effective memetic algorithms (MAs) that combine a classical multiobjective evolutionary technique referred as NSGA-II with a novel problem-specific local search. To enhance the ability to deal with multiple objectives, a hierarchical strategy is used in local search which gives varying degrees of consideration to each objective. The effectiveness of the proposed MAs is well demonstrated by extensive comparisons against the existing best-performing algorithms for the considered problem. This work can be extended to those practical problems in the flexible manufacturing system. In addition, the idea to deal with objectives hierarchically can be generalized for the other production scheduling problems with multiple objectives, such as hybrid flow shop, blocking flow shop, and no-wait job shop.