Resource scheduling application

Question

I'm trying to implement an application that coordinates multiple users who are scheduling exclusive resources. The schedule data must maintain strong consistency over a network with a single master node. The scheduled resources could be anything from a conference room to a worker on a job site.

We assume the conference room cannot be scheduled for two meetings at once and a worker cannot be on two job sites at the same time. The business logic of the application must not allow a user to "overbook" a resource.

What I can't figure out is how to represent the data so that if two or more users operate on the schedule at the same time, and there are conflicts, one of the updates will abort.

The only solution I've seen so far is to track time slots for each exclusionary resource. So if the conference room is used on 5 min intervals, and it was scheduled for 9-9:30am, then the corresponding 5 minute time slots for 9-9:30am would all return TRUE, while the unscheduled slots would return FALSE or NULL. The DB transaction would then pull the conference room object out of the store, check all the time slots, and abort if the update conflicted with existing time slots.

However, this seems like it will get really big, really fast. Perhaps it could be garbage collected? Also, one of the goals of the design is to support variable granularity, so some objects will get scheduled on a minute to minute basis while others could be on a day to day basis, and this data design does not support that very well.

Currently, I am trying to implement this on Google App Engine using Python, but I would be really interested to see some more general solutions to this problem. All I've come up with Googling is scheduling recurring tasks, or algorithms that perform one time operations to automatically build optimized schedules.

Answer 1

You'll want to track just start and end times for each exclusionary resource. The data storage in your problem is actually the easy part - the hard(er) part is crafting queries to look for conflicts in time intervals.

If my logic is correct after being up for 21 hours, the following psuedo-code should check for meeting conflicts.

# Set up your proposed meeting
proposed.start = <thursday, 1pm>
proposed.end   = <thursday, 2pm>

# Look for meetings that intersect with or straddle proposed meeting
conflicts = <SELECT * FROM meeting WHERE
             meeting.start BETWEEN proposed.start AND proposed.end OR
             meeting.end   BETWEEN proposed.start AND proposed.end OR
             meeting.start <= proposed.start AND meeting.end >= proposed.end>


if conflicts.length > 0:
   # We have a conflict!

Answer 2

To automatically optimize a timetable of a school or university (or even other problems) take a look at the following Java tools:

TimeFinder, UniTime or Drools Solver

The problem with user interaction is not as easiely solved as you explained I think, because there could be other constraint violations as well (timetabling can get a lot more complicated).

First, I would only allow timetablers accessing/changing the timetable data.

Second, I would create an independent solution for each timetabler and then optimize this solution with the proposed tools above. The solutions then can be stored to the database and the timetabler could use them to further optimize the schedule or to compare to other solutions.