Scheduling Algorithms – Elevator Edition

This Popular Mechanics article about Elevator Scheduling Algorithms is well worth a read.

This part in particular struck me:

With the elevators directing themselves, engineers had to spell out rules for when to go where. The simplest method was for the elevators to shuttle back and forth between predefined “terminal floors” at scheduled intervals. It was like taking a bus—you waited for the 3:10 car up to the 10th floor, and then found your way from there. This, of course, was grossly inefficient. During busy times of day, the elevator cabs would waste everyone’s time sitting at a terminal floor until their scheduled departure. During off-peak hours they would make pointless empty trips.

By 1965 it was clear to everyone that this was a bad idea.

So, it took until 1965 before a “grossly inefficient” (and no doubt annoying) algorithm was recognised by enough people to be considered not good enough?! How long might it take Product Managers to recognise the limitations of today’s more common approaches, I wonder.

Another thing to note is that Elevator algorithms aren’t optimising for efficiency:

Sometimes, it’s actually better to make a passenger’s ride longer. Imagine two scenarios, one in which your elevator takes 10 seconds to arrive and then one minute to reach your destination, and another in which each portion takes thirty seconds. Many people find waiting so painful that they’d prefer the first option, even though they’d reach their destination 10 seconds later (though people who feel claustrophobic in elevators would prefer to minimize time inside the car). Accordingly, some elevators optimize not for time, but for a customized “pain index,” in which the computer system weighs the awfulness of each kind of delay.

Minimising cycletime (from button press to arrival) isn’t the optimal result in this case, despite what you might expect. It seems that we would prefer to have a longer “in-process” journey if that means we can sooner reduce the uncertainty of when we might start the journey. It is waiting combined with uncertainty that is extra painful for us. As a result, pre-process waits are perceived as worse than in-process waits.

What the article doesn’t say is that post-process waits are also considered worse than pre-process waits, because there is no further value being added. For example, waiting to check out of a hotel is perceived as being more painful than waiting to check in. Continuous Delivery and reducing the cycletime of the “last mile” to production is possibly an easier sell because of this phenomenon. The value-adding changes have already been made, so why do I have to then wait for those changes to be pushed to production? (I hope to one day see a fraction of this urgency being applied upstream of development, where a lot of time is currently wasted.)

Optimising elevators for minimal “pain” makes sense. In doing so, as in most service settings, we expect everyone to be treated equally though. Delaying all people wearing jeans in order to provide a speedier service to those wearing suits would be considered offensive. Here though, is a key difference between Product Development and service settings – one that is often overlooked or purposely ignored in the design of a scheduling system – the value of the items in process.

The items travelling through a Product Development system have hugely different Cost of Delay – every backlog I have seen with quantified Cost of Delay has a power law distribution. The items also have quite different size, and consequently block the team for different lengths of time. Ignoring either of these will result in a much worse outcome.

If you’re interested in a scheduling algorithm that maximises value delivered in Product Development, you can learn about CD3 here.