[CentralOH] Python Puzzler: Room scheduling

[Len Jaffe]

I agree that it's a graph traversal model, but IMO you model rooms as
nodes, and period changes are edges, with a room change having a cost of 1
and no-change having a cost of 0.

I think that given the relatively small number of permutations of teachers
in classrooms vs cheap computing power, you could generate the graph entire
state space first.   Also a second set of weights is recorded with total
changes by teacher.

The "fewest total room changes" is then the minimal spanning tree of the
graph.

If each edge records room changes, by teacher, then the "fewest total room
changes" is then the minimal spanning tree of the graph using the sum of
the individual teacher-room-changes for weight, and the "lowest average
room changes per teacher" is simply computing averages on the second set of
states, and then sorting.

This brings back fond college AI memories of writing lisp to solve one of
those 9-tile numbered square puzzles with 8 numbered tiles and one empty
space.  Good times.




On Thu, May 28, 2015 at 4:20 PM, Joe Shaw <joe at joeshaw.org> wrote:

> 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
>>
>
> _______________________________________________
> CentralOH mailing list
> CentralOH at python.org
> https://mail.python.org/mailman/listinfo/centraloh
>
>


-- 
Len Jaffe - Information Technology Smoke Jumper - lenjaffe at jaffesystems.com
614-404-4214    @LenJaffe <https://www.twitter.com/lenJaffe>
www.lenjaffe.com
Host of Code Jam Columbus <http://www.meetup.com/techlifecolumbus/>  -
@CodeJamCMH <https://www.twitter.com/CodeJamCMH>
Curator of Advent Planet <http://www.lenjaffe.com/AdventPlanet/> - An
Aggregation of Online Advent Calendars.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/centraloh/attachments/20150528/8e112dd6/attachment-0001.html>