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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Idir Hamaz, Laurent Houssin, Sonia Cafieri
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90-08 90B35 90B36 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/15acdbc9b02f4ffdb5ab61490b1f53a8
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:15acdbc9b02f4ffdb5ab61490b1f53a8
record_format	dspace
spelling	oai:doaj.org-article:15acdbc9b02f4ffdb5ab61490b1f53a82021-12-02T05:01:08ZA robust basic cyclic scheduling problem2192-440610.1007/s13675-018-0100-3https://doaj.org/article/15acdbc9b02f4ffdb5ab61490b1f53a82018-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001040https://doaj.org/toc/2192-4406This 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.Idir HamazLaurent HoussinSonia CafieriElsevierarticle90-0890B3590B36Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 3, Pp 291-313 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-08 90B35 90B36 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-08 90B35 90B36 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Idir Hamaz Laurent Houssin Sonia Cafieri A robust basic cyclic scheduling problem
description	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.
format	article
author	Idir Hamaz Laurent Houssin Sonia Cafieri
author_facet	Idir Hamaz Laurent Houssin Sonia Cafieri
author_sort	Idir Hamaz
title	A robust basic cyclic scheduling problem
title_short	A robust basic cyclic scheduling problem
title_full	A robust basic cyclic scheduling problem
title_fullStr	A robust basic cyclic scheduling problem
title_full_unstemmed	A robust basic cyclic scheduling problem
title_sort	robust basic cyclic scheduling problem
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/15acdbc9b02f4ffdb5ab61490b1f53a8
work_keys_str_mv	AT idirhamaz arobustbasiccyclicschedulingproblem AT laurenthoussin arobustbasiccyclicschedulingproblem AT soniacafieri arobustbasiccyclicschedulingproblem AT idirhamaz robustbasiccyclicschedulingproblem AT laurenthoussin robustbasiccyclicschedulingproblem AT soniacafieri robustbasiccyclicschedulingproblem
_version_	1718400814834253824

A robust basic cyclic scheduling problem

Ejemplares similares