Tuesday, March 3, 2015

1960’s Technology – Dining Room Table Scheduling

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