Robust Permutation Flowshops Under Budgeted Uncertainty
This provides a theoretical breakthrough for robust scheduling problems under budgeted uncertainty, offering exact polynomial-time solutions where previously only heuristic or integer programming methods existed.
The paper shows that the robust permutation flowshop problem under budgeted uncertainty can be solved by solving polynomially many nominal instances, leading to polynomial-time algorithms for two machines and polynomial-time approximations for any fixed number of machines, with a logarithmic improvement in running time for two and three machines.
We consider the robust permutation flowshop problem under the budgeted uncertainty model, where at most a given number of job processing times may deviate on each machine. We show that solutions for this problem can be determined by solving polynomially many instances of the corresponding nominal problem. As a direct consequence, our result implies that this robust flowshop problem can be solved in polynomial time for two machines, and can be approximated in polynomial time for any fixed number of machines. The reduction that is our main result follows from an analysis similar to Bertsimas and Sim (2003) except that dualization is applied to the terms of a min-max objective rather than to a linear objective function. Our result may be surprising considering that heuristic and exact integer programming based methods have been developed in the literature for solving the two-machine flowshop problem. Next, we show a logarithmic factor improvement in the overall running time implied by a naive reduction to nominal problems in the case of two machines and three machines. We conclude by noting that our reduction appears to have more general consequences for robust optimization problems under budgeted uncertainty having a similar form.