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.


11 comments:

  1. You would also need a rule cannot have library and lunch on same day? (Time conflict)

    When you say "Support staff do Morning Bus Duty and Library Duty." do you mean that other roles cannot do those jobs, or that Support staff cannot do other jobs? It's unclear.

    ReplyDelete
    Replies
    1. Hi Josh, thank you for the comments and suggestions. Regarding the time conflict; yes good point, a person can only be in one place at a time. The "Support staff do Morning Bus Duty and Library Duty" I interpret to mean "Morning Bus Duty and Library Duty will have support staff assigned to them" but that support staff can still do other duties. Also I would guess that teachers *can* do those duties in a pinch and that this is a weaker constraint than the two places at once rule.

      Delete
    2. actually the one job per day rule ought to be sufficient. It reminds me of a more complicated version of the chess960 setup.. https://gist.github.com/jreighley/6aa4505fa2048360a64fa7cef6e593d6

      Delete
  2. My inclination would be to make your rules into clojure.spec Then Take 4 instances of the list of staff and shuffle. Make a list of the 20 available jobs. draw the first name off the suffled staff list and link each drawn name into the first job in the list that they conform to the specs for.

    Probably not efficient, but prototype effective. Perhaps it would crash sometimes, but you could always just start the process again until you had a valid answer.

    ReplyDelete
    Replies
    1. Hi Josh, following this approach works great!
      I have a proof of concept here:
      http://timothypratley.github.io/leaderboardx/#/roster
      code is here:
      https://github.com/timothypratley/leaderboardx/blob/master/src/algopop/leaderboardx/app/views/roster.cljs

      I'm going to throw more rules at it and more data to see how it handles that.

      Delete
  3. is core.logic unsuitable?

    ReplyDelete
    Replies
    1. I think it might be unsuitable for solving the problem in the browser because core.logic does not seem to have the finite domain code ported to ClojureScript. I think this is a finite domain problem and can't be solved with the primitives currently implement in ClojureScript... which means I'd have to run a server. That might also be a good approach if it provides a significant advantage.

      Delete
  4. You can do this with core.logic. Throw away that data representation though; it will not be useful.

    ReplyDelete
    Replies
    1. Hi Richard, thanks for the input.

      Delete
  5. I received an email suggesting jusCSP as a possible candidate for solving the schedule.

    I set up a basic problem for jusCSP http://prajitr.github.io/jusCSP/ to solve, and the short answer is that it is surprisingly slow.

    To see what I mean you can go to:
    http://timothypratley.github.io/leaderboardx/#/roster

    There is a load button on the right; load the Example dataset.
    Now if you click "Randomize" it will try random shuffles until it finds a solution that matches roles pretty quickly.
    If you click "Randomize (CSP)" it will use jusCSP to solve with only the constraint that there is 1 duty per person per day...
    and it takes more than 5 seconds for me. This is not an unreasonable amount of time, but at this stage I'm worried that
    it is so much worse than the shuffler+random tries.

    The code setting up the constraint problem is here: https://github.com/timothypratley/leaderboardx/blob/master/src/algopop/leaderboardx/app/views/roster.cljs#L144

    I looked into the alternate library noted: https://github.com/njoubert/csp.js
    But it has no instructions on how to build/install/use or run the examples.
    Looking at the examples the HTML file includes "require.js" and that's all... which doesn't seem like a valid option for me to use it.
    In the commit message of the sudoku example it says "a simple sudoku example but too big for the current system to easily"
    which makes me think it wont be able to handle my grid either.

    ReplyDelete
  6. Continue the good work; keep posting more n more n more.
    c++ programming

    ReplyDelete