A note on appointment scheduling with piecewise linear cost functions

Dongdong Ge, Guohua Wan, Zizhuo Wang, Jiawei Zhang

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We consider the problem of determining the optimal schedules for a given sequence of jobs on a single processor. The objective is to minimize the expected total cost incurred by job waiting and processor idling, where the job processing times are random variables. It is known in the prior literature that if the processing times are integers and the costs are linear functions satisfying a mild condition, then the problem can be solved in a polynomial number of expected cost evaluations. In this work, we extend the result to piecewise linear cost functions, which include many useful objective functions in practice. Our analysis explores the (hidden) dual network flow structure of the appointment scheduling problem and thus greatly simplifies that of prior work. We also find the number of samples needed to compute a near optimal solution when only some independent samples of processing times are known.

Original languageEnglish (US)
Pages (from-to)1244-1251
Number of pages8
JournalMathematics of Operations Research
Volume39
Issue number4
DOIs
StatePublished - Nov 1 2014

Keywords

  • Convex relaxation
  • Duality
  • Sampling
  • Scheduling
  • Stochastic programming

Fingerprint Dive into the research topics of 'A note on appointment scheduling with piecewise linear cost functions'. Together they form a unique fingerprint.

Cite this