Employee scheduling seems to be a problem common to a large number of businesses.
Are the needs of most small/medium businesses currently being met in this area or is there an opportunity for providing tools in this space ?
Employee Scheduling
41–50 of 137 posts
Re: Employee Scheduling
#42I’m a bit uncertain about what Google OR-Tools is…it seems to be some sort of framework for solving optimization problems, but based on the example here I am curious how general such a tool can be, as normally I find that a “drop in” algorithms framework is generally quite difficult to make or use. Is anyone using this for something useful? Does it perform faster than a hand-rolled implementation tailored to the prob…
Using solvers for Linear Programming (LP) and Mixed Integer Linear Programming (MILP) problems can be ridiculously effective and generalizes very widely.
It can't solve every problem, but it can solve many more than you think, and there's an active research area around using them for solving problems.
Re: Employee Scheduling
#43I'm glad to see the domain of constraint programming and operational research in general generate interest so I thought I would take the opportunity to share some links and resources I have found useful. Personally, I've spent most of my time on the routing (TSP, VRP, VRPTW) side of things using CP (OscaR-CP).
Discrete optimization and constraint programming can be a bit difficult to get into. There are two great free online courses on Coursera that do a good job at introducing the topic.
Discrete Optimization
https://www.coursera.org/learn/discrete-optimization
I don't remember the exact content of this course but I believe it covers the basics in a few different methodologies.
Basic Modeling for Discrete Optimization
https://www.coursera.org/learn/basic-modeling
This is a great course by Peter Stuckey that uses MiniZinc. The MiniZinc programming language is a great starting point that teaches you to think of solving discrete optimization problems only in terms of modelling the problem.
Håkan Kjellerstrands blog is another great resource
It contains hundreds of different models for a large variety of different solvers. Chances are that he has created a model for your solver for a similar problem.
Two books worth mentioning are:
Handbook of Constraint Programming
Principles of Constraint Programming
Other solvers/frameworks:
The OscaR library
https://bitbucket.org/oscarlib/oscar/wiki/Home
My personal favorite. An OR framework written entirely in Scala. As such it's an absolute joy to work with and the internals are (relatively speaking) easier to understand.
GeCode
Another extremely potent solver. Exclusively CP based.
Mini-CP
https://minicp.readthedocs.io/en/latest/
An extremly lightweight CP solver, designed for educational purposed to expose how a CP solver works without obfuscating performance optimizations found in research/production solvers.
MiniZinc
A solver agnostic constraint modelling languages, designed to interface a given optimization model with different solvers.
A few notable researches:
Phil Kilby
Pascal Van Hentenryck
Paul Shaw
Laurent Perron - OR-tools
Peter Stuckey - MiniZinc
Pierre Schaus - OscaR, Mini-CP
Renaud Hartert - OscaR
I also want to make a plug for the work of the Uppsala University optimization group
http://www.it.uu.se/research/group/optimisation/
Especially the work of Pierre Flener, Gustav Björdal and Justin Pearson who I've had the pleasure to work with during my masters thesis on vehicle routing using CP.
Re: Employee Scheduling
#44“Every day, each shift is assigned to a single nurse, and no nurse works more than one shift” WeirdChamp
Re: Employee Scheduling
#45Employee scheduling seems to be a problem common to a large number of businesses. Are the needs of most small/medium businesses currently being met in this area or is there an opportunity for providing tools in this space ?
I run a small business and we use WhenIWork to schedule our shifts. We couldn't be happier with the software, functionality, and customer support, although it's a tad pricey.
Re: Employee Scheduling
#46Earlier quoted context omitted.
It is. The two main components is the CP-SAT solver and the routing library (CP + local search). As with all discrete optimization problems, a large part of performance and scalability comes down to how well you model the problem. Using a framework gives you the flexibility to focus on modeling and the ability to easily extend your problem to satisfy new constraints without the burden of maintaining an optimization a…
It's a lot of fun to play with. I used it at work to solve a partition assignment problem (you have data preintersected by property sets and a boolean query that constrains various properties, which set of preintersections are smallest for executing the query and cover all possible respondent documents?). Unfortunately it was not quite fast enough for our use case (runtimes of 50-100ms on harder queries) but it was f…
Did you use a wrapper or work directly with the solver? If you require runtimes that are that small the compilation time into the proto-model fed into the solver is likely a bottleneck.
Usually the time horizon for solving these kinds of problems is on the scale of minutes/hours so the tool chain isn't optimized for that time span.
Re: Employee Scheduling
#47Employee scheduling seems to be a problem common to a large number of businesses. Are the needs of most small/medium businesses currently being met in this area or is there an opportunity for providing tools in this space ?
for small-medium companies managers are stressed or manipulative over this topic, some aid would help a lot yeah
Re: Employee Scheduling
#48Earlier quoted context omitted.
It's a lot of fun to play with. I used it at work to solve a partition assignment problem (you have data preintersected by property sets and a boolean query that constrains various properties, which set of preintersections are smallest for executing the query and cover all possible respondent documents?). Unfortunately it was not quite fast enough for our use case (runtimes of 50-100ms on harder queries) but it was f…
Did you use a wrapper or work directly with the solver? If you require runtimes that are that small the compilation time into the proto-model fed into the solver is likely a bottleneck. Usually the time horizon for solving these kinds of problems is on the scale of minutes/hours so the tool chain isn't optimized for that time span.
I tried both ways: compiling into the proto model to use the newer solver, and also using the older solver directly. But the profiling in each case showed that the solving time dominated. I don't think it was an issue of what the library is optimized for so much as it was just too big of a problem to solve in too little time. Even my hand rolled solution that gives non-optimal answers can take 5-10ms on difficult queries.
We ended up requiring users to adjust their queries a little to make it easier to spot the targeted preintersections. This seemed like a decent trade-off considering the latency impact of the alternative.
Re: Employee Scheduling
#49Employee scheduling seems to be a problem common to a large number of businesses. Are the needs of most small/medium businesses currently being met in this area or is there an opportunity for providing tools in this space ?
Scheduling is one of these areas where the core problem is quite well-defined, but the devil is in the details - both static and dynamic. Bit like one module of ERP.
Static details include things like local labour laws, skill constraints, unions etc.
Dynamic details include things like allowing employees to state preferences, swap shifts (while respecting labour laws), call in sick etc. without having to reshuffle everything.
There probably are quite a few submarkets (geographies/industries/sizes) that don't have tools; whether you can make money is a different question.
Re: Employee Scheduling
#50I get the point is to show a problem solving technique, but I'm either missing something, or they are missing a constraint.
In several solutions, a nurse works shift 2 one day, then shift 0 the next. In fact, Nurse 3 keeps getting stuck with the back to back shifts.