HN Explorer

Ask HN: Constraint Solving Libraries for Automated Scheduling?

4 points by nathanhammond ↗ HN
I've been searching for an existing scheduling solution where the primary goal isn't filling set shift times, but instead supplying a certain amount of coverage at each hour of the day based upon a set of constraints (listed here: http://www.nathanhammond.com/a-scheduling-problem).

There are two existing categories of businesses that come to mind that might have this type of use pattern:

    * Medical facilities
    * Call centers
I've reached out (via phone!) to multiple companies that provide services to these business categories but I've been told by salespeople that they either don't have this sort of functionality, that it is so specifically tailored to the target market as to be useless to me, that I shouldn't be pursuing this (!), or they assume that because I'm doing this for a non-profit I'm not willing to pay for it (my money is just as green!).

At this point (unless you're aware of somebody that will sell their product to me) I was wondering what tools I should use to build this.

My first thought was to use something like Prolog, but because I'm not expecting there to be a "perfect" solution, I don't know how I would make that work.

After a bit of research I found Drools Planner which appears to be the 800lb gorilla, but before heading down that path I was wondering if any of you were aware of other lighter-weight tools that would make this easier to build in my spare time?

Thanks!

9 comments

[ 2.2 ms ] story [ 30.0 ms ] thread
verdatel
This might help --> https://www.shiftdata.com/
nathanhammond
Amusingly, these are the folks who told me I shouldn't be pursuing this. I don't know who it was I talked to over there, but he was very quick to dismiss me. I have an outstanding trial request with them in any case to poke at it as they seemed the most promising.
[deleted]
(comment deleted)
[deleted]
(comment deleted)
ott2
Search for constraint programming solutions to "nurse rostering" problems.
ge0ffrey
Drools planner is lightweight: use simple score calculation and you need only about 5 jars (planner, xstream and apache commons jars)
[dead] barefoot_hacker
Welcome to an old and important topic in 'operations research'.

Such scheduling problems, and 'constraint satisfaction' problems more generally, have been attacked seriously for decades.

A fundamental point is what is wanted is a 'feasible' solution to an integer linear programming problem (ILP). That is, what ILP looks for is an 'optimal' solution but you want only a 'feasible' solution.

What is 'linear programming' (LP)? Remember a high school algebra system of linear equations. Linear programming asks for a solution to such a system but also asks that one more such equation -- called the 'objective function', e.g., cost -- be as small as possible. A solution to the linear equations is 'feasible'. If a feasible solution also makes the value of the objective function as small as possible, then that solution is 'optimal'.

If we also ask that the solution be integers, then we have 'integer linear programming' (ILP).

Or, for an example, a 'feasible' solution is a path that will get you to your date's house, and an optimal solution will get you there in least time.

Fundamentally in LP and ILP, although not necessarily always in practice, looking for a feasible solution is no easier than looking for an optimal solution. That is, fundamentally constraint satisfaction is no easier than optimization. So, really, in both theory and much of practice, constraint satisfaction problems end up in the world of optimization (i.e., linear programming and ILP).

So, one approach to such scheduling and constraint satisfaction problems is ILP, and for that there is C-PLEX done by R. Bixby of Rice University and the Optimization Subroutine Library (OSL) done at IBM's Yorktown Heights lab and as in

Ming S. Hung, Walter O. Rom, Allan D. Waren, 'Optimization with IBM OSL', ISBN 0-89426-244-0, Boyd & Fraser Publishing, Danvers, MA, 1994.

And there are several more collections of LP and ILP software.

ILOG was a French company heavily interested in constraint satisfaction problems and worked with SAP and made use of C-PLEX. Apparently now ILOG and C-PLEX are sold by IBM.

For academics, ILP, constraint satisfaction, etc. are in operations research, the mathematical sciences, and selected parts of engineering. Computer science also gets interested. Schools to consider include Georgia Tech, Rice, and Waterloo. E.g., Georgia Tech was the origin of

George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York, 1999.

ILP was one of the primary sources of motivation for the theory of NP completeness in computational complexity, e.g., as in

Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.

We should note: Practical ILP problems vary enormously in difficulty. If we only ask for feasible solutions that save nearly all the money instead of necessarily the last tiny fraction of a penny exactly, then in practice the variation in difficulty is even larger. By "vary", I mean that for finding solutions some ILP problems are really easy and others are really difficult.

So, with this variation, it may be that your actual, practical problems are easy enough and can give you many happy trips to the bank.

But the theory of NP completeness asks for more: It wants an algorithm (and so far no one knows if such an algorithm can exist) that will solve any ILP problems, including the worst cases that can exist, even in theory, to exact optimality (when an optimal solution exists), in computer execution time that grows no faster than a polynomial in the size of the input data for the problem. It turns out, that's asking a lot, asks for a very strong guarantee, and asks for much more than is commonly sufficient for nice trips to the bank in practice. To be clear, many practical ILP problems are quite doable, but the worst case problems are much, much worse. To be more clear, it has long been known that your scheduling p...