  We study single-machine scheduling of jobs, each belonging to a job type that
determines its duration distribution. We start by analyzing the scenario where
the type characteristics are known and then move to two learning scenarios
where the types are unknown: non-preemptive problems, where each started job
must be completed before moving to another job; and preemptive problems, where
job execution can be paused in the favor of moving to a different job. In both
cases, we design algorithms that achieve sublinear excess cost, compared to the
performance with known types, and prove lower bounds for the non-preemptive
case. Notably, we demonstrate, both theoretically and through simulations, how
preemptive algorithms can greatly outperform non-preemptive ones when the
durations of different job types are far from one another, a phenomenon that
does not occur when the type durations are known.
