A simheuristic algorithm for the stochastic permutation flow-shop problem with delivery dates and cumulative payoffs

Abstract

[EN] This paper analyzes the permutation flow-shop problem with delivery dates and cumulative payoffs (whenever these dates are met) under uncertainty conditions. In particular, the paper considers the realistic situation in which processing times are stochastic. The main goal is to find the permutation of jobs that maximizes the expected payoff. In order to achieve this goal, the paper first proposes a biased-randomized heuristic for the deterministic version of the problem. Then, this heuristic is extended into a metaheuristic by encapsulating it into a variable neighborhood descent framework. Finally, the metaheuristic is extended into a simheuristic by incorporating Monte Carlo simulations. According to the computational experiments, the level of uncertainty has a direct impact on the solutions provided by the simheuristic. Moreover, a risk analysis is performed using two well-known metrics: the value-at-risk and conditional value-at-risk.