Programming: A Puzzle Worth Solving

Every year school coordinators around the globe have to make a duty roster. A teachers job doesn't end at the class room, they also take turns monitoring key areas of the school at key times to keep the students safe. A duty roster is a schedule of who is responsible for each area for each time slot that requires supervision.

Figure 1: A randomly selected duty roster schedule

Duty

Start

mon

tues

wed

thurs

fri

Morning Bus

Recess

Lunch

Library

Evening Bus

08:00

11:00

13:00

15:00

Barry

Kirstin

Barry

Kim

Barry

Brian

Bob

Kirstin

Kim

Barry

Kate

Bob

Barry

Kate

Kim

Brian

Kirstin

Bob

Kate

Kirstin

Bob

Brian

Kirstin

A randomly generated schedule like the one presented in figure 1 does not suffice. There are some obvious rules that need to be followed such as not giving too many duties to one particular person. Lets consider some simple rules to apply to a schedule.

Nobody should do more than one duty per day.
Nobody should do more than four duties per week.
Support staff do Morning Bus Duty and Library Duty.

We might choose to represent the data for this problem like this:

{:duties {"Morning Bus" {:start-time "08:00"}
          "Recess" {:start-time "11:00"}
          "Lunch" {:start-time "13:00"}
          "Library" {:start-time "13:00"}
          "Evening Bus" {:start-time "15:00"}}
 :people {"Kate" {:role "coordinator"}
          "Kim" {:role "teacher"}
          "Kirsten" {:role "teacher"}
          "Barry" {:role "teacher"}
          "Brian" {:role "support"}
          "Bob" {:role "support"}}
 :roles {"Support" {}
         "Teacher" {}
         "Coordinator" {}}
 :rules {"Match duty role" {:rule [:in [:people :role] [:duties :roles]]}
         "Duties per day" {:rule [:<= [:match :people :duties :day-of-week] 1]}
         "Total duties" {:rule [:<= [:match :people :duties] 4]}}}

So... how do we solve it?

I have built a UI for entering the data but I'm stuck on building the solver.
I have not found a constraint solver capable of solving this problem that runs in the browser.
Running a back-end is undesirable as this is a free, open source project with no budget.

I'm looking for ideas, references, examples, suggestions, collaborators or a mentor.
My preferences run to ClojureScript and JavaScript.

Can you help? There is a comments forum on this blog, or feel free to link to your favorite social site or email me directly timothypratley@gmail.com for discussion.

Pages

A Puzzle Worth Solving