  We study a single-server scheduling problem for the objective of minimizing
the expected cumulative holding cost incurred by jobs, where parameters
defining stochastic job holding costs are unknown to the scheduler. We consider
a general setting allowing for different job classes, where jobs of the same
class have statistically identical holding costs and service times, with an
arbitrary number of jobs across classes. In each time step, the server can
process a job and observes random holding costs of the jobs that are yet to be
completed. We consider a learning-based $c\mu$ rule scheduling which starts
with a preemption period of fixed duration, serving as a learning phase, and
having gathered data about jobs, it switches to nonpreemptive scheduling. Our
algorithms are designed to handle instances with large and small gaps in mean
job holding costs and achieve near-optimal performance guarantees. The
performance of algorithms is evaluated by regret, where the benchmark is the
minimum possible total holding cost attained by the $c\mu$ rule scheduling
policy when the parameters of jobs are known. We show regret lower bounds and
algorithms that achieve nearly matching regret upper bounds. Our numerical
results demonstrate the efficacy of our algorithms and show that our regret
analysis is nearly tight.
