Simulated Annealing

[Jim Gill]

Hello Left Brainers - 

I have a solution that schedules 230 campers (we are a summer camp) into six activity periods each day.   There are several conditions that must occur for a class to be scheduled.  For example:  The class must be open, the camper must be in the appropriate grade, the class must have space -  and there are others as well.  When all the classes are scheduled there are always kids that have blanks where the scripting could not put a class in their schedule for various reasons.   

We are able to fill the blanks by manually looking at ALL the kids schedules and moving things around to allow everyone to have a full schedule.  Example:  Sylvie wants Ballet in Period 1 however their is no space; there is space in Period 4 however Sylvie is already scheduled into Play Rehearsal.  Jane is scheduled in Ballet Period 1 and has Tennis in Period 4 - Tennis is offered all day in every Period.  So we switch Jane's schedule so she has Tennis in Period 1 and now has Ballet in Period 4.  This opens a space for Sylvie in Period 1 so she can be scheduled into Ballet.  

There is an algorithm that does this as well called Simulated Annealing.   http://katrinaeg.com/simulated-annealing.html  I have a Schedule Rank (temperature) for each kid based on what they chose and what they received (see upper right of screenshot).    As humans, we are smart enough (for now) to see the solution and reason things out.  A script that can do it?

Each time I sit down to attempt this through scripting - I just don't know where to begin.   Has anyone else attempted a Simulated Annealing or anything similar.    Any help is appreciated!!

Best,

Jim Gill

[Fitch]

Thanks for the link, very interesting. It sounds like if you already have a "temperature" metric, you've done the hardest part, assuming the annealing algorithm is the method.

But yeah, this is a tough one.

[Jim Gill]

Thanks Fitch - yeah it is a tough one.  The only thing I have really come up with is running the same scheduling script multiple times and comparing the mean Rank (temperature) and selecting the higher value.  The order campers are scheduled is randomized each time (to be fair).  This would be random optimization of the schedule instead of optimizing the existing schedule.    There are coders for hire out there that specialize in Simulated Annealing but I have yet to find one that can help me with a FMP script.

I will get this eventually (or someone I hire will) - watch this space.

Jim

[Fitch]

Well sure, the concept of a looping script is simple enough, the tricky part is what happens inside that loop. I wouldn't think completely randomizing every camper's schedule for every iteration would be efficient.