Robust scheduling in a two-machine re-entrant flow shop to minimise the value-at-risk of the makespan: branch-and-bound and heuristic algorithms based on Markovian activity networks and phase-type distributions

This paper addresses a two-machine re-entrant flow shop scheduling problem with stochastic processing times where each job is expected to require a rework phase, flowing twice within the whole system. Due to the stochastic characteristics of the addressed problem, the proposed approach aims to devise robust schedules, i.e., schedules that are less sensitive to the occurrence of uncertain events, specifically, to the variability of the processing times. Two classes of approaches are proposed: the first is a branch-and-bound algorithm capable of solving the problem optimally, although with limitations regarding the size of the scheduling instances; the second is heuristic algorithms that can be applied to medium/large instances. For both approaches, the goal is to minimise the value-at-risk associated with the makespan, to assist decision-makers in balancing expected performance and mitigating the impact of extreme scenarios. A Markovian Activity Network (MAN) model is exploited to estimate the distribution of the makespan and evaluate its value-at-risk. Phase-type distributions are used to cope with general distributions for the processing times while exploiting a Markovian approach. A set of computational experiments is conducted to demonstrate the effectiveness and performance of the proposed approaches.