Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Early or tardy surgeries are frustrating for both patients and personnel, and cause inefficient use of resources at the operating rooms. The stochastic Earliness/Tardiness (E/T) scheduling problem addresses this by minimizing the total expected deviation of the surgery completion times from the planned completion times. We introduce the concept of E/T-concavity as a property of a probability distribution if the E/T costs are concave as a function of the standard deviation of the completion time, whenever the optimal planned completion times are selected. We use this concept to generate an optimal schedule for the multiple machine variant of the E/T problem. The optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the E/T objective. We demonstrate the usefulness of our results in practice by proving E/T-concavity for several probability distributions and by showing that, under the assumption of E/T-concavity, a simple Shortest Variance First (SVF) rule is optimal. We conclude by providing a numerical example of surgery scheduling where we demonstrate the benefits of the SVF rule compared to several commonly used scheduling rules.
Original languageEnglish
Article number100194
Number of pages9
JournalOperations research for health care
Volume22
Early online date15 Jul 2019
DOIs
Publication statusPublished - 1 Sep 2019

Fingerprint

Earliness-tardiness
Surgery
Scheduling
Costs and Cost Analysis
Completion Time
Costs
Concavity
Appointments and Schedules
Operating Rooms
Schedule
Probability Distribution
Standard deviation
Demonstrate
Scheduling Problem
Deviation
Numerical Examples
Resources
Optimization

Keywords

  • Surgery scheduling
  • Stochastic scheduling
  • Multiple machine scheduling
  • Earliness/Tardiness

Cite this

@article{3275b9afaf854201b017bc7bdba5ae7a,
title = "Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling",
abstract = "Early or tardy surgeries are frustrating for both patients and personnel, and cause inefficient use of resources at the operating rooms. The stochastic Earliness/Tardiness (E/T) scheduling problem addresses this by minimizing the total expected deviation of the surgery completion times from the planned completion times. We introduce the concept of E/T-concavity as a property of a probability distribution if the E/T costs are concave as a function of the standard deviation of the completion time, whenever the optimal planned completion times are selected. We use this concept to generate an optimal schedule for the multiple machine variant of the E/T problem. The optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the E/T objective. We demonstrate the usefulness of our results in practice by proving E/T-concavity for several probability distributions and by showing that, under the assumption of E/T-concavity, a simple Shortest Variance First (SVF) rule is optimal. We conclude by providing a numerical example of surgery scheduling where we demonstrate the benefits of the SVF rule compared to several commonly used scheduling rules.",
keywords = "Surgery scheduling, Stochastic scheduling, Multiple machine scheduling, Earliness/Tardiness",
author = "Maarten Otten and Aleida Braaksma and Richard Boucherie",
year = "2019",
month = "9",
day = "1",
doi = "10.1016/j.orhc.2019.100194",
language = "English",
volume = "22",
journal = "Operations research for health care",
issn = "2211-6923",
publisher = "Elsevier Science & Technology",

}

TY - JOUR

T1 - Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling

AU - Otten, Maarten

AU - Braaksma, Aleida

AU - Boucherie, Richard

PY - 2019/9/1

Y1 - 2019/9/1

N2 - Early or tardy surgeries are frustrating for both patients and personnel, and cause inefficient use of resources at the operating rooms. The stochastic Earliness/Tardiness (E/T) scheduling problem addresses this by minimizing the total expected deviation of the surgery completion times from the planned completion times. We introduce the concept of E/T-concavity as a property of a probability distribution if the E/T costs are concave as a function of the standard deviation of the completion time, whenever the optimal planned completion times are selected. We use this concept to generate an optimal schedule for the multiple machine variant of the E/T problem. The optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the E/T objective. We demonstrate the usefulness of our results in practice by proving E/T-concavity for several probability distributions and by showing that, under the assumption of E/T-concavity, a simple Shortest Variance First (SVF) rule is optimal. We conclude by providing a numerical example of surgery scheduling where we demonstrate the benefits of the SVF rule compared to several commonly used scheduling rules.

AB - Early or tardy surgeries are frustrating for both patients and personnel, and cause inefficient use of resources at the operating rooms. The stochastic Earliness/Tardiness (E/T) scheduling problem addresses this by minimizing the total expected deviation of the surgery completion times from the planned completion times. We introduce the concept of E/T-concavity as a property of a probability distribution if the E/T costs are concave as a function of the standard deviation of the completion time, whenever the optimal planned completion times are selected. We use this concept to generate an optimal schedule for the multiple machine variant of the E/T problem. The optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the E/T objective. We demonstrate the usefulness of our results in practice by proving E/T-concavity for several probability distributions and by showing that, under the assumption of E/T-concavity, a simple Shortest Variance First (SVF) rule is optimal. We conclude by providing a numerical example of surgery scheduling where we demonstrate the benefits of the SVF rule compared to several commonly used scheduling rules.

KW - Surgery scheduling

KW - Stochastic scheduling

KW - Multiple machine scheduling

KW - Earliness/Tardiness

U2 - 10.1016/j.orhc.2019.100194

DO - 10.1016/j.orhc.2019.100194

M3 - Article

VL - 22

JO - Operations research for health care

JF - Operations research for health care

SN - 2211-6923

M1 - 100194

ER -