Missing Massages: My Second BootCamp Project

Introducing indifference to appointment scheduling

Posted by mh on Nov 1, 2017

Brief context setting: due to some inconvenient timing, I spent the first few days of the second bootcamp project in northern Minnesota, away from my computer and the internet. By the time I returned to SF, the other groups had made enough progress that I didn't want to jump in and disrupt their flows, so I attempted to take on the project on my own. Thus began one of the longer weeks of my life. The silver lining is there were no failed merges.

My second project, the Indifference Optimizer, was selected to solve one particularly irksome (though tiny) problem in my life. At CK, we have chair massages (and other timeslot-based signups) about 2-3 times per year*, and other similar events more frequently (trainings, CKU classes). Typically, events like that have limited availability, and so there are multiple ways to "fairly" assign those timeslots.

The first is to assign slots randomly. This works when everybody is doing the event at the same time (like biking across the Golden Gate Bridge, or a Bocce tournament), but fails when people need to sign up for specific timeslots.

The second, which is currently used at CK, is a first-come-first-served process. While I typically have no issue with the fairness of this option, we would send out sign-up lists in the middle of the day, which would reward those people who were not buried in work, and had the ability to check email as it came in. Ironically, this ensured we awarded the massages to those people who needed them least (though I suppose "needed" is always going to be relative).

Another way is to select interested people in a random order, and have them choose from an available timeslot. This would work, but requires people to be relatively attentive and available for their selection time, which could drag the process out forever.

A slightly more technologically-advanced method would be having each person rank their preferences, then cycle through and give them their top remaining slot. In retrospect, given my time constraints, I should have stopped here.

Taking this one step further introduces the concept of "indifference". It attempts to solve the issue that if person A and person C can make any time after noon, and person B can only make a 1 pm appointment, it is a more optimal solution to put person B in the 1 pm slot, even if they chose after person A or C.

Indifference Optimizer

Simple concept, right? Turns out it gets a little tricky: I had to build an algorithm that queued users and reserved spots (though didn't assign them), but knew when and how to assign those queued users into the reserved slots and then move down the list.

Thankfully, with the help of my fearless instructor (Jayson Phillips), we learned that the hieuristic to trigger the assignment phase is actually quite simple: choose users in a random order, and build an array of queued users and reserved slots (slots which are (tied for) top remaining priority for a queued user). As soon as # reserved slots = # queued users, trigger the assignment phase, as you can run this with no regrets.

For a brief example, think of if the first user has only one choice. You know he/she will always take that slot, so you can assign it. For n=2, if you have two users (1, 2) that have top preferences of ([a,b],[b]), respectively, after looking through user 1, you'll have 1 queued user (#1), and two reserved slots ([a,b]). Once you go through user 2, you'll have 2 queued users, and still two reserved slots, so you should assign them.

Needless to say, after solving the "hard" part, I got caught up with the assignment step. Mind you, this was Thursday night, with the project being due Saturday morning (and having no routing on the front end, etc.). I worked out many examples on paper, but was unable to come up with an elegant algorithm that solved the assignment issue (start with users with 1 choice, eliminate that choice, repeat).

So, I "cheated". I saw some similarities between what I was trying to codify and Sudoku, so while researching Sudoku solutions, I chanced upon a helpful article about depth-first tree search. My implementation simply brute forces the answer, which is very inelegant.

Once those queued users were assigned to those reserved slots, I nuked the reserved slots from the remaining users, removed any users that had no remaining preferences, and rinsed and repeated.

Logic having been finished very late on Thursday, I spent Friday patching together some frontend, a mysql backend, a way to share each campaign (via front-end url parsing), error handling (via bad handlebars if-statements).

I think this project has the most interesting applications going forward (namely earning me a massage), so I'll likely revisit it sometime in the near future. As with Project 1, here's the mini pitch deck with a bit more detail.

Parting Thoughts

  • Build better campaign selection/sharing (search?)
  • Implement auth: only allow people within org to sign up
  • Create version that works for rolling schedules (e.g., haircuts)

Indifference Optimizer