I’m writing a semi-automatic scheduling application. Given some existing bookings and some resource requirements, it needs to find the times at which a new event can be scheduled. A human user will then evaluate the results and choose one of the options. It does not need to optimise a timetable for multiple events and hence it is not the usual NP-Hard timetabling problem.
The system has a number of resources (trainers, rooms, equipment) each of which has a type (e.g. French teacher, seminar room, projector…). Resources are booked for events each of which has a start and end time.
Now, say I need to schedule a 2 hour long French class using a projector in a seminar room, what are the times that at least one resource of each required resource type is available?
In order to limit the problem space, it’s acceptable to consider only 9am-5pm, Mon-Fri at 15 minute intervals for the next 90 days. Total number of resources in of the order of 1000.
How can I do this without having to compare every resource with every other resource?
2
I would try to use a one dimensional sweep-line algorithm for this. First, for each resource part of a booking, find out the points in time where its status switches from “available” to “booked”, or vice versa (restricted, for example, for every point in time after now). You put each of this points in time into a data record containing
- time stamp
- kind of status switch (to “booked” or “available”)
- reference to the resource
Make one list of all of those records and sort it by time stamp. Next, you create a boolean array with a flag “available” for each of the resources, initialize it with the current availability status. Finally, the “sweep” takes place: walk through the sorted list from one record to the next, change the availability state in your boolean array of the related resource, until each of the flags have the state “available”. Move one record further and get the time stamp, this will tell you how long the resources are all available within a contiguous time interval (you may take care for not crossing day boundaries here). If the time span is long enough, you found a solution in form of a time interval. You continue this until your reach the end of the list or your have enough intervals found.
As a bonus, this works fine with or without the “15 minute” and “90 days” constraints.
2
One presumes you have three tables – trainers, rooms, equipment. You have a ‘blocksize’ of 2 hours. So the first temporary result set you generate (in this case for trainers) lists the available trainers and their block starting times, where only those that have at least two hours available are included. You create another result set for rooms, and another for equipment. At this point you merge the available times of all three categories into one list and assign each interval an identity, therefore day 1 hour 1 is 1, day 1 hour 2.5 is 2, day 3 hour 3.25 is 3, etc. You have one (combined) list of all times available in all categories. These IDs get updated back into the respective intermediate sets. Thus the first time slot available for a room might be 2, the first for a trainer might be 5, and the first for equipment might be 7. Now you query on the set of all records where ‘trainertimeid = roomtimeid and trainertimeid = equipmenttimeid’. What is returned is the set of all records where availability is found in all three categories.
1