[CentralOH] Python Puzzler: Room scheduling
joe at joeshaw.org
Thu May 28 22:20:47 CEST 2015
At first blush this looks a bit like a graph or tree problem to me. The
way I would go about modeling this is that each period change would be a
node on the tree and would incur a penalty score of some sort. Moving a
teacher might incur a penalty of 1, for instance. Maybe that number
increases exponentially as the teacher is subsequently moved, in order to
satisfy condition #2. Completely disallowed moves would incur a huge
penalty (say, 1000 whereas other penalties are in the 1-10 range) like Ms.
Anderson being assigned to teach period 6 or Ms. Chastain being moved to
other rooms. A score of 0 is the optimal (but maybe impossible) result
with this scoring heuristic.
If you do depth first search you can then completely prune branches of the
tree as soon as they incur a penalty greater than the best path seen so
far. You could also prune with a breadth first search but then you have to
track more state as you go along.
On Thu, May 28, 2015 at 4:05 PM Eric Floehr <eric at intellovations.com> wrote:
> 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
> 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?
> CentralOH mailing list
> CentralOH at python.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the CentralOH