  Scheduling jobs with given processing times on identical parallel machines so
as to minimize their total completion time is one of the most basic scheduling
problems. We study interesting generalizations of this classical problem
involving scenarios. In our model, a scenario is defined as a subset of a
predefined and fully specified set of jobs. The aim is to find an assignment of
the whole set of jobs to identical parallel machines such that the schedule,
obtained for the given scenarios by simply skipping the jobs not in the
scenario, optimizes a function of the total completion times over all
scenarios.
  While the underlying scheduling problem without scenarios can be solved
efficiently by a simple greedy procedure (SPT rule), scenarios, in general,
make the problem NP-hard. We paint an almost complete picture of the evolving
complexity landscape, drawing the line between easy and hard. One of our main
algorithmic contributions relies on a deep structural result on the maximum
imbalance of an optimal schedule, based on a subtle connection to Hilbert bases
of a related convex cone.
