Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem

Abstract. The importance of multi-objective optimization is globably established nowadays. Furthermore, a great part of real-world problems are subject to uncertainties due to, e.g., noisy or approximated fitness function(s), varying parameters or dynamic environments. Moreover, although evolutionary algorithms are commonly used to solve multi-objective problems on the one hand and to solve stochastic problems on the other hand, very few approaches combine simultaneously these two aspects. Thus, flow-shop scheduling problems are generally studied in a single-objective deterministic way whereas they are, by nature, multi-objective and are subjected to a wide range of uncertainties. However, these two features have never been investigated at the same time. In this paper, we present and adopt a proactive stochastic approach where processing times are represented by random variables. Then, we propose several multi-objective methods that are able to handle any type of probability distribution. Finally, we experiment these methods on a stochastic bi-objective flow-shop problem. Key words: multi-objective combinatorial optimization, stochasticity, evolutionnary algorithms, flow-shop, stochastic processing times