My
previous blog post was about scheduling classes at a major university. I’d now like to relate a much small
scheduling problem that I had the opportunity to be involved in.
A
man in my parent’s church in Waterbury, Connecticut, Mr. Ranft, was the
headmaster of a small private boy’s school in that city, McTernan. The student population, all of whom boarded,
was about 150 students. Knowing that I
was majoring in computer science, Mr. Ranft asked if I could help with a
scheduling problem that they were having.
The problem was related to their dining room.
All
the boys and the resident faculty had dinner together in the school’s dining
room. There was a faculty member at the
head of each table and they desired that all the boys periodically rotate (about
once a month) among the tables so each faculty member could get to know each
boy during the course of the year. But
they wanted these rotations to be assigned and not left up to the boys. So one of the constraints is that they did
not want two boys to be at the same table in consecutive rotations. They also wanted each boy to be at the
headmaster’s table at least once during the year. And a complicating factor was that not all
the tables were the same size, for example, the headmaster’s table seated more
boys than any of the other tables.
They
had not figured a good way to do this scheduling and their manual efforts were
not working well and were very time-consuming.
Mr. Ranft wondered if a computer could do a better job. I agreed to take on the challenge. I approached this as follows:
Rotation
one – I assigned each of the 150 boys a random number (using the random number
generator on the computer – in FORTRAN).
I then sorted the boys (actually just the numbers 1-150, I didn’t need
to know their names) by that random number, put the first N1 at table 1, the
next N2 at table 2, etc. (N1, N2, etc. just being the number of seats at that
table).
Next
rotations – Again, I just picked up with the next set of random numbers, and
did the same thing, the lowest N random numbers went to table 1, then table 2,
etc.
While
the above did a good job of making sure that the assignments were random, and
that no one could choose where to go next, I then did some manual checking to
see if the random numbers resulted in any breaking of the “rules”. For example, if anyone had not been assigned
to the headmaster’s table during the year I would look for someone who was at
the headmaster’s table that rotation but was also there at least one other
rotation and make a manual change to switch the two boys.
I
then printed out a chart with 150 spaces for the 150 boys and each boy’s table
assignments for each of the monthly rotations.
I left it to the school to fill in the names of the boys on the
chart. Mr. Ranft was very pleased with
the results I had put together. He
retired to Florida a few years later, so I never had any follow-up on how
things had worked out. But I was pleased
that I could use my knowledge of computers to solve what he had viewed as a
very difficult problem.
No comments:
Post a Comment