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
13:00
15:00
Barry
Kirstin
Barry
Barry
Kim
Barry
Brian
Bob
Kirstin
Kim
Barry
Kate
Bob
Barry
Kate
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.