Minimizing worst-case and average-case makespan over scenarios

FEUERSTEIN ESTEBAN; SITTERS RENE; VAN ZUYLEN ANKE; MARCHETTI-SPACCAMELA ALBERTO; VAN DER STER SUZANNE; SCHALEKAMP FRANS; STOUGIE LEEN

JOURNAL OF SCHEDULING

SPRINGER

Lugar: Berlin; Año: 2016 p. 1 - 11

1094-6136

We consider scheduling problems over scenarioswhere the goal is to find a single assignment of the jobs tothe machines which performs well over all scenarios in anexplicitly given set. Each scenario is a subset of jobs thatmust be executed in that scenario. The two objectives thatwe consider are minimizing the maximum makespan overall scenarios and minimizing the sum of the makespans ofall scenarios. For both versions, we give several approximationalgorithms and lower bounds on their approximability.We also consider some (easier) special cases. Combinatorialoptimization problems under scenarios in general, andscheduling problems under scenarios in particular, have seenonly limited research attention so far. With this paper, wemake a step in this interesting research direction.