Need help with an appointment scheduling problem

Question

I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could help me. The problem regards the process of scheduling a date and hour for each patient appointment over a week, each patient has to come in do a first visit and then a transfusion, we have N beds for transfusion, thus if they are all occupied at a certain moment we have to consider a certain waiting time for the patient. I am stuck on writing the constraints for my problem. I have as data:

• P --> List of patients
• K --> List of pathologies
• L --> List of laboratories
• T --> Time horizon in days
• H --> List of time slots for each day
• Ms --> Maximum ending time for transfusions
• Mv --> Maximum ending time for visits
• N --> Total number of beds for transfusions
• t^(v)(k) --> time for first visit pathology k
• t^(s)(k) --> time for transfusion pathology k
• S(p,k) --> 1 if patient p has pathology k, 0 otherwise (every patient has only one pathology)
• W(l,k,t) --> 1 if laboratory l is designed for visits of pathology k on day t, 0 otherwise

I was thinking about using as variables:

• X(p,t,h) --> 1 if patient p begins visit on day t on time slot h, 0 otherwise
• Y(p,t,h) --> 1 if patient p begins drug transfusion on day t on time slot h, 0 otherwise
• R(p) --> Waiting time of patient p between visit and infusion
• U(p) --> 1 if patient p has to wait between visit and infusion, 0 otherwise
• C(p) --> Total time spent in the hospital for patient p

Do you guys think these variables are enough ? We work under the assumption that nurses are always available, and thus we do not consider that as a constraint. How would you write the model ? I need serious help and would be extremely helpful to anyone wanting to help...

The constraints on top of the question are what I came up with, I am not sure if they are all necessary or not. It may be possible to solve the problem using less constraints. What do you guys think ? Any feedback is appreciated it is one of my first experiences writing such a big model.

Answer 1

Assorted comments in no particular order:

• Are you using "infusion" and "transfusion" interchangeably?
• I suspect that, in order to handle the occupancy constraints for transfusion beds, you will need a variable for the time each patient starts transfusion. You may be able to compute that from X(p,t,h) and W(p), but it might be easier to start with an explicit variable for transfusion start time and compute W from that variable and X.
• It is unclear what role the laboratory index (l, from set L) plays. If there are multiple laboratories set up for different pathologies on a given day, then you need bed capacity N(l) for each lab, not just one total bed capacity N.
• You are going to need an objective function, which means you need to settle on a criterion for choosing among possible schedules. (By "you" I mean "whoever is commissioning the model".) This could be maximizing the number of patients seen per day, minimizing waiting times for appointments, minimizing cycle times (time from when the patient walks in to when they walk out) or possibly something else. The objective criterion may dictate the need for additional variables. By the same token, depending on the criterion, either or both of U(p) and C(p) may be unnecessary.
• ADDENDUM (I forgot to include this the first time around): You may need a parameter for the time to "refresh" a bed (change bed linen, change IVs, sterilize anything that can't outrun you) and constraints to enforce that. In scheduling problems that's known as a "setup time" or "changeover time". Similarly, there is probably a capacity limit on "first visits" (perhaps staff need to go over paperwork, or doctors need to examine the patients), and there may be a minimum time gap between first visits (staff require time to regroup between patients, examining rooms need to be sterilized, ...).