A robust flexible flow shop problem under processing and release times uncertainty

Abstract

The aim of this paper is to present a simheuristic approach that obtains robust solutions for a multi-objective hybrid flow shop problem under uncertain processing and release times. This approach minimizes the expected tardiness and standard deviation of tardiness, as a robustness measure for the stated problem. The simheuristic algorithm hybridizes the NSGA-II with a Monte Carlo Simulation process. Initially, the deterministic scenario was tested on 32 different created small size instances and 32 medium and large benchmarked instances. As a result, the proposed algorithm improved quality of solutions by 1.21% against the MILP model and it also performed better than ERD, NEHedd, and ENS2, while consuming a reasonable computational time. Afterwards, one experimental design was carried out using 10 random instances from the same benchmark as a blocking factor, where four factors of interest were considered. The factors and their respective values are number of generations (50, 100), crossover probability (0.8, 0.9), mutation probability (0.1, 0.2), and population size (60, 100). Results show that the factors instance, mutation probability and number of generations, as well as other interactions between them, have a significant effect in the total tardiness for the deterministic scenario, proving the importance of an appropriate selection of parameters when using genetic algorithms to obtain quality solutions. Then, the performance of the proposed NSGA-II was compared against ERD, NEHedd, and ENS2 methods. Results show that our algorithm improves the quality of the solutions for both objective functions, proving the robustness of our solutions for the HFS problem. Finally, two additional generalized experiments were carried out to analyze the effect of number of jobs (10, 20), number of stages (2, 3), shop condition (0.2, 0.6), probability distribution (uniform, lognormal), and CV (0.05, 0.25, 0.4) on both objective functions. The shop condition, probability distribution and CV were proven to be highly influential on the variability of the results, with the only exception being the coefficient of variation having no statistically significant effect on the total tardiness.