current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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?

share|improve this question
1  
I've done this with fairly simple SQL Select statements. It works very well, provided you don't get into the NP-hard aspect. Just put the conditions you want into the WHERE clause. –  Robert Harvey Dec 23 '13 at 22:46
    
Thanks. Could you elaborate? I can't see how to formulate this in SQL. –  Tamlyn Dec 24 '13 at 16:50

2 Answers 2

up vote 2 down vote

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.

share|improve this answer
    
Interesting. Since bookings tend to start on the hour and there are many resources, the modal time between sorted intervals is likely to be zero. But rather than a Boolean array of availability, I could store the time that the resource became available and three statuses: "booked", "available" and "available for more than [2 hours]". As soon as I have a resource of each type in the third status, I have a match. Complexity is then O(n*m) where n is number of resources and m is number of bookings. –  Tamlyn Dec 24 '13 at 17:12
    
@Tamlyn: records with the same time stamp should be processed at once, of course, so only non-zero time intervals are left over. The availability time for a specific resource can be easily determined from the sorted list, without the need of storing redundant information, so I would consider your suggestion as premature optimization - not wrong, but unnecessary complicating things. You should do this only when you notice real performance problems after implementing the solution without the additional "availability time". –  Doc Brown Dec 24 '13 at 19:07
up vote 0 down vote

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.

share|improve this answer
    
I don't really understand. What does a result set look like, how are sets merged together and how are intervals numbered? –  Tamlyn Dec 24 '13 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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