Minimizing the weighted sum of completion times under processing time uncertainty

Zacharie Alès, Thi Sang Nguyen and Michael Poss

february, 2018

Publication type:

Paper in peer-reviewed journals

Journal:

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

Publisher:

Elsevier

DOI:

10.1016/j.endm.2018.01.003

HAL:

hal-01768638

Keywords :

Integer programming Robust optimization Scheduling

Abstract:

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},
}