Minimizing the weighted sum of completion times under processing time uncertainty

Zacharie Alès, Thi Sang Nguyen and Michael Poss

february, 2018

Type de publication :

Article (revues avec comité de lecture)

Journal :

Electronic Notes in Discrete Mathematics, vol. 64, pp. 15 - 24

Editeur :

Elsevier

DOI :

10.1016/j.endm.2018.01.003

HAL :

hal-01768638

Mots clés :

Integer programming Robust optimization Scheduling

Résumé :

We address the robust counterpart of a classical single machine scheduling problem by considering a budgeted uncertainty and an ellipsoidal uncertainty. We prove that the problem is N P-hard for arbitrary ellipsoidal uncertainty sets. Then, a mixedinteger linear programming reformulations and a second order cone programming reformulations are provided. We assess the reformulations on randomly generated instances, comparing them with branch-and-cut algorithms.

BibTeX :

@article{Ale-Ngu-Pos-2018,
    author={Zacharie Alès and Thi Sang Nguyen and Michael Poss },
    title={Minimizing the weighted sum of completion times under 
           processing time uncertainty },
    doi={10.1016/j.endm.2018.01.003 },
    journal={Electronic Notes in Discrete Mathematics },
    year={2018 },
    month={2},
    volume={64 },
    pages={15--24},
}