[CentralOH] Python Puzzler: Room scheduling

[Eric Floehr]

How would you go about figuring out the best room schedule in Python? This
is a real optimization problem my wife's high school department has.

You have three classrooms: R1, R2, R3

The day is segmented into 7 periods. Each classroom can be used all 7
periods, or not.

There are 4 teachers. Each teacher needs to teach class for 5 periods, but
they can be any of the 7 periods of the day. Each teacher has one period
where they can't teach (listed), and one period where they won't have to
teach that can be any period of the day:

Ms. Anderson, can't teach period 6
Mr. Boxleitner, can't teach period 2
Ms. Chastain, can't teach period 7
Mr. Duchovny, can't teach period 3

Additionally, Ms. Chastain must teach in the same room for all 5 of her
class periods. The other three teachers can move rooms as necessary.

What is the "optimal" arrangement of teachers in rooms to meet these
constraints? "Optimal" means:

1. Fewest room changes, where a room change is defined as a teacher moving
from one room to another.  For example, if Ms. A seven period schedule is:
period 6 and 7 off, and period 1 in room 1, period 2 in room 2, period 3 in
room 2, period 4 in room 1 and period 5 in room 2, that is three total room
changes.

2. Lowest average room changes per teacher. I.e. 3 teachers moving once is
preferable to 1 teacher moving 3 times.

3. A room change with a break in between is preferable to an immediate room
change. A "break" is either the teacher's free period or their "can't
teach" period. For example, if Ms. A teaches in room 1 every period except
period 7 where she teaches in room 2, that's preferable to teaching period
1 in room 2 and then period 2 (and other periods) in room 1.

Beyond that, there is no "right" answer.

How do you go about providing "good" solutions in Python?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20150528/e2571467/attachment.html>