Efficient solutions to the m-machine robust flow shop under budgeted uncertainty

This work presents two solution methods for the m-machine robust permutation flow shop problem with processing time uncertainty. The goal is to minimize the makespan of the worst-case scenario by utilizing an approach based on budgeted uncertainty, in which only a subset of operations will reach their worst-case processing time values. To obtain efficient solutions to this problem, we first extend an existing two-machine worst-case procedure, based on dynamic programming, generalizing it to m machines. The worst-case calculation is then incorporated into two proposed solution methods: an exact column-and-constraint generation algorithm and a GRASP metaheuristic. Based on experiments with four sets of literature-based instances, empirical results demonstrate the ability of the GRASP to efficiently produce an optimal or near-optimal solution in most cases.