Monday, October 29, 2007

The Problem at Hand

So, this isn't really the problem, but it's close enough...

We assign workers to jobs at various client sites around the country. Although we learn about some of these jobs a few days ahead of time, most are rush jobs -- "How soon can you get here?" sorts of things. And, these jobs are specialized. Not all workers can perform all jobs. Special equipment is often required as are various worker certifications. Fairness matters too -- workers who haven't done a job in awhile get first dibs.

Does this sound like a problem for a rules engine yet?

Even though there are a lot of hard-and-fast rules, my client's employees still need to exercise some discretion when making assignment choices. So, our goal is to provide a ranked list of workers appropriate for particular jobs. Speed is important. Users won't wait for us to compute a list of workers each time they want to contemplate a decision. A half second is probably all the compute time we can tolerate.

This leads me to discuss the scale of our problem. We have about 500 jobs starting every day and about 1000 workers. While these numbers don't seem large at first, we're looking at half a million potential assignments at any given time. Some of the rules for assignment are straightforward: If the job requires the worker to have a particular certification, he or she must have the certification. However, many of the rules are more computationally intensive: How long will it take the worker to drive to the job site, and will he be able to start on time? A call out to our routing server takes a couple of seconds, and that alone is way beyond our SLA for our users.

2 comments:

snshor said...

You may use rules to configure the problem, but to get a reasonably good solution you need to use some scheduling software specifically designed to handle this kind of problems - for example you may look at the Ilog Scheduler (I don't work or speak for Ilog)

Daniel Selman said...

I agree, this really sounds like a classic scheduling problem. Using optimization technology will likely give you much better results and execute faster.

http://www.ilog.com/products/optimization/

I do work for ILOG! ;-)

At ILOG we have a number of customers that combine rules and optimization - often the rules are used to select the constraints that are applied by the optimization engine. This allows customers to easily "tweak" the solutions without being mathematical programming gurus. The ILOG Optimization Decision Management System product is designed to suite these use cases.