Complexity results for the basic residency scheduling problem

Jiayi Guo, David R. Morrison, Sheldon H. Jacobson, Janet A. Jokela

Research output: Contribution to journalArticlepeer-review


Upon graduation from medical school, medical students join residency programs to complete their clinical training and fulfill specialty board certification requirements. During residency, they are assigned several years of clinical rotations, where they work under the supervision of physician faculty in a variety of different settings, to ensure that they gain the requisite training prior to beginning independent practice. These rotations typically last a short period of time, and the problem of determining a schedule for all the residents in a program can be quite tedious. In this paper, a basic residency scheduling problem that produces a 1-year schedule is defined, and a proof of NP-completeness is presented. Furthermore, a specific model of the residency scheduling program for the internal medicine residency program at the University of Illinois College of Medicine at Urbana-Champaign is studied. Finally, a method for determining alternate optima is presented.

Original languageEnglish (US)
Pages (from-to)211-223
Number of pages13
JournalJournal of Scheduling
Issue number3
StatePublished - Jun 2014


  • Alternate optima
  • Medical School
  • Residency program
  • Schedule perturbation

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Complexity results for the basic residency scheduling problem'. Together they form a unique fingerprint.

Cite this