7

I want to do something similar to Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). using Hopcroft-Karp Algorithm. But my additional requirement is that my time intervals are overlapping. Eg. The time slots can be 10am-11am or 10.15am to 11.15am. So if I choose 10am to 11 am slot, I don't want to choose 10.15 am to 11.15 am slot. Is it possible to achieve this without hitting the performance badly?

Community
  • 1
  • 1
HarshJain
  • 327
  • 1
  • 4
  • 12
  • I'm looking for this too using Constraint Programming. @hakank seems to be an expert in this! Closest I've got: http://stackoverflow.com/questions/20631657/constraint-programming-scheduling-speakers-in-shortest-time/20645601?noredirect=1#20645601 – Marcus Dec 19 '13 at 16:09

1 Answers1

1

You could use a flow algorithm similar to what your proposing with Hopcroft-Karp if you add another level distinguishing time slots with some sort of flow expander.

So you would have a source connected to the people, people connected to time slots, time slots connected to time breakdowns, and breakdowns connected to a sink.

To further describe the breakdowns, say you have time slots that start at 10:00, 10:15, 10:30 and 10:45. The time breakdowns would be at 15 minutes. If all meetings are an hour long then the 10:00 time slot would be connected to the 10:00-10:15 breakdown as well as the 10:15-10:30, 10:30-10:45 and 10:45-11:00 breakdowns.

There would have to be some modified logic at the connection between the time slots and the breakdowns. That is because their would have to be a change in flow values between the input of the time slots and the connections to the breakdowns. This is because whenever one person gets assigned to a time slot (time slot in-flow = 1) there are multiple flows to the breakdown (time slot out-flow = 4 per example above).

One disclaimer I haven't tried this. If you do please tell us if/how well it works.

wckd
  • 410
  • 2
  • 9