Journal Article

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

Levorato, Mario, Figueiredo, Rosa, Sotelo, David, Frota, Yuri

2024

Overview

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.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Breakdowns / Decision making / Dynamic programming / Employment / Expected values / Fuzzy sets / Heuristic methods / Literature reviews / Optimization / Permutations / Probability / Probability distribution / Random variables / Robustness (mathematics) / Scheduling / Uncertainty