Robust Permutation Flowshops Under Budgeted Uncertainty
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911712466173952 |
|---|---|
| author | Goldberg, Noam Hermelin, Danny Shabtay, Dvir |
| author_facet | Goldberg, Noam Hermelin, Danny Shabtay, Dvir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22110 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Robust Permutation Flowshops Under Budgeted Uncertainty Goldberg, Noam Hermelin, Danny Shabtay, Dvir Data Structures and Algorithms Discrete Mathematics Optimization and Control 90 F.2 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. |
| title | Robust Permutation Flowshops Under Budgeted Uncertainty |
| topic | Data Structures and Algorithms Discrete Mathematics Optimization and Control 90 F.2 |
| url | https://arxiv.org/abs/2602.22110 |