6

I'm trying to figure out an algorithm for resolving appointment times.

I currently have a naive algorithm that pushes down conflicting appointments repeatedly, until there are no more appointments.

# The appointment list is always sorted on start time
appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 11:00 -> 12:30>,
   <Appointment: 13:00 -> 14:00>,
   <Appointment: 13:30 -> 14:30>,
]

Constraints are that appointments:

  • cannot be after 15:00
  • cannot be before 9:00

This is the naive algorithm

for i, app in enumerate(appointment_list):
    for possible_conflict in appointment_list[i+1:]:
        if possible_conflict.start < app.end:
           difference = app.end - possible_conflict.start
           possible_conflict.end   += difference
           possible_conflict.start += difference
        else:
           break

This results in the following resolution, which obviously breaks those constraints, and the last appointment will have to be pushed to the following day.

appointment_list = [
   <Appointment: 10:00 -> 12:00>,
   <Appointment: 12:00 -> 13:30>,
   <Appointment: 13:30 -> 14:30>,
   <Appointment: 14:30 -> 15:30>,
]

Obviously this is sub-optimal, It performs 3 appointment moves when the confict could have been resolved with one: if we were able to push the first appointment backwards, we could avoid moving all the subsequent appointments down.

I'm thinking that there should be a sort of edit-distance approach that would calculate the least number of appointments that should be moved in order to resolve the scheduling conflict, but I can't get the a handle on the methodology. Should it be breadth-first or depth first solution search. When do I know if the solution is "good enough"?

closed as too broad by Robert Harvey Apr 17 at 22:09

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • What is the quantity you want to optimize given the non-overlapping and 9 to 15 constraints? Without a formal definition of it, you can't show that your approach is not optimal/is optimal. – Patrick Oct 31 '13 at 6:41
  • I'm sorry I should have been explicit, I should I want to be able to resolve all conflicts with the minimal number of rebookings (Appointment moves). – Thomas Oct 31 '13 at 6:59
  • 1
    "Minimal number of rebookings" is a metric, not an algorithm (although a very sensible one). For such combinatorial problems, there is often no efficient algorithm (in fact, many are NP-complete). But this one doesn't look quite so terrible in practice; try checking all one-move solutions first, then all two-move solutions, etc. – Kilian Foth Oct 31 '13 at 8:12
  • @KilianFoth: Patrick asked what quantity I wanted to optimise. You are right though, Minimal number of rebookings is not an algorithm. It is a metric that I would use to evaluate a potential algorithm's performance. – Thomas Oct 31 '13 at 12:42
  • I think that a good metric in your case would be a pair <numberOfShifts (Priority1), totalAmountOfUnusedTime(Priority2)>. You want both to go as much down as possible. The everything else is about making a decision of whether to keep, or to shift to some other time. To me it looks like a variation of Knapsack problem (Dynamic programming). – user181706 May 28 '15 at 18:23
1

This is a classic problem to be solved with a schedule algorithm, many PHd and research papers have been written about this sort of problem. Therefore it is impossible to provide a short answer and a long answer would cost you days of my time.

Firstly check how many possible options of appointments you have, if that is reasonable low, you could use back tracking to look at all options and choose the best. Otherwise expect to spend weeks reading up on the research, unless you get lucky. Start with reading up on Constraint satisfaction

It only takes a small limitation like "appoints are not moved to different days" to change a very hard problem, into something you can solve by looking at all possible outcomes. Therefore how you define your problem is very important.

See the "Algorithm for creating a school timetable" question for lots of pointer, also have a look at optaplanner as it is open source and can be setup to solve most constraint satisfaction problems.

0

I am not sure I understood your problem (if at all) and/or your desired type of solution, but...

I'd start by sorting and reassigning on appointment lengths, instead of start time.

For instance, let's consider another "even worse" scenario of overlapping;

same as in your example, but for the last appointment, that we'll make 2 hour-long instead:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 11:00 -> 12:30 (1.5 hour-long)
Appointment #3: 13:00 -> 14:00 (1 hour-long)
Appointment #4: 13:30 -> 15:30 (2 hour-long)

First, let's reassign on (decreasing) lengths, instead of start times:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)
Appointment #4: 13:00 -> 14:00 (1 hour-long)

Next, let's go back to the constraints (where the largest time frame allowed is from 9:00 to 15:00 anyway).

Already, we know that we won't be able to fit 6.5 hours of appointments in only 6 hours total.

So, we can "drop" (i.e., push to next day) appointment #4.

We're left with:

Appointment #1: 10:00 -> 12:00 (2 hour-long)
Appointment #2: 13:30 -> 15:30 (2 hour-long)
Appointment #3: 11:00 -> 12:30 (1.5 hour-long)

So, finally, we can reschedule by putting the first appointment at the start of that time frame, and enqueuing the others (with or without gaps, as long as we don't go past 15:00)...

Appointment #1: 10:00 -> 12:00 (2 hour-long) => move to 9:00 -> 11:00
Appointment #2: 13:30 -> 15:30 (2 hour-long) => move after appointment #1
Appointment #3: 11:00 -> 12:30 (1.5 hour-long) => move after appointment #2

To end up with:

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:00 -> 14:30

or, why not,

Appointment #1: 9:00 -> 11:00
Appointment #2: 11:00 -> 13:00
Appointment #3: 13:30 -> 15:00

'HTH,

0

Here it really depends whether you are looking for a good enough solution or really an optimal solution.

In case you really want to find the optimal solution you can consider modelling your problem as a mixed integer programming (MIP) problem or as a constraint programming (CP) problem.

If you go for the MIP approach you probably want to add a binary variable for each appointment indicating if an appointment is moved or not. For every appointment you can associate a second linear variable indicating by how much an appointment is moved. For every appointment add a constraint stating that the linear variable indicating by how much the appointment is moved can only be non-zero if the associated binary variable is positive. For every appointment pairs add a binary variable indicating if the first appointment is before the second one. Then for every appointment pair add two constraint using the aforementioned binary variable to forbid appointments to overlap. Your objective function is then to minimise the sum of the binary variables indicating if an appointment is moved.

If you are looking for a more heuristic approach, here would be a way to tackle the problem: As long as there are overlapping appointments select the appointment overlapping with the largest number of appointments and move it to a position were it does not overlap with any appointment. Repeat the process as long as there are overlapping appointments.

Not the answer you're looking for? Browse other questions tagged or ask your own question.