NSGA-II with Iterated Greedy for a Bi-objective Three-stage Assembly Flowshop Scheduling Problem

In this paper we address a three-stage assembly flowshop scheduling problem where there are m machines at the first stage, a transportation machine at the second stage and an assembly machine at the third stage. At the first stage, different parts of a product are manufactured independently on parallel production lines. At the second stage, the manufactured parts are collected and transferred to the next stage. At the third stage, the parts are assembled into final products. The objective is to schedule n jobs on the machines so that total flowtime and the total tardiness of the jobs are minimized simultaneously. This problem has many applications in industry and belongs to the class of NP-Hard combinatorial optimization problems. In order to obtain near Pareto optimal solutions, we propose an Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) coupled with Iterated Greedy (IG) strategy. IG is a simple heuristic that has shown excellent results for different flowshop scheduling problems. A comparative study is presented between the results obtained using the standard NSGA-II, the enhanced NSGA-II with IG approach and a single-objective GRASP heuristic. Experimental results on both medium and large size of instances show the efficiency of the hybrid NSGA-II approach.