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
- who is being relieved by the shift owner and who is the relief at the end of the shift, and
- 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:
- 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)
- 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.