Scheduling is the act of allocating tasks, resources and time to achieve specific goals. It’s widely applicable, from the simple act of filling one’s day with tasks to more complex acts of drawing school timetables, scheduling sports leagues, production systems etc. Though the problem can be stated simply, the ability to find good schedules is often a challenging task. Given the prevalence of these problems, appropriately, it has been a well studied area in Computer Science and Operations Research.
In various operational setting, scheduling quickly becomes very complicated due to scale (multiple but limited resources), complexity (variety of dependent steps), uncertainty (inability to estimate arrival and service times) or other factors (such as unexpected downtimes, weather etc.). Numerous examples of such systems can be found in production & manufacturing, repairs & maintenance and in service industries.
However complicated a system is, the simple goal of scheduling is to maximize the utilization of the limited resources and optimize system wide performance. Scheduling is seldom seen in isolation as it also involves a related query on deciding the quantity and quality of resources that need to be deployed. Though, in many operational settings, the decision of resources to be deployed is usually a given (for example in garment manufacturing, the number of seamsters, cutters, quality checkers etc.) and a planner’s task is to identify how best to deploy them to maximize production yield while respecting employment standards. Similarly in a service setting such as healthcare, with limited doctors and diagnostic equipment, the task is identifying how to assign appointment time to patients to ensure high quality of care while minimizing the possibility of wasted resources.
Scheduling can get very challenging when resources are limited and processes are complex.
Appointment booking in Clinics is particularly complex due to the varying behaviour of patients, which significantly impacts the flow of traffic within the facility. The planner must consider specific waiting limit requirements for future appointments and the potential following cases:
- Re-entry of patients into the hospital for further check-ups
- Walk-ins
- No-shows
- Varying movement of patients within a healthcare system
Patient Flows and possible variations of Behaviour in Healthcare Systems
Balancing these factors is crucial to prevent overburdening or underutilizing resources while maintaining quality of care and managing costs. Coordination involves not just allocating resources like consultation rooms, surgical theatres, MRI machines, and beds but also anticipating how the patient behaviour and return visits can affect overall traffic and efficiency.
To make the context specific, imagine an orthopaedic ward where patients require multiple visits to the consulting Physician for procedures such as X-rays, Scans or other diagnostics. Since return consultation should be respected (or even prioritised), it immediately affects the appointment times of patients in the queue. Waiting times at hospitals are particularly stressful for patients and it is desirable to minimize it whereas, No-shows and lateness lead to physician idleness and overtime, incurring substantial costs. How can hospitals effectively schedule appointments to balance these objectives, while factoring in the uncertainties such as consultation, durations, return visits etc.?
A common approach used in patient scheduling is using a fixed time-slot policy in which, the planner assigns patients at fixes intervals (say 10 mins). As illustrated below, the x-axis represents the nth patient and the y-axis represents the inter-arrival time or rather the amount of time allocated to each patient — 10 minutes. While this is intuitive and easy to implement, this method has its drawbacks: (i) if a consultation ends quickly, the doctor may have idle time, wasting valuable resources; (ii) if appointments run longer or patients return for follow-ups, it can cause delays and disrupt the schedule.
In A Fixed time-slot policy, patients are scheduled to arrive at equal intervals
In a Dome-shaped policy, the patients are scheduled with different time buffers based on their arrival sequence. Middle time slots are spread out more than the early and late slots.
A well known fix to the above issue is to follow a dome-shaped policy. As opposed to the fixed time-slot policy, here the inter-arrival times at the beginning and the end of scheduling period are tighter whereas more time buffer is afforded in the middle slots. This buffer time is important as it provides opportunity to absorb the delays (that occur due to some of the cases described before: no-shows, re-entry of patients, etc.) and prevent propagation to the later slots. However, determining the optimal gap or buffer time, which forms the ‘dome’, is tricky when dealing with complex set of uncertainties, variability in patient behaviour, and when dealing with re-entry scenarios.
In a recent paper “Intraday Scheduling with Patient Re-entries and Variability in Behaviours”, Zhou et al. present a state-of-the-art scheduling methodology that handles such complex uncertainties. They build on some of the recent work in the field of Robust Optimization called “Pipeline Queues” and demonstrate the applicability of this methodology in real world scenarios. The optimization model built under this paradigm shows computational tractability in addition to being easy to implement and experiments on datasets obtained from various clinics in Singapore shows an improvement in all metrics, such as patient waiting times (10-26%) and healthcare overtime, when compared to benchmark methods.
Efficient scheduling is crucial across plenty of industries. The challenge lies in managing time, resources, and uncertainties effectively. The Pipeline Queues is a promising methodology (as observed in the patient Appointment booking) with potential benefits for complex scheduling scenarios across diverse sectors.
