Design question: Scheduling a Variable-timeslot Resource
I originally posted this in general java programming, because this seemed like a more high-level design descussion. But now I see some class design questions. Please excuse me if this thread does not belong here (this is my first time using the forum, save answering a couple questions).
Forum,
I am having trouble determining a data structure and applicable algorithm (actually, even more general than the data structure -- the general design to use) for holding a modifiable (but more heavily read/queried than updated), variable-timeslot schedule for a given resource. Here's the situation:
Let's, for explanation purposes, say we're scheduling a school. The school has many resources. A resource is anything that can be reserved for a given event: classroom, gym, basketball, teacher, janitor, etc.
Ok, so maybe the school deal isn't the best example. Let's assume, for the sake of explanation, that classes can be any amount of time in length: 50 minutes, 127 minutes, 4 hours, 3 seconds, etc.
Now, the school has a base operation schedule, e.g. they're open from 8am to 5pm MTWRF and 10am to 2pm on saturday and sunday. Events in the school can only occur during these times, obviously.
Then, each resource has its own base operation schedule, e.g. the gym is open from noon to 5pm MTWRF and noon to 2pm on sat. and sun. The default base operation schedule for any resource is the school which "owns" the resource.
But then there are exceptions to the base operation schedule. The school (and therefore all its resources) are closed on holidays. The gym is closed on the third friday of every month for maintenance, or something like that. There are also exceptions to the available schedule due to reservations. I've implemented reservations as exceptions with a different status code to simplify things a little bit: because the basic idea is that an exception is either an addition to or removal from the scheduleable times of that resource. Each exception (reservation, closed for maintenance, etc) can be an (effectively) unrestricted amount of time.
Ok, enough set up. Somehow I need to be able to "flatten" all this information into a schedule that I can display to the user, query against, and update.
The issue is complicated more by recurring events, but I think I have that handled already and can make a recurring event be transparent from the application point of view. I just need to figure out how to represent this.
This is my current idea, and I don't like it at all:
A TimeSlot object, holding a beginning date and ending date. A data structure that holds list of TimeSlot objects in order by date. I'd probably also hold an index of some sort that maps some constant span of time to a general area in the data structure where times around there can be found, so I avoid O(n) time searching for a given time to find whether or not it is open.
I don't like this idea, because it requires me to call getBeginningDate() and getEndDate() for every single time slot I search.
Anyone have any ideas?
[3112 byte] By [
mwardena] at [2007-9-28 12:55:40]
If I am correct, your requirement is to display a schedule, showing the occupancy of a resource (open/closed/used/free and other kind of information) on a time line.
I do not say that your design is incorrect. What I state below is strictly my views and should be treated that way.
I would not go by time-slot, instead, I would go by resource, for instance the gym, the class rooms (identified accordingly), the swimming pool etc. are all resources. Therefore (for the requirements you have specified), I would create a class, lets say "Resource" to represent all the resources. I would recommend two attributes at this stage ("name" & "identifier").
The primary attribute of interest in this case would be a date (starting at 00:00hrs and ending at 24:00hrs.), a span of 24hrs broken to the smallest unit of a minute (seconds really are not very practical here).
I would next encapsulate the availability factor, which represents the concept of availability in a class, for instance "AvailabilityStatus". The recommended attributes would be "date" and "status".
You have mentioned different status, for instance, available, booked, closed, under-maintainance etc. Each of these is a category. Let us say, numbered from 0 to n (where n<128).
The "date" attribute could be a java.util.Date object, representing a date. The "status", is byte array of 1440 elements (one element for each minute of the day). Each element of the byte array is populated by the number designation of the status (i.e, 0,1,2...n etc.), where the numbers represent the status of the minute.
The "Resource" class would carry an attribute of "resourceStatus", an ordered vector of "ResourceStatus" objects.
The object (all the objects) could be populated manually at any time, or the entire process could be automated (that is a separate area).
The problem of representation is over. You could add any number of resources as well as any number of status categories.
This is a simple solution, I do not address the issues of querying this information and rendering the actual schedule, which I believe is straight forward enough.
It is recognized that there are scope for optimizations/design rationalization here, however, this is a simple and effective enough solution.
regards
Ironluca@yahoo.com
Thanks for your thoughts. The problem with this solution is that it requires a large amount of memory space for a simple representation of availability. Not only that, but the extra space offers little value, as it is likely that timespans of a given status will be larger than a couple of minutes. In reality, there would probably only be about 10 events each day. My idea offers 10*2 space, while yours offers a constant 1440. See what I'm getting at?
The one advantage of your solution is accessing. Because each "time slot" is in a fixed position, I would be able to calculate the exact position of the beginning of a timeslot. Therefore, querying becomes much nicer. Even finding timeslots close to a requested time would be much much nicer. However, because of the granualarity of your solution, once I found the time, I would have to inspect every single index from bytearray[beginminute-1] to bytearray[endminute-1] and make sure its status for each is 'available'.
By the way, the problem set up is a subset of the whole application, obviously. I do have a separate Facility and Resource class. I'm just trying to figure out how to represent the scheduling part of it all.
