Non-indexability of the stochastic appointment scheduling problem

Abstract: Consider a set of jobs with independent random service times to be scheduled on a single machine. The jobs can be surgeries in an operating room, patients' appointments in outpatient clinics, etc. The challenge is to determine the optimal sequence and appointment times of jobs to minimize some function of the server idle time and service start-time delay. We introduce a generalized objective function of delay and idle time, and consider

l_{1}

-type and

l_{2}

-type cost functions as special cases of interest. Determining an index-based policy for the optimal sequence in which to schedule jobs has been an open problem for many years. For example, it was conjectured that `least variance first' (LVF) policy is optimal for the

l_{1}

-type objective. This is known to be true for the case of two jobs with specific distributions. A key result in this paper is that the optimal sequencing problem is non-indexable, i.e., neither the variance, nor any other such index can be used to determine the optimal sequence in which to schedule jobs for

l_{1}

and

l_{2}

-type objectives. We then show that given a sequence in which to schedule the jobs, sample average approximation yields a solution which is statistically consistent.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

BRENT

This page was built for publication: Non-indexability of the stochastic appointment scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188257)