[CentralOH] Python Puzzler: Room scheduling

[Joe Shaw]

Hi,

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.

Joe

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
> 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?
>
>
>
> _______________________________________________
> CentralOH mailing list
> CentralOH at python.org
> https://mail.python.org/mailman/listinfo/centraloh
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20150528/2d2fa1c4/attachment.html>