2

I am having a bit of trouble designing a new feature at the moment. It is part of a resource management system. I was wondering if anyone has experience doing anything similar.

I'll try to explain:

Resource: a Person, Place, or Thing

Availability Template (AT): allows you to define a standard availability pattern for a type of resource. e.g.: Mon-Fri 9-5.

Resource Additional Availability (AA): allows you to define one-off availability for a resource. e.g.: Bob's overtime 10-3 on Saturdays.

Resource Availability Exclusions (AE): allows you to define when a resource is not available. e.g: Room 4 is cleaned between 4-5 on Fridays.

It's easy enough to check whether or not a resource is available at a point in time: Availability = (AT(rID, time) || AA(rID, time)) && !AE(rID, time).

But I need to be able to query a resource's availability over a time period. i.e.: "Is Room 4 available at 9am for 2 hours on Thursday?".

So far, I have created an algorithm that "samples" the availability at a specific interval over the time period. However, this means that the returned availability lags the actual availability and some information might be missed.

E.g.: if I sample the availability every 15 minutes between 9 and 11, it would miss an exclusion between 9:05 and 9:10.

I could use a very small sampling period (eg: 1 minute) but that might not be performant and overall it is still quite an ugly brute-force approach.

Are there any standard patterns or algorithms for this type of problem?

Improve this question
4
  • I suspect the simplest and most pragmatic answer is to use multiple sampling periods, i.e. start by looking at rules which apply to any of the days in the desired interval, then the hours in the interval, and so on until you either run out of rules or hit intervals of one minute and can confirm the possible matches are actual matches (I'm assuming you already have a minimum period such as one minute or one second somewhere in your app, since defining availability to nanosecond precision would be a bit pointless).
    – Ixrec
    Jan 14, 2016 at 15:50
  • @lxrec that's an interesting idea. But it's still based on the same pattern, and there are still arbitrary values and limits (e.g.: should 1 minute be the minimum, or 2, or 5?). It just smells a bit, if you know what I mean. I was thinking there should be standard ERP algorithms for this type of problem, or a mathematical algorithm where I could "union" all the availabilities. I will think about your suggestion...
    – Kev
    Jan 14, 2016 at 16:09
  • Related? Nurse Scheduling Problem
    – Dan Pichelman
    Jan 14, 2016 at 16:44
  • @DanPichelman: that is a problem which is at least 100 times harder than what the OP is asking for.
    – Doc Brown
    Jan 14, 2016 at 16:57

1 Answer 1

Reset to default
6

First, reduce the problem to a test of availabilities "per day". All your examples are using ranges for only one day, but if you also want to support a range like "Monday 10:00 to Wednesday 14:00", break this down into three tests for "Monday 10:00 to 23:59", "Thursday 00:00 to 23:59" and "Wednesday 00:00 to 10:00".

For each day, store an interval representation of the available times in form of a list of intervals. Initially, the list contains only one interval, lets say [9:00 , 17:00] for each day, and whenever a part of the day gets blocked for an different interval, (for example, room gets blocked from 10:00 to 11:25), you calculate the new resulting list of intervals (here [9:00,10:00], [11:25, 17:00]). Additional availability leads to additional intervals for some dates, and the "availability check" is nothing but an overlapping test of one new interval with all "available time" intervals of a specific day.

So in terms of sets, all you need is a "subtraction" operation on intervals, a "union" operation, and an overlapping test.

The implementation of the overlapping test for two intervals is not hard, it does not require any "sampling", just comparing the minimum and maximum values of each interval. See here for an example. Creating interval unions, or "subtraction" of intervals is not too complicated, too, see here, note that the "set difference" of two intervals yields either two new intervals, one new interval or zero intervals . At the second link, you will also find a reference to an interval package in Python. I guess there are similar components or code snippets available for each major programming language, if you don't want to implement this on your own.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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