Dynamic job assignment: A column generation approach with an application to surgery allocation

Troels Martin Range*, Dawid Kozlowski, Niels Chr Petersen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

101 Downloads (Pure)


We consider the assignment of jobs to heterogeneous agents in a dynamic system with a rolling time horizon. An example is a hospital operating theatre where the jobs are surgeries and the agents are the surgeons. The paper is presented in the context of surgery allocation and the system is characterized as follows: Patients are grouped into categories and they arrive continually following a stochastic process. Patients in each group have specific time limits within which they need treatment and if it cannot be accommodated then the patients are outsourced. The service level is the percentage of patients in each group treated within the time limit. Surgery durations are stochastic and depend on the surgeon conducting the surgeries. Each surgeon has limited time available and expected overtime is penalized by a non-decreasing convex function. We develop a column generation approach for the assignment of already arrived patients and tentative future patients to surgeons on specific days. It balances the conflicting objectives of including as many arrived patients as possible within their time limits, maximizing the service level of future patients, and minimizing the expected overtime of surgeons. A computational study is conducted with the model embedded in a rolling time horizon frame. The study indicates that the assignment of patients based on our model increases system performance in terms of service level and reduced overtime compared to a First-Come-First-Served (FCFS) policy when the arrival rates of patients are medium to high compared to the capacity of the system.

Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number1
Pages (from-to)78-93
Publication statusPublished - 1. Jan 2019


  • Generalized assignment problem
  • OR in health services
  • Simulation
  • Stochastic knapsack problem
  • Surgery allocation


Dive into the research topics of 'Dynamic job assignment: A column generation approach with an application to surgery allocation'. Together they form a unique fingerprint.

Cite this