Algorithm to display a schedule calendar with specific constraints
April 12, 2007 2:18 AM   Subscribe

I've charged with adding a feature to a shift scheduler / coverage requestor that displays shift information for a given week. I've been able to display them so as to satisfy the constraints I've been given, but it's got me wondering wondering if there's a more rigorous/mathematical approach to the general problem of organizing the display of any such calendar information.

The shifts in question are for employees (consultants) at a college computer lab, and all begin either 0, 15, 30, or 45 minutes past the hour. This weekly schedule calendar will be used for consultants to see their own shifts and to view shifts which are available for coverage. Let's say a consultant is looking at a shift as the current or prospective owner of it. For me, I'd say the pertinent information is
  1. who is being relieved by the shift owner and who is the relief at the end of the shift, and
  2. who are the people with whom the shift owner is going to be working
This places two constraints on the display so that the above information is most readily communicated:
  1. Contiguous shifts should not be in seperate columns (unless one person is being relieved by more than one other person or vice-versa) (i.e. temporally contiguous shifts should be vertically contiguous)
  2. Concurrent shifts should not be seperated by unnecessary blank spaces (i.e. temporally concurrent shifts should be horizontally contiguous)
It's trivial to create an algorithm that satisfied the first condition (which seems most important to me). The problem is, I can't figure out whether it's possible to create an algorithm that guarantees that neither constraint will ever be violated. I haven't run into any examples so far where it's obviously impossible, but I don't doubt that they might exist.

If the second condition can't always be satisfied, how might an optimal algorithm be constructed such that it is always satisfied whenever possible? I'd be very interested into any pointers on how to frame this in a more theoretical manner (for instance, a graph theoretical approach).

Lest I be called out for this, I'd like to say that I'm not asking metafilter to do my job for me. I've already written code that is fine by my superiors, but it got me to wondering whether there isn't a better way to do it. My current approach starts off by finding contiguous shifts that are necessarily joined together (that is, one person relieves one other person). It then goes through the shifts (ordered first by start-time, then length of shift or block-of-contiguous-shifts) and moves them as far to the left as possible. After that it does some hackish rearrangements which seem to give satisfactory results. Here are links to the results of my crack at the problem: 1 2. Like I said though, I'm interested in the more general cases than in the practical one that I've had to deal with here.
posted by Frankieist to Computers & Internet (3 answers total) 2 users marked this as a favorite
It seems to me that provided that there are always the same number of rows in your table and that they always represent the same time slots, constraint 2 is guaranteed to be satisfied.
posted by benign at 5:41 AM on April 12, 2007

Response by poster: benign: time slots vary from semester to semester, and are different at each campus location. I'm interested though in how one would do this with any arbitrary schedule information. I can't find any calendaring applications that do this gracefully (iCal doesn't need to display it in columns, and phpicalendar looks awful).
posted by Frankieist at 5:51 AM on April 12, 2007

Response by poster: err, that should be phpicalendar looks awful when trying to display complex and concurrent schedule information.
posted by Frankieist at 5:52 AM on April 12, 2007

« Older The rose petals on the bed weren't necessary, but...   |   I do not trust my judgement Newer »
This thread is closed to new comments.