dgary@ecsvax.UUCP (D Gary Grady) (02/19/86)
The "arrangement puzzle" recently posted, requesting an algorithm for a
real-life problem, reminds me of a problem I ran into several years ago
and never solved in a completely satisfactory manner.
A group of surgeons needed to be assigned to emergency room duty with
the following constraints:
o Each assignment was for 24 hours (that is, one person would be on duty
Monday, another Tuesday, and so on).
o Whoever had the duty Friday was also stuck with Saturday and Sunday.
o Everyone was to work roughly the same number of weekdays (Mondays,
Tuesdays, Wednesdays, and Thursdays).
o Everyone was to work roughly the same number of weekends.
o Assignments were to be spread out as much as possible; no one was to
work consecutive days if at all possible, and the days between
assignments were to be as great as possible.
Now the hard part:
o Due to pre-set vacations, conferences, etc, physicians were often not
available for days or weeks at a stretch. Their assignments were to
be made more frequent in the times they WERE there to satisfy the
two equity criteria (roughly equal days and weekends worked).
I'll warn you from my own experience that this turns out to be harder
than it looks. Several simple-minded algorithms that sounded good
turned out to be flawed in practice. My final program worked, but still
produced imperfect results that had to be tinkered with by a human. (I
should admit that the real problem was even worse. A surgeon qualified
to perform a certain type of surgery needed to be on call. If the
physician on duty was so qualified, he or she fulfilled that need.
Otherwise one of the others had to be assigned that duty as well,
subject to the same requirements as listed before.)
Any strokes of brilliance?
--
D Gary Grady
Duke U Comp Center, Durham, NC 27706
(919) 684-3695
USENET: {seismo,decvax,ihnp4,akgua,etc.}!mcnc!ecsvax!dgary