A robust basic cyclic scheduling problem
This paper addresses the Basic Cyclic Scheduling Problem where the processing times are affected by uncertainties. We formulate the problem as a two-stage robust optimization problem with a budgeted uncertainty set. More precisely, we consider the uncertainty set introduced by Bertsimas and Sim (Ope...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2018
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/15acdbc9b02f4ffdb5ab61490b1f53a8 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | This paper addresses the Basic Cyclic Scheduling Problem where the processing times are affected by uncertainties. We formulate the problem as a two-stage robust optimization problem with a budgeted uncertainty set. More precisely, we consider the uncertainty set introduced by Bertsimas and Sim (Oper Res 52(1):35–53, 2004) where the activity durations are subject to interval uncertainty and the level of robustness is controlled by a parameter. We propose three exact algorithms for solving the problem. Two of them use a negative circuit detection algorithm as a subroutine, and the last one is a Howard’s algorithm adaptation. Results of numerical experiments on randomly generated instances show that the Howard’s algorithm adaptation yields efficient results and opens perspectives on more difficult robust cyclic scheduling problems. |
|---|