Learning project - not for production use
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Peer review scheduler in Prolog

Continuing my exploration of Prolog, I decided to write a program to generate a schedule for peer reviews.

Each week, each developer in the team is paired with a different developer. In an ideal world there would be a simple rotation - e.g. with 4 developers it might look like this:

  • Week 1: Dev 1 + Dev 2; Dev 3 + Dev 4
  • Week 2: Dev 1 + Dev 3; Dev 2 + Dev 4
  • Week 3: Dev 1 + Dev 4; Dev 2 + Dev 3
  • Repeat...

But in practice it isn't that simple - sometimes developers take holidays so aren't available for a week, and sometimes new people join or old ones leave.

This means we need to:

  1. Keep a record of historical pairings
  2. Attempt to pair developers who haven't worked together for the longest time
  3. Maximise the total time between pairings across all developers

I currently do this manually each week using a Google Sheets - but this is a Prolog script I created to do that.

(Warning: It's a bit rough around the edges! I probably won't use it in practice - it was just for practice - so I've not spent any time polishing it.)

This is what the output looks like:

6  [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,sam], [nick,vaiva]],
10 [[charnieze,-], [danny,izzy], [dave,fletcher], [heidi,pete], [matt,sam], [nick,vaiva]],
10 [[charnieze,heidi], [danny,pete], [dave,fletcher], [izzy,-], [matt,sam], [nick,vaiva]],
64 [[charnieze,fletcher], [danny,heidi], [dave,nick], [izzy,matt], [pete,vaiva], [sam,-]],
67 [[charnieze,izzy], [danny,-], [dave,nick], [fletcher,matt], [heidi,sam], [pete,vaiva]],
69 [[charnieze,izzy], [danny,heidi], [dave,nick], [fletcher,matt], [pete,vaiva], [sam,-]],

The lowest value is the same as the previous week (first item in the history list). The highest is the one that maximises the number of weeks between repeating pairs across all developers. Here is a copy of the history list, with those pairs converted to uppercase so they stand out:

    % Remember the top entries are the most recent here:
    [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,sam], [nick,vaiva]],
    [[charnieze,heidi], [danny,izzy], [dave,fletcher], [matt,nick], [pete,sam], [vaiva,-]],
    [[charnieze,-], [danny,pete], [heidi,izzy], [matt,vaiva], [nick,sam]],
    [[charnieze,danny], [dave,vaiva], [fletcher,-], [heidi,nick], [izzy,sam], [matt,pete]],
    [[charnieze,sam], [danny,matt], [dave,-], [fletcher,nick], [heidi,vaiva], [izzy,pete]],
    [[charnieze,vaiva], [danny,sam], [dave,matt], [fletcher,pete], [heidi,-], [izzy,nick]],
    [[charnieze,pete], [danny,dave], [fletcher,izzy], [heidi,matt], [nick,-], [sam,vaiva]],
    [[charnieze,nick], [danny,vaiva], [dave,heidi], [fletcher,sam], [izzy,matt]],
    [[charnieze,matt], [danny,nick], [dave,izzy], [fletcher,vaiva], [heidi,sam], [pete,-]],
    [[charnieze,fletcher], [DANNY,HEIDI], [dave,sam], [izzy,vaiva], [matt,-], [nick,pete]],
    [[CHARNIEZE,IZZY], [danny,-], [dave,pete], [fletcher,heidi], [matt,sam], [nick,vaiva]],
    [[charnieze,heidi], [danny,izzy], [DAVE,NICK], [FLETCHER,MATT], [PETE,VAIVA], [SAM,-]],
    [[charnieze,dave], [danny,fletcher], [heidi,pete], [izzy,-], [matt,vaiva], [nick,sam]],
    [[charnieze,danny], [dave,fletcher], [heidi,izzy], [matt,nick], [pete,sam], [vaiva,-]]

Note that [charnieze,heidi] and [danny,izzy] from the same row as the other four aren't selected because they also appear further up in the history, so they score less.

With 11 or 12 developers (6 pairs), the script takes 3 seconds to run. However, with 13 or 14 developers (7 pairs) it takes 47 seconds, and with 15 or more it fails completely:

ERROR: /home/dave/prolog/peer-reviews.pl:162: Initialization goal raised exception:
ERROR: Out of global stack

If I were to write it again, I would probably change the strategy - instead of generating all possible permutations for the week and then scoring them, I would accept the first result above a target score for each developer - e.g. "> 10 weeks ago". Prolog would then attempt to combine these into a valid week, and backtrack if that is not possible. It there are no possible permutations above that score, I would then reduce the target score by 1 week at a time.

Other improvements could include:

  • Read the staff list and history from CSV files or a database
  • Append the best result to the history automatically, or allow the user to choose
  • Additional scoring constraints - e.g.
    • Some developers like to be paired for 2 weeks at a time instead of 1 week
    • Some developers already work closely together, so don't need to be paired as often