Learning in scheduling: simple policies for Bayesian scheduling.

Abstract: We consider the problem of scheduling jobs on a single machine, non-preemptively. The goal is to minimize the total completion time of the jobs. It is well known that this problem is solved by scheduling the jobs in order of shortest processing times (SPT) when the jobs’ processing times are known or shortest expected processing times (SEPT), when we have full knowledge on the true expected values.

In this talk, we consider the stochastic scheduling problem in which we have additional uncertainty about the parameters of the distribution of the jobs’ processing times. We assume that jobs appear in $m$ classes and the processing times of jobs in one class are independently and identically distributed. By processing a job from one class one can learn about the true parameters of the distribution. The initial beliefs on these parameters are modelled as a prior distribution and after processing a job the posterior distribution models the updated beliefs on the parameter.

When the processing times are exponentially distributed with an unknown parameter that is gamma distributed, optimal policies based on Gittins-indices exist (see, e.g., Hamada and Glazebrook, 1993). However, computing these indices may be computationally challenging.

In this talk, we consider two simple policies, based on SEPT. The first policy processes the jobs based on the initial beliefs of the expected processing time. This implies that all jobs of one class are processed consecutively. The second policy, always processes a job from a class with shortest expected processing time according to the updated beliefs.

We can show that both policies have a (worst-case) approximation ratio of $m$, the number of classes, and that this ratio is tight.

Posted on May 9, 2023 in ACGO, Seminars