New multi-objective method to solve reentrant hybrid flow shop scheduling problem

Frédéric Dugardin (1) , Farouk Yalaoui (1) , Lionel Amodeo (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

This paper focuses on the multi-objective resolution of a reentrant hybrid flow shop scheduling problem (RHFS). In our case the two objectives are: the maximization of the utilization rate of the bottleneck and the minimization of the maximum completion time. This problem is solved with a new multi-objective genetic algorithm called L-NSGA which uses the Lorenz dominance relationship. The results of L-NSGA are compared with NSGA2, SPEA2 and an exact method. A stochastic model of the system is proposed and used with a discrete event simulation module. A test protocol is applied to compare the four methods on various configurations of the problem. The comparison is established using two standard multi-objective metrics. The Lorenz dominance relationship provides a stronger selection than the Pareto dominance and gives better results than the latter. The computational tests show that L-NSGA provides better solutions than NSGA2 and SPEA2; moreover, its solutions are closer to the optimal front. The efficiency of our method is verified in an industrial field-experiment.

Domains: Operations Research [cs.RO]

Frédéric Dugardin, Farouk Yalaoui, Lionel Amodeo. New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 2010, 203 (1), pp.22-31. ⟨10.1016/j.ejor.2009.06.031⟩. ⟨hal-02611073⟩