A parallel genetic algorithm for multi-objective flexible flowshop scheduling in pasta manufacturing. (November 2021) - Shen, Ke; De Pessemier, Toon; Martens, Luc; Joseph, Wout
Highlights: We introduce a generalized flexible flowshop model with non-identical parallel machines. We propose a specialized parallel genetic algorithm (GA) based on the island model. Multi-objectives are addressed by a new application of Pareto-dominance. The effectiveness of the algorithm is demonstrated on benchmark and real-sized instances. The performance of the algorithm is compared with the traditional GA and the NSGA-II. Abstract: Among the potential road maps to sustainable production, efficient manufacturing scheduling is a promising direction. This paper addresses the lack of knowledge in the scheduling theory by introducing a generalized flexible flow shop model with unrelated parallel machines in each stage. A mixed-integer programming formulation is proposed for such model, solved by a two-phase genetic algorithm (GA), tackling job sequencing and machine allocation in each phase. The algorithm is parallelized with a specialized island model, where the evaluated chromosomes of all generations are preserved to provide the final Pareto-Optimal solutions. The feasibility of our method is demonstrated with a small example from literature, followed with the investigation of the premature convergence issue. Afterwards, the algorithm is applied to a real-sized instance from a Belgium pasta manufacturer. We illustrate how the algorithm converges over iterations to trade-off near-optimal solutions (with 8.50% shorter makespan, 5.24% cheaper energy cost and 6.02% lower labor cost), and how the evaluated candidates distribute in the objective space. A comparison with a NSGA-II implementation is further performed using hypothesis testing, having 5.43%, 0.95% and 2.07% improvement in three sub-objectives mentioned above. Although this paper focuses on scheduling issues, the proposed GA can serve as an efficient method for other multi-objective optimization problems.