A real Computer Science problem from ServiceTitan
As you probably know, ServiceTitan helps companies from Home Services industry to be way more efficient. Doesn’t sound quite sexy for programmers, right? And I totally understand that. In reality, as any truly technology company, we have a good number of fairly complex problems to solve. Here I’ll describe a simplified version of one of these —an interesting one from algorithmic standpoint.
Let’s imagine you own a Home Services company. You have a crew of technicians typically doing “fix X / install Y” jobs. There are many ways for your customers to book a visit of one of these awesome all-hands guys, but ultimately, this process ends up with a selection of time slot for technician to arrive at.
As an owner of such a company, you want to maximize your income. You know that suggesting an appointment slot is actually a big deal:
- Obviously, you should have some free capacity for this time slot
- But even if you have a free capacity at time slot S, it doesn’t actually mean you want to suggest S to the current customer. E.g. because you know that John is the only available technician at S. And he is so awesome that typically he increases a value of any job by 20% — because he is a great technician, but also a great salesman. So frequently he finds something else to upsell. Unfortunately, the job you book now is supposed to have a very low value; on the other hand, you anticipate a few high value jobs for the time slot S. So it’s reasonable for you to suggest some other time for the current booking — or, at least, try.
That’s the high level story. Now, to make things simpler, let’s assume the definition of the problem is:
- You have a set of technicians t … t[T], a set of time slots s … s[S], and a set of jobs j … j[J]
- All time slots are ordered by their start time, and they don’t overlap with each other.
- “Assignment” is a triplet of (technician, job, time slot). Each job can be assigned only once (i.e. it can be a part of only one assignment). Each time slot can be assigned only once for each technician — and certainly, only if he is available at this time slot. Also, let’s assume any technician needs a single time slot to complete any job.
- Each cell in adjacency matrix ts[1…T, 1…S] contains 1 if a technician is available at a certain time slot, otherwise 0
- Each cell in adjacency matrix tj[1…T, 1…J] contains 1 if a technician can be assigned to a certain job, otherwise 0
- For each job, you know its estimated value j.value ≥ 0.
- For each job, you also know j.minSlotIndex— an index of time slot starting from which you can assign this job. E.g. if j.minSlotIndex = 10, you can assign j at s, s, … s[S], but not at s or s.
- For each technician, you know his/her “upsell multiplier” t[…].m > 0; e.g. if it is 1.2 for John, you expect to earn 20% more on any job you assign to John.
- 1 ≤ T ≤ 100, 1 ≤ S ≤ 30, 1 ≤ J ≤ 3000, avg(ts)~ 1 (most of technicians are available at all time slots), avg(tj) ≤ 0.3 (in average, ≤ 30% of technicians can handle a certain job).
Your goal is to assign technicians to jobs and time slots in such a way that your total expected income is maximized. In other words, your goal is to generate a set of valid assignments a[1 … A] so that sum(j[a[i].jobIndex].value * t[a[i].technicianIndex].m) is maximized over all possible sets of valid assignments.
Solutions are welcome, but it’s better to PM them to me via Facebook — I want to make sure readers of this post will have some time to think about the problem. And I’ll definitely share the info on who solved it first / second / third / etc. :)