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.