Non-indexability of the stochastic appointment scheduling problem

DOI10.1016/J.AUTOMATICA.2020.109016zbMATH Open1447.90015arXiv1708.06398OpenAlexW3024612361MaRDI QIDQ2188257FDOQ2188257

Authors: Mehdi Jafarnia-Jahromi, Rahul Jain 

Publication date: 10 June 2020

Published in: Automatica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1708.06398

Recommendations

• Appointment scheduling with discrete random durations
• Appointment scheduling with discrete random durations
• A note on appointment scheduling with piecewise linear cost functions
• On index policies for stochastic minsum scheduling
• Optimized appointment scheduling

zbMATH Keywords

sequencingsample average approximationoperations research applicationsstochastic appointment scheduling

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36)

Cites Work

• Lectures on Stochastic Programming
• Über die Verallgemeinerung des Begriffes der zueinander konjugierten Potenzen
• Scheduling. Theory, algorithms, and systems.
• Title not available (Why is that?)
• Operating room planning and scheduling: a literature review
• The construction of stable project baseline schedules
• Monte Carlo bounding techniques for determinig solution quality in stochastic programs
• Title not available (Why is that?)
• Sequencing and scheduling \(N\) customers for a stochastic server
• Scheduling arrivals to a stochastic service delivery system using copositive cones
• Appointment scheduling with discrete random durations
• Optimized appointment scheduling
• Title not available (Why is that?)
• On sample size control in sample average approximations for solving smooth stochastic programs
• Optimal booking and scheduling in outpatient procedure centers
• Title not available (Why is that?)
• Minimizing earliness and tardiness costs in stochastic scheduling
• Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment
• Outpatient appointment systems in healthcare: a review of optimization studies
• Title not available (Why is that?)
• Appointment sequencing: why the smallest-variance-first rule may not be optimal
• Optimal appointment scheduling in continuous time: the lag order approximation method
• Technical Note—A Sampling-Based Approach to Appointment Scheduling
• Optimal stationary appointment schedules

Cited In (3)

• Optimal sequencing using a scheduling heuristic
• A note on appointment scheduling with piecewise linear cost functions
• Current trends in operating room scheduling 2015 to 2020: a literature review

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)