15 ms·

Employee Scheduling

641 points by weitzj 7y ago

saagarjha 7y ago
I’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 problem? Is it easier to use?
- cm2187 7y ago
  For the part I have used, it is a common API over various solvers (free and commercial), plus some google own solvers. It is pretty neat, but because of licensing reasons requires you to recompile it yourself to access all the free solvers.
- radomir_cernoch 7y ago
  Exactly my thinking. <disclaimer>I work in a company that deals exclusively with OR. This means that we might be overly specialized for this product.</disclaimer> I see OR-Tools as an educational product. The tool is easy to start tinkering with and it has superb documentation - even for people not specialized in combinatorial optimization.
  - saagarjha 7y ago
    What do you work on?
  - 7thaccount 7y ago
    Can you link to your company. I've always thought it would be cool to 100% work on LP, MIP, and Nonlinear models. Do y'all use CPLEX/GUROBI for the big stuff and Prolog for more discreet items?
- filleokus 7y ago
  I'm not either completely sure about what "OR-Tools" really is, I've considered it an API and packaging to different solvers. I've used the LP solver [0] for real problems (not on a massive scale), but it worked very nice. Basically a scheduling problem where we very quickly could give the user a pretty decent solution as a starting point that they then could customise. Dramatically shortened the time for the user for that process, compared to the previous random/heuristic "solution" we give. [0]: https://developers.google.com/optimization/lp/glop https://developers.google.com/optimization/lp/glop
- deleted 7y ago
  [deleted]
- Sesse__ 7y ago
  It depends on how good your hand-rolled implementation is. Will it find the shortest path in a graph faster than your Dijkstra implementation? No, leave the simple problems to hand-rolled code. Can it run e.g. TSP faster than a dedicated TSP solver written by an expert? No, but it sure will beat what you or I can code up of TSP over a week. These things have great heuristics and can solve/approximate a very wide of variety of NP-hard problems much better than you could yourself. I've used the CP solver to plan sports tournament schedules (make sure everybody gets equal time on the streamed field, make sure that special team that arrives with the late train doesn't have the first game, nobody has to play two games in a row, etc.). I made the mistake of using the Python frontend (which is much worse documented than the C++ API), but otherwise, it was a good experience. Constraint programming feels a bit odd at first, though.
- paulgb 7y ago
  I have used the or-tools VRP (vehicle routing problem) solver to optimize the drawing order of a pen plotter [1]. The Python API is a bit ugly but once I got past that, I found it had enough flexibility (e.g. asymmetric costs, disjoint routes) to represent the problem neatly. 1. https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/ https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/
- knackfuss 7y ago
  I've utilized OR-Tools in conjunction with the CBC (Coin Branch and Cut) solver to solve a mold distribution optimization problem of plastic mold injectors for a client of ours. It was free and it got the job done very well. We used it in C# and it's pretty well documented. We tried LPSolve (55) and it was a pain to use and super slow. Also, commercial options like Gurobi and IBM's CPLEX are super expensive for smaller projects.
- cerved 7y ago
  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 algorithm. Generally speaking, there's no point in reinventing what's more than likely a worse wheel. OR-tools is a state of the art OR framework. The CP-SAT solver has consistently won the Minizinc challenge the last few years and the routing library is a great local search framework. It's also worth mentioning the fantastic OscaR, a Scala CP/CBLS library which I've used extensively in my masters thesis on vehicle routing. Gecode is another solid CP solver. Minizinc is an interesting project that aims to create a unified language to interface with a lot of different solvers (CP, SAT, MIP)
  - asdfasgasdgasdg 7y ago
    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 fascinating to see provably optimal solutions to the problem.
    - cerved 7y ago
      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.
      - asdfasgasdgasdg 7y ago
        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.
- aliceryhl 7y ago
  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.
- larrydag 7y ago
  There are a lot of optimization software tools available. One of my favorite is GLPK which is a free software implementation of AMPL. I created a employee scheduling framework for GLPK. It's listed as one of the examples in the download. https://www.gnu.org/software/glpk/ https://www.gnu.org/software/glpk/
michaelt 7y ago
I see their documentation also covers routing vehicles across multiple deliveries, with time windows. Can someone who's tested this stuff out advise on how many deliveries it can handle at a time? The examples only list trivial problems, but that might just be to keep the examples short.
- nappy-doo 7y ago
  I can chime in. Googler here, who knows the OR team very well. They are solving EXTREMELY large problems for customers. I can't tell you who, and I can't tell what problems, but they are among the biggest OR problems you can imagine. (No, I don't mean within Google, although they solve scheduling problems there as well.) EDIT: There are articles: https://cloud.google.com/press-releases/2020/0120/lufthansa https://cloud.google.com/press-releases/2020/0120/lufthansa https://www.cnbc.com/2020/01/19/lufthansa-taps-googles-cloud-tech-to-mitigate-impact-of-flight-delays.html https://www.cnbc.com/2020/01/19/lufthansa-taps-googles-cloud...
  - sidesquid 7y ago
    I heard of some projects involved at air controllers?
  - srean 7y ago
    I am curious if some of the ITA folks landed (no pun intended) there, not because of the airline domain but because of expertise in dealing with complicated constraints.
  - apelapan 7y ago
    The articles are more statement of ambition than indication of actually "solving problems". I will follow whatever information gets out about this project with great interest. The big challenge in making something like this actually work, are not the fancy hightech bits. Dealing with humdrum data integrations and torrential rates of change in rules and constraints, sourced from hundreds of mostly non-technical people across dozens of independent departments is where it gets hard.
- 7y ago
polotics 7y ago
Can someone chime in on how this compares with the software that takes part in the yearly planning competition, eg. FastDownward etc. What subset of PDDL is supported?
- lsuresh 7y ago
  The CP-SAT solver would be used for combinatorial optimization problems. These solvers are very different than the ones you'd use for planning problems a la PDDL.
asah 7y ago
Happy user here! I've used it for a couple of projects. Here's an open source solver for a fun presumably-NP casual video game: https://github.com/asah/tents-and-trees https://github.com/asah/tents-and-trees As with other solvers, it can be a little difficult to debug, so I recommend starting small and adding constraints and known test examples.
weitzj 7y ago
I would imagine that this tool would be helpful if you connect it with a social graph, i.e. self organizing Facebook groups which help each other take care of each other’s children during the Corona outbreak or schedule incident response teams in an organization,like:” who has to work together? Are there any hidden connections between employees?”
petters 7y ago
State of the art for employee scheduling seems to be column generation; see benchmarks here: http://www.schedulingbenchmarks.org/nurse.html http://www.schedulingbenchmarks.org/nurse.html Here is an open-source column generation solver that currently achieves the best solutions on that benchmark: https://github.com/PetterS/monolith/tree/master/minimum/linear/colgen https://github.com/PetterS/monolith/tree/master/minimum/line...
- microcolonel 7y ago
  Thank you for the pointers! I've been interested in crew scheduling systems for my company to make effective use of personnel. Is the problem of producing ideal time slots for appointments requiring a crew (pattern of ordered and unordered availability) very different?
  - petters 7y ago
    Perhaps not very different, but each problem formulation has its own complication. For column generation, specifically, the routine that generates the columns incorporates a lot of problem-specific information. The rest of the solver is more general.
pimlottc 7y ago
Are there any good projects that implement this in a user-friendly system that allows schedulers to choose from multiple options and make adjustments based day-to-day conditions? Algorithms like this look cool but can end up being too rigid for many real-world scenarios. You can’t just take the output and force everyone to follow that schedule.
- hatchoo 7y ago
  What kind of use cases do you have in mind?
  - jdironman 7y ago
    Most likely I am guessing he is thinking about the food service industry.
- londons_explore 7y ago
  One option for real world use is to take the rigid schedule, and tell people that if they don't like it they need to find swaps with other people. Make the fill schedule visible to all so people can easily find swaps by hand. Always pay the original shift owner for the shift, and preferably, don't even keep records or who really did the shift (doing so opens you up to liability if employees swap in some way that is illegal, such as doing not enough shifts to qualify for medicare/benefits/whatever). Tell them that it is critical someone fills every one of their shifts, but it needn't be them. Employees will end up bartering, swapping, paying for others to fill their shift, etc. Overall, most shifts will get filled, and most people will be happy. You run the small risk that an employee will deliberately use the ability to swap to work some illegal shift pattern, and then prosecute you over it. So far, it's never gone far.
  - lonelappde 7y ago
    Admitting you pressure your employees (not independent (sub)contractors) to pay off part of their wage to do their job? Offloading your logistical planning work to staff and not paying them for the time spent? This is begging for a NLRB lawsuit and I hope someone wises up.
mark_l_watson 7y ago
Really nice. OR is not my field, and when I must dabble, in the past, I always used MiniZinc constraint solving language (sometimes with Python bindings). On the page above the linked page, on Google’s OR tools, there is mention that their tools won four gold medals in the MiniZinc completions.
- cerved 7y ago
  Not just this year but the last couple of years
jbkiv 7y ago
Great find, thank you. I ended up playing with the tools they provide. I always loved solving optimization problems and this page ia a gem, I did not know it existed.
- cerved 7y ago
  You should check out http://www.hakank.org/ http://www.hakank.org/ for a fantastic resource of optimization models for a huge variety of solvers and problems
guiriduro 7y ago
Would also be interested in a compare and contrast with open source optaplanner https://www.optaplanner.org/learn/useCases/employeeRostering.html https://www.optaplanner.org/learn/useCases/employeeRostering...
lazycrazyowl 7y ago
How does it compare with Gurobi optimiser ?
samsquire 7y ago
I've used ORTools to schedule tasks to be done in parallel. it's really simple. https://github.com/samsquire/devops-schedule https://github.com/samsquire/devops-schedule
Dowwie 7y ago
Any thoughts about the scheduling projects open sourced by staffjoy a few years ago, regarding the relevant schedule optimizers chosen? https://github.com/Staffjoy https://github.com/Staffjoy
- philip1209 7y ago
  Hey - I was the primary author of Staffjoy! We had a few different algorithm iterations. One of our biggest learnings was that it's hard to build a generalized auto-scheduling algorithm. While most companies have similar needs at a surface level - things like local labor laws, cross-functional roles, breaks, and business quirks mean that you end up customizing the algorithm for most customers. For the best auto-scheduling - Kronos is the incumbent, and Legion.co is probably the most advanced disruptor.
  - Dowwie 7y ago
    Thanks for replying! You gave money back to investors and open sourced your work. That's commendable behavior! I never forgot that story. As usual, the solution seems straightforward from 30,000 feet but once we go into the details, it turns out to be much more complicated. Noted about Kronos and Legion. Have you done any further scheduling related work since Staffjoy?
tgflynn 7y ago
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 ?
- Alextigtig 7y ago
  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.
- agumonkey 7y ago
  for small-medium companies managers are stressed or manipulative over this topic, some aid would help a lot yeah
- mikaraento 7y ago
  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.
- ses1984 7y ago
  My sister is in charge of scheduling physicians for shifts and on call for a large hospital and she has a really hard time. She does it manually with the help of a spreadsheet. She engaged with some software company to help and after many hours of work she still uses the spreadsheet. Part of the problem is that some senior physicians do whatever they want and aren't interested in playing fair. They'll call her the day before a holiday and tell her they're not coming in, and my sister is left trying to figure out the least shitty way to cover the gap.
  - 7y ago
cerved 7y ago
I'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 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 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 http://www.hakank.org/ http://www.hakank.org/ 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 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 https://www.gecode.org/ https://www.gecode.org/ Another extremely potent solver. Exclusively CP based. Mini-CP https://minicp.readthedocs.io/en/latest/ 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 https://www.minizinc.org/ https://www.minizinc.org/ 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/ 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.
whatsmyusername 7y ago
“Every day, each shift is assigned to a single nurse, and no nurse works more than one shift” WeirdChamp
ytjohn 7y ago
I 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.
- cerved 7y ago
  Are you referring to the first model? Only 5/5184 solutions are displayed. There's no objective function and the branching is probably defaulting to a simple systematic search with min domain, min value heuristic. If these are the first 5 solutions in the search tree, it's not surprising that nurse 3 keeps getting stuck with back to back shifts (does not work day 3)
  - Tarq0n 7y ago
    They listed the constraint of no back-back shifts in the text but didn't implement it as a constraint.
    - cerved 7y ago
      By back to back, do you mean nurse 3 works shift 2 day 1 and shift 0 day 2? Or that nurse 3 always works two days in a row in the listed solutions? The example doesn't mention back to back shifts, only that a nurse can at most work one shift a day which in turn implies the constraint that no nurse can work shifts back to back (in the same day). One could easily add the constraint that a nurse scheduled on shift 2 cannot work shift 0 the next day.
simulate 7y ago
I built a web interface for this type of nurse scheduling optimization. Mine uses CPLEX instead of the CP-SAT solver but the Python set up is very similar. Here's the web interface to the nurse scheduler: https://forio.com/app/showcase/nurse-scheduling/ https://forio.com/app/showcase/nurse-scheduling/ and here are some other optimization examples: https://forio.com/products/epicenter/example-applications/ https://forio.com/products/epicenter/example-applications/
- 6510 7y ago
  https://forio.com/app/showcase/nurse-scheduling/nurses.html?Gloria https://forio.com/app/showcase/nurse-scheduling/nurses.html?... Thursday, 02:00 to 08:00 — Emergency Thursday, 08:00 to 12:00 — Oncology Thursday, 12:00 to 18:00 — Oncology Friday, 08:00 to 12:00 — Emergency
  - toxik 7y ago
    Turns out Gloria is an incredibly hard worker.
    - 6510 7y ago
      Oh angry programmers are down voting my post. People driving desks.
    - blindfly 7y ago
      It's the pandemic thing everyone's working overtime
duxup 7y ago
Technical solution aside: I wrote a schedule for a team of ~20 co-workers for a 24/7 support shop. This required people change shifts / sleep schedules often. The schedule was a point of contention for years. After I volunteered to write the schedules, in 3 months I had everyone happy. It was not hard.....but.... The catch was that I did it manually for a month at a time with a wide ranging amount of changing priorities that would be hard to program ... and the key was COMMUNICATION, and working with people and their personal preferences.
- cosmodisk 7y ago
  One of the senior teachers in my school used to organise schedule for 1000 pupils and 50+ teachers. With some minor things everything worked pretty damn well.Then they decided to get some software to do the same.Never ended up working...
  - duxup 7y ago
    Humans might be kinda slow and expensive, but their ability to handle a lot of variable data and inputs and weigh them dynamically, filter out absurd results before applying them, and etc is pretty amazing. Like if someone comes to me and says "what if we... did X with the schedule". I could tell them how to do that and not to right away. The code would have to be changed / rewritten and tested and fail at it each time... so much mess. Especially when scheduling other humans... the humans being scheduled can smell a computer scheduling a mile away and IMO they expect the worst at that point. They're not necessarily wrong.
    - marcosdumay 7y ago
      > their ability to handle a lot of variable data and inputs and weigh them dynamically I dunno. Computers are pretty good at this one too, on different kinds of variance and weights. The largest problem I see is that everyone is discussing "either or" on this thread, while the clear winner is both.
      - 7y ago
ralaruri 7y ago
Google OR tools was an excellent resource when I was trying to solve a p-median problem in Python for my operations research course in school. https://github.com/ralaruri/Pmedian/blob/master/PMedianRamziEditFinal.py https://github.com/ralaruri/Pmedian/blob/master/PMedianRamzi...
graycat 7y ago
WOW! There is still some interest in optimization? I'm shocked! The message long was "Operations Research is dead." Gee, I got started in OR (operations research) at FedEx, covered a lot from some of the best people in grad school, taught it as a prof in B-school, and applied it to US national security and some commercial problems. Good to see the interest in some of the flight operations work for Lufthansa -- I was considering (no great progress) some of those problems at FedEx! One commercial problem was allocating marketing resources for some banks. I was given the formulation, 0-1 integer linear programming with 600,000 variables and 40,000 constraints. I derived some non-linear duality theory, used the IBM OSL (Optimization Subroutine Library), and in 500 iterations found a feasible solution with the objective function guaranteed to be within 0.025% of optimality! Another commercial problem was some more marketing optimization. It was also 0-1 integer linear programming, but surprisingly it was just a problem in least cost network flows. That is also linear programming, but there the simplex algorithm takes on a special form where a basis is a spanning tree of arcs in the network. A simplex pivot is to add an arc to the tree, thus, yielding a circuit, and running flow around the circuit in the direction that saves money and removing from the circuit, thus, making a tree again, one of the first arcs where the flow goes to zero. There is a cute variation of the algorithm due to W. Cunningham (one of my profs) based on his strongly feasible basis, that avoids cycling. A super nice point about the simplex problem on least cost network flows is if all the arc capacities are whole numbers and if start with an integer basic feasible solution, then the simplex algorithm will automatically maintain an integer basic feasible solution and terminate with an integer solution. It is good to suspect that a lot of integer linear programming problems are actually just such network flow problems or nearly so. Once I used that stuff to say, for NASA, how to assign signals to satellite channels to minimize some signal interference -- it was an example of the bottleneck assignment problem which should be solvable very quickly by some post optimality tweaking with the network simplex algorithm. I enjoyed using the IBM OSL, but IBM withdrew it from marketing in about 2003, maybe in favor of marketing C-PLEX. But it appears that at about 2004 IBM donated the source of the OSL (with lots of pieces, network flow, stochastic programming, etc.) to Riverware which might distribute the open source. I got started with the OSL when I was in an AI group at IBM's Watson lab where the OSL was written. The Watson lab long had some high expertise in optimization -- Gomory (cutting planes, Gilmore-Gomory column generation, etc.) was head of the lab; there was Phil Wolfe (the Wolfe dual, etc.), Ellis Johnson (group theory and integer programming), etc. So, in particular, if still want to do some OR and optimization, get some quite well written software, and save some money, then might look into getting all the IBM OSL code open source.
johnjwang 7y ago
We run into this for customer support (www.assembled.com) and one of the things we've learned is that the ability to solve the fully constrained problem in the real world is not quite enough, at least for our customers. Quite often, people are looking for the right set of constraints to apply so they're kind of running a meta problem on top of the NSP. How many back-to-back shifts should I allow? Should people's shifts always start at the same time? Can I give some people regular 9-5 schedules? All of the above questions will decrease the strict optimality of the solution, but increase the happiness and long term retention of your workforce. Thus, the question really become, how much do each of these cost in terms of optimality and what are the tradeoffs. We've found that developing a very fast heuristic algorithm for the NSP allows people to iterate quickly on these types of questions (even though it's not quite as optimal as a SAT solver). We use a greedy algorithm with a heuristic that is relatively specific to our problem domain to ensure that we have a reasonable combination of speed and optimality.
MatthewWilkes 7y ago
DevRel was a mistake.
lonelappde 7y ago
Why was the title changed to something less informative?
coleca 7y ago
Interesting project, I'd like to see it take into account decades of ambiguous union contracts, past practices, seniority, preferences, time off requests, preferences, training and certification levels, and not to mention the various local, state and federal labor laws. Scheduling isn't an easy problem to solve in the real world vs the lab where there are far less constraints and consequences for getting it wrong. Kronos (kronos.com) is the recognized leader in this space and even their software has a hard time keeping it all straight.
- cerved 7y ago
  CP solvers are excellent at handling side constraints, at least as long as they can be expressed as a boolean, discrete or linear relation.
whatever1 7y ago
IBM makes an even faster (than google or) cp optimizer https://arxiv.org/pdf/1909.08247.pdf https://arxiv.org/pdf/1909.08247.pdf
deleted 7y ago
[deleted]
dzink 7y ago
We had to find a solution for doctors to manage 22 different peers distributing 30 shifts a month. The schedule had to abide by each employees vacation requests and distributed undesirable shifts like weekends and holidays in some equitable manner, and be easily interpreted by staff. The solution was an excel spreadsheet with a lot of auto-fill logic and formulas to show shift and burden counts for each doctor so the person managing the sheet could move around shifts when needed and ensure equitable distribution still remained. Excel really helped where python and other tools would require a lot more code and be a lot less flexible to operator changes.
- hipjiveguy 7y ago
  Since it's a spreadsheet, is there any way you can share it? I assume the Dr's names could be easily changed so it's generic?
froindt 7y ago
I have been building a employee scheduling system in a factory environment. New employees need to be trained on machines, for a certain number of shifts, with a limit of how many employees can train on a machine at a time. A question becomes "how many new employees could we handle?". I looked at some solutions, but landed on an Excel spreadsheet with a small macro for spreadsheet setup, conditional formatting to call out an employee being allocated to 2 positions on the same shift, and a visual way to show for each operator, how long it takes to be fully trained. HR or a manager can setup training schedules by manually allocating people to training slots. There were some constraints the business wanted (train on machine #1 before #2, do 2 days of training if you haven't already trained on _x_ machine). They would have been hard to accommodate in a way the end user could configure, so I have a notes section they can fill in (and they have to manually observe these constraints). Totally open to other ideas people have on how to approach the proble.
- mushufasa 7y ago
  This sounds like a good solution to me. I can imagine some HN readers might comment 'ew Excel!' but it truly is the right tool for something where you have to transparently demonstrate the logic to non-technical stakeholders in a way they can easily edit and adapt. Of course, you could build or buy a web app that handles this specific scenario more powerfully and scaleably, but if this is a quarterly problem rather than a everyday problem then the additional overhead of the different interface / logins may not be worthwhile. My only comments would be 1) macros are too hard for nontechnical users in my experience, even just w/r/t setup (excel prompts you a security warning to enable macros that is scary). I think you could maybe do this using the what-if analysis tables, simple ifelse formulas, and conditional formatting. 2) another improvement might be a cloud-based version where there is a link at which others can easily view + collaborate, like Google Sheets or Airtable. I think Excel is supposed to have this feature as part of the 365 subscription but I've never used it.
- cerved 7y ago
  Using Excel sounds like a pain to maintain but if it works it works. Your problem sounds like a JSP (job shop scheduling problem). If it is you could use MiniZinc https://www.minizinc.org/ https://www.minizinc.org/ and look at Håkan Kjellstrans MiniZinc page http://www.hakank.org/minizinc/ http://www.hakank.org/minizinc/, it has a couple of different JSP models.
aerovistae 7y ago
What is this? There's no introduction
- cerved 7y ago
  It's an example model of how to use the or-tools CP-SAT solver to solve employee scheduling problems. It's part of the or-tools library which is a framework for solving scheduling, routing and other NP-hard discrete optimization problems https://developers.google.com/optimization/introduction/overview https://developers.google.com/optimization/introduction/over...
JustSomeNobody 7y ago
This doesn’t take into account certain people are more productive when paired up (and less productive when paired with other people).
- cerved 7y ago
  No it doesn't. It's an extremely basic model to introduce the CP-SAT solver to people with little to no experience in scheduling problems or CP. Pairing up people based on such criteria requires turning the problem into a MOCO or incorporating it with the current objective function.
mcguire 7y ago
"OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions."
closeparen 7y ago
My team used to have an absolutely wild script for oncall scheduling. People would enter their availability weeks, and then we'd run a genetic algorithm, scoring the fitness of each schedule "offspring" according to the number of availabilities violated and then making random mutations to the most promising. It would slam CPU for several hours and still produce clearly ridiculous solutions. Brute force would have been better. I'll have to play with this.
dghughes 7y ago
The problem with employee schedules where employees work in shifts is communication. At one place it was done using Excel as I'm sure it's still done today in many organizations. You always have two people trading shifts but never telling anyone. Then the one who was supposed to work doesn't show up they forgot they traded shifts. Human nature is half the problem.
jonbaer 7y ago
Maybe a little OT, but why aren't the OR-tools in general more focused (or more "marketed") towards GPU/TPU clouds since they seem like the exact problems which they are made for? More focus seems to be towards TF/PT/NN and not the real problems like what OR-tools and solvers in general push for.
- mochomocha 7y ago
  Typical algorithms solving combinatorial problems are usually heavily branching, so not so much vectorizable. For example for a branch-and-cut MIP solver, you could run the LP-relaxed problems on GPU, but most of the logic lives in branching and cutting heuristics that are much harder to parallelize.
- 7thaccount 7y ago
  A lot of OR stuff can be parallelized, but it isn't a panacea. Those techniques don't necessarily get you the best answer sometimes. My company does some massive optimization problems and although we have lots of cores for all the simulations, any one is pretty much single core + a lot of RAM. It doesn't work well on GPU like some heuristic optimization problems can. Edit: Someone smarter than me says it better below :)
- cerved 7y ago
  For starters, CP and SAT are based on integers and boolean variables. Secondly, local search and systematic search are just no way near parallelizable to the degree required to see gains running GPU/TPU.
mighty_plant 7y ago
Google or-tools are quite fun although a little bit of a pain to setup and get started at least if you want to use the JVM and support different OS. Just to share a little anecdote about my use case: The department I work in consists of about 40 developers and once a year we had a day together just to form new teams in a self organized manner. Management wanted about one third of a team to move to a different team to spread and gather knowledge but completely backed off during that day. We had a special coach and scrum masters supporting us but still it was very exhausting and a lot of the developers didn't like it. The devs that showed motivation to change teams were more or less forced to go to the teams which were disliked the most (either because of their domain or the already present members). So in the end there was not much rotation and the whole thing was quite expensive so that this year it was cancelled. That's when I started to use Google or-Tools to write a little tool that suggests teams based on some constraints like size, at least one experienced dev / software architect per team and an optimization function based on preferences of each dev for a certain domain as well as their sympathy towards other devs When I announced it it got almost no attention and was dismissed as "inhuman".
IndexPointer 7y ago
Well now I want to spend a few hours using it to solve the peaceable queens problem: https://youtu.be/IN1fPtY9jYg https://youtu.be/IN1fPtY9jYg
- cerved 7y ago
  Sounds similar to n-Queens, check out http://www.hakank.org/google_or_tools/nqueens.py http://www.hakank.org/google_or_tools/nqueens.py http://www.hakank.org/google_or_tools/nqueens2.py http://www.hakank.org/google_or_tools/nqueens2.py http://www.hakank.org/google_or_tools/nqueens3.py http://www.hakank.org/google_or_tools/nqueens3.py for inspiration
  - hakank 7y ago
    Actually, the Peaceable Army (or Armies) of Queens problem is a separate problem and much harder than the n-queens problem. Here is a MiniZinc model: http://hakank.org/minizinc/peaceableArmyOfQueens.mzn http://hakank.org/minizinc/peaceableArmyOfQueens.mzn , and a Picat model: http://hakank.org/picat/peaceableArmyOfQueens.pi http://hakank.org/picat/peaceableArmyOfQueens.pi (Also: Thanks for your links to my site.)
westurner 7y ago
From "Ask HN: What algorithms should I research to code a conference scheduling app" https://news.ycombinator.com/item?id=15267804 https://news.ycombinator.com/item?id=15267804 : > Resource scheduling, CSP (Constraint Satisfaction programming) CSP: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem https://en.wikipedia.org/wiki/Constraint_satisfaction_proble... Scheduling (production processes): https://en.wikipedia.org/wiki/Scheduling_(production_processes) https://en.wikipedia.org/wiki/Scheduling_(production_process... Scheduling (computing): https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Scheduling_(computing) ... To an OS, a process thread has a priority and sometimes a CPU affinity. From http://markmail.org/search/?q=list%3Aorg.python.omaha+pyschedule#query:list%3Aorg.python.omaha%20pyschedule+page:1+mid:enenp7smhvr5636g+state:results http://markmail.org/search/?q=list%3Aorg.python.omaha+pysche... : Pyschedule: - Src: https://github.com/timnon/pyschedule https://github.com/timnon/pyschedule From https://github.com/timnon/pyschedule https://github.com/timnon/pyschedule : > pyschedule is python package to compute resource-constrained task schedules. Some features are: - precedence relations: e.g. task A should be done before task B - resource requirements: e.g. task A can be done by resource X or Y - resource capacities: e.g. resource X can only process a few tasks Previous use-cases include: - school timetables: assign teachers to classes - beer brewing: assign equipment to brewing stages - sport schedules: assign stadiums to games ... https://en.wikipedia.org/wiki/Slurm_Workload_Manager https://en.wikipedia.org/wiki/Slurm_Workload_Manager : > Slurm is the workload manager on about 60% of the TOP500 supercomputers.[1] Slurm uses a best fit algorithm based on Hilbert curve scheduling or fat tree network topology in order to optimize locality of task assignments on parallel computers.[2] ... https://en.wikipedia.org/wiki/Hilbert_curve_scheduling https://en.wikipedia.org/wiki/Hilbert_curve_scheduling : > [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes.[2]
tracker1 7y ago
Now do that with a few thousand employees, vacation request ranking/status and three different sets of thousands of pages of union contracts. The above is something I actually worked on before.. The bitter irony, is they all just traded their vacation weeks as it came up anyway.
reportgunner 7y ago
This looks nice but actually doesn't adress the actual challenges of scheduling. It's rather easy to generate a schedule and most of the feasible variants are available online already (there aren't infinite possibilities on how to schedule shifts) - you fit it to a 7 day or a 28 day (or a multiple of 7) cycle and then copy paste. The scheduling challenges occur when people need to take unexpected vacations or during vacation period when staffing is low. Another challenge is the skill level of the individual employees which is usually not binary - can do work / cannot do work - since employees come to work to perform tasks and they don't always learn all of the tasks the first day.

641 points by weitzj 7y ago

I’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 problem? Is it easier to use?

cm2187 7y ago
For the part I have used, it is a common API over various solvers (free and commercial), plus some google own solvers. It is pretty neat, but because of licensing reasons requires you to recompile it yourself to access all the free solvers.
radomir_cernoch 7y ago
Exactly my thinking. <disclaimer>I work in a company that deals exclusively with OR. This means that we might be overly specialized for this product.</disclaimer> I see OR-Tools as an educational product. The tool is easy to start tinkering with and it has superb documentation - even for people not specialized in combinatorial optimization.
- saagarjha 7y ago
  What do you work on?
- 7thaccount 7y ago
  Can you link to your company. I've always thought it would be cool to 100% work on LP, MIP, and Nonlinear models. Do y'all use CPLEX/GUROBI for the big stuff and Prolog for more discreet items?
filleokus 7y ago
I'm not either completely sure about what "OR-Tools" really is, I've considered it an API and packaging to different solvers. I've used the LP solver [0] for real problems (not on a massive scale), but it worked very nice. Basically a scheduling problem where we very quickly could give the user a pretty decent solution as a starting point that they then could customise. Dramatically shortened the time for the user for that process, compared to the previous random/heuristic "solution" we give. [0]: https://developers.google.com/optimization/lp/glop https://developers.google.com/optimization/lp/glop
deleted 7y ago
[deleted]
Sesse__ 7y ago
It depends on how good your hand-rolled implementation is. Will it find the shortest path in a graph faster than your Dijkstra implementation? No, leave the simple problems to hand-rolled code. Can it run e.g. TSP faster than a dedicated TSP solver written by an expert? No, but it sure will beat what you or I can code up of TSP over a week. These things have great heuristics and can solve/approximate a very wide of variety of NP-hard problems much better than you could yourself. I've used the CP solver to plan sports tournament schedules (make sure everybody gets equal time on the streamed field, make sure that special team that arrives with the late train doesn't have the first game, nobody has to play two games in a row, etc.). I made the mistake of using the Python frontend (which is much worse documented than the C++ API), but otherwise, it was a good experience. Constraint programming feels a bit odd at first, though.
paulgb 7y ago
I have used the or-tools VRP (vehicle routing problem) solver to optimize the drawing order of a pen plotter [1]. The Python API is a bit ugly but once I got past that, I found it had enough flexibility (e.g. asymmetric costs, disjoint routes) to represent the problem neatly. 1. https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/ https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/
knackfuss 7y ago
I've utilized OR-Tools in conjunction with the CBC (Coin Branch and Cut) solver to solve a mold distribution optimization problem of plastic mold injectors for a client of ours. It was free and it got the job done very well. We used it in C# and it's pretty well documented. We tried LPSolve (55) and it was a pain to use and super slow. Also, commercial options like Gurobi and IBM's CPLEX are super expensive for smaller projects.
cerved 7y ago
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 algorithm. Generally speaking, there's no point in reinventing what's more than likely a worse wheel. OR-tools is a state of the art OR framework. The CP-SAT solver has consistently won the Minizinc challenge the last few years and the routing library is a great local search framework. It's also worth mentioning the fantastic OscaR, a Scala CP/CBLS library which I've used extensively in my masters thesis on vehicle routing. Gecode is another solid CP solver. Minizinc is an interesting project that aims to create a unified language to interface with a lot of different solvers (CP, SAT, MIP)
- asdfasgasdgasdg 7y ago
  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 fascinating to see provably optimal solutions to the problem.
  - cerved 7y ago
    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.
    - asdfasgasdgasdg 7y ago
      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.
aliceryhl 7y ago
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.
larrydag 7y ago
There are a lot of optimization software tools available. One of my favorite is GLPK which is a free software implementation of AMPL. I created a employee scheduling framework for GLPK. It's listed as one of the examples in the download. https://www.gnu.org/software/glpk/ https://www.gnu.org/software/glpk/

michaelt 7y ago

I see their documentation also covers routing vehicles across multiple deliveries, with time windows. Can someone who's tested this stuff out advise on how many deliveries it can handle at a time? The examples only list trivial problems, but that might just be to keep the examples short.

nappy-doo 7y ago
I can chime in. Googler here, who knows the OR team very well. They are solving EXTREMELY large problems for customers. I can't tell you who, and I can't tell what problems, but they are among the biggest OR problems you can imagine. (No, I don't mean within Google, although they solve scheduling problems there as well.) EDIT: There are articles: https://cloud.google.com/press-releases/2020/0120/lufthansa https://cloud.google.com/press-releases/2020/0120/lufthansa https://www.cnbc.com/2020/01/19/lufthansa-taps-googles-cloud-tech-to-mitigate-impact-of-flight-delays.html https://www.cnbc.com/2020/01/19/lufthansa-taps-googles-cloud...
- sidesquid 7y ago
  I heard of some projects involved at air controllers?
- srean 7y ago
  I am curious if some of the ITA folks landed (no pun intended) there, not because of the airline domain but because of expertise in dealing with complicated constraints.
- apelapan 7y ago
  The articles are more statement of ambition than indication of actually "solving problems". I will follow whatever information gets out about this project with great interest. The big challenge in making something like this actually work, are not the fancy hightech bits. Dealing with humdrum data integrations and torrential rates of change in rules and constraints, sourced from hundreds of mostly non-technical people across dozens of independent departments is where it gets hard.
7y ago

polotics 7y ago

Can someone chime in on how this compares with the software that takes part in the yearly planning competition, eg. FastDownward etc. What subset of PDDL is supported?

lsuresh 7y ago
The CP-SAT solver would be used for combinatorial optimization problems. These solvers are very different than the ones you'd use for planning problems a la PDDL.

asah 7y ago

Happy user here! I've used it for a couple of projects. Here's an open source solver for a fun presumably-NP casual video game: https://github.com/asah/tents-and-trees https://github.com/asah/tents-and-trees As with other solvers, it can be a little difficult to debug, so I recommend starting small and adding constraints and known test examples.

weitzj 7y ago

I would imagine that this tool would be helpful if you connect it with a social graph, i.e. self organizing Facebook groups which help each other take care of each other’s children during the Corona outbreak or schedule incident response teams in an organization,like:” who has to work together? Are there any hidden connections between employees?”

petters 7y ago

State of the art for employee scheduling seems to be column generation; see benchmarks here: http://www.schedulingbenchmarks.org/nurse.html http://www.schedulingbenchmarks.org/nurse.html Here is an open-source column generation solver that currently achieves the best solutions on that benchmark: https://github.com/PetterS/monolith/tree/master/minimum/linear/colgen https://github.com/PetterS/monolith/tree/master/minimum/line...

microcolonel 7y ago
Thank you for the pointers! I've been interested in crew scheduling systems for my company to make effective use of personnel. Is the problem of producing ideal time slots for appointments requiring a crew (pattern of ordered and unordered availability) very different?
- petters 7y ago
  Perhaps not very different, but each problem formulation has its own complication. For column generation, specifically, the routine that generates the columns incorporates a lot of problem-specific information. The rest of the solver is more general.

pimlottc 7y ago

Are there any good projects that implement this in a user-friendly system that allows schedulers to choose from multiple options and make adjustments based day-to-day conditions? Algorithms like this look cool but can end up being too rigid for many real-world scenarios. You can’t just take the output and force everyone to follow that schedule.

hatchoo 7y ago
What kind of use cases do you have in mind?
- jdironman 7y ago
  Most likely I am guessing he is thinking about the food service industry.
londons_explore 7y ago
One option for real world use is to take the rigid schedule, and tell people that if they don't like it they need to find swaps with other people. Make the fill schedule visible to all so people can easily find swaps by hand. Always pay the original shift owner for the shift, and preferably, don't even keep records or who really did the shift (doing so opens you up to liability if employees swap in some way that is illegal, such as doing not enough shifts to qualify for medicare/benefits/whatever). Tell them that it is critical someone fills every one of their shifts, but it needn't be them. Employees will end up bartering, swapping, paying for others to fill their shift, etc. Overall, most shifts will get filled, and most people will be happy. You run the small risk that an employee will deliberately use the ability to swap to work some illegal shift pattern, and then prosecute you over it. So far, it's never gone far.
- lonelappde 7y ago
  Admitting you pressure your employees (not independent (sub)contractors) to pay off part of their wage to do their job? Offloading your logistical planning work to staff and not paying them for the time spent? This is begging for a NLRB lawsuit and I hope someone wises up.

mark_l_watson 7y ago

Really nice. OR is not my field, and when I must dabble, in the past, I always used MiniZinc constraint solving language (sometimes with Python bindings). On the page above the linked page, on Google’s OR tools, there is mention that their tools won four gold medals in the MiniZinc completions.

cerved 7y ago
Not just this year but the last couple of years

jbkiv 7y ago

Great find, thank you. I ended up playing with the tools they provide. I always loved solving optimization problems and this page ia a gem, I did not know it existed.

cerved 7y ago
You should check out http://www.hakank.org/ http://www.hakank.org/ for a fantastic resource of optimization models for a huge variety of solvers and problems

guiriduro 7y ago

Would also be interested in a compare and contrast with open source optaplanner https://www.optaplanner.org/learn/useCases/employeeRostering.html https://www.optaplanner.org/learn/useCases/employeeRostering...

lazycrazyowl 7y ago

How does it compare with Gurobi optimiser ?

samsquire 7y ago

I've used ORTools to schedule tasks to be done in parallel. it's really simple. https://github.com/samsquire/devops-schedule https://github.com/samsquire/devops-schedule

Dowwie 7y ago

Any thoughts about the scheduling projects open sourced by staffjoy a few years ago, regarding the relevant schedule optimizers chosen? https://github.com/Staffjoy https://github.com/Staffjoy

philip1209 7y ago
Hey - I was the primary author of Staffjoy! We had a few different algorithm iterations. One of our biggest learnings was that it's hard to build a generalized auto-scheduling algorithm. While most companies have similar needs at a surface level - things like local labor laws, cross-functional roles, breaks, and business quirks mean that you end up customizing the algorithm for most customers. For the best auto-scheduling - Kronos is the incumbent, and Legion.co is probably the most advanced disruptor.
- Dowwie 7y ago
  Thanks for replying! You gave money back to investors and open sourced your work. That's commendable behavior! I never forgot that story. As usual, the solution seems straightforward from 30,000 feet but once we go into the details, it turns out to be much more complicated. Noted about Kronos and Legion. Have you done any further scheduling related work since Staffjoy?

tgflynn 7y ago

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 ?

Alextigtig 7y ago
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.
agumonkey 7y ago
for small-medium companies managers are stressed or manipulative over this topic, some aid would help a lot yeah
mikaraento 7y ago
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.
ses1984 7y ago
My sister is in charge of scheduling physicians for shifts and on call for a large hospital and she has a really hard time. She does it manually with the help of a spreadsheet. She engaged with some software company to help and after many hours of work she still uses the spreadsheet. Part of the problem is that some senior physicians do whatever they want and aren't interested in playing fair. They'll call her the day before a holiday and tell her they're not coming in, and my sister is left trying to figure out the least shitty way to cover the gap.
- 7y ago

cerved 7y ago

I'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 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 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 http://www.hakank.org/ http://www.hakank.org/ 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 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 https://www.gecode.org/ https://www.gecode.org/ Another extremely potent solver. Exclusively CP based. Mini-CP https://minicp.readthedocs.io/en/latest/ 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 https://www.minizinc.org/ https://www.minizinc.org/ 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/ 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.

whatsmyusername 7y ago

“Every day, each shift is assigned to a single nurse, and no nurse works more than one shift” WeirdChamp

ytjohn 7y ago

I 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.

cerved 7y ago
Are you referring to the first model? Only 5/5184 solutions are displayed. There's no objective function and the branching is probably defaulting to a simple systematic search with min domain, min value heuristic. If these are the first 5 solutions in the search tree, it's not surprising that nurse 3 keeps getting stuck with back to back shifts (does not work day 3)
- Tarq0n 7y ago
  They listed the constraint of no back-back shifts in the text but didn't implement it as a constraint.
  - cerved 7y ago
    By back to back, do you mean nurse 3 works shift 2 day 1 and shift 0 day 2? Or that nurse 3 always works two days in a row in the listed solutions? The example doesn't mention back to back shifts, only that a nurse can at most work one shift a day which in turn implies the constraint that no nurse can work shifts back to back (in the same day). One could easily add the constraint that a nurse scheduled on shift 2 cannot work shift 0 the next day.

simulate 7y ago

I built a web interface for this type of nurse scheduling optimization. Mine uses CPLEX instead of the CP-SAT solver but the Python set up is very similar. Here's the web interface to the nurse scheduler: https://forio.com/app/showcase/nurse-scheduling/ https://forio.com/app/showcase/nurse-scheduling/ and here are some other optimization examples: https://forio.com/products/epicenter/example-applications/ https://forio.com/products/epicenter/example-applications/

6510 7y ago
https://forio.com/app/showcase/nurse-scheduling/nurses.html?Gloria https://forio.com/app/showcase/nurse-scheduling/nurses.html?... Thursday, 02:00 to 08:00 — Emergency Thursday, 08:00 to 12:00 — Oncology Thursday, 12:00 to 18:00 — Oncology Friday, 08:00 to 12:00 — Emergency
- toxik 7y ago
  Turns out Gloria is an incredibly hard worker.
  - 6510 7y ago
    Oh angry programmers are down voting my post. People driving desks.
  - blindfly 7y ago
    It's the pandemic thing everyone's working overtime

duxup 7y ago

Technical solution aside: I wrote a schedule for a team of ~20 co-workers for a 24/7 support shop. This required people change shifts / sleep schedules often. The schedule was a point of contention for years. After I volunteered to write the schedules, in 3 months I had everyone happy. It was not hard.....but.... The catch was that I did it manually for a month at a time with a wide ranging amount of changing priorities that would be hard to program ... and the key was COMMUNICATION, and working with people and their personal preferences.

cosmodisk 7y ago
One of the senior teachers in my school used to organise schedule for 1000 pupils and 50+ teachers. With some minor things everything worked pretty damn well.Then they decided to get some software to do the same.Never ended up working...
- duxup 7y ago
  Humans might be kinda slow and expensive, but their ability to handle a lot of variable data and inputs and weigh them dynamically, filter out absurd results before applying them, and etc is pretty amazing. Like if someone comes to me and says "what if we... did X with the schedule". I could tell them how to do that and not to right away. The code would have to be changed / rewritten and tested and fail at it each time... so much mess. Especially when scheduling other humans... the humans being scheduled can smell a computer scheduling a mile away and IMO they expect the worst at that point. They're not necessarily wrong.
  - marcosdumay 7y ago
    > their ability to handle a lot of variable data and inputs and weigh them dynamically I dunno. Computers are pretty good at this one too, on different kinds of variance and weights. The largest problem I see is that everyone is discussing "either or" on this thread, while the clear winner is both.
    - 7y ago

ralaruri 7y ago

Google OR tools was an excellent resource when I was trying to solve a p-median problem in Python for my operations research course in school. https://github.com/ralaruri/Pmedian/blob/master/PMedianRamziEditFinal.py https://github.com/ralaruri/Pmedian/blob/master/PMedianRamzi...

graycat 7y ago

WOW! There is still some interest in optimization? I'm shocked! The message long was "Operations Research is dead." Gee, I got started in OR (operations research) at FedEx, covered a lot from some of the best people in grad school, taught it as a prof in B-school, and applied it to US national security and some commercial problems. Good to see the interest in some of the flight operations work for Lufthansa -- I was considering (no great progress) some of those problems at FedEx! One commercial problem was allocating marketing resources for some banks. I was given the formulation, 0-1 integer linear programming with 600,000 variables and 40,000 constraints. I derived some non-linear duality theory, used the IBM OSL (Optimization Subroutine Library), and in 500 iterations found a feasible solution with the objective function guaranteed to be within 0.025% of optimality! Another commercial problem was some more marketing optimization. It was also 0-1 integer linear programming, but surprisingly it was just a problem in least cost network flows. That is also linear programming, but there the simplex algorithm takes on a special form where a basis is a spanning tree of arcs in the network. A simplex pivot is to add an arc to the tree, thus, yielding a circuit, and running flow around the circuit in the direction that saves money and removing from the circuit, thus, making a tree again, one of the first arcs where the flow goes to zero. There is a cute variation of the algorithm due to W. Cunningham (one of my profs) based on his strongly feasible basis, that avoids cycling. A super nice point about the simplex problem on least cost network flows is if all the arc capacities are whole numbers and if start with an integer basic feasible solution, then the simplex algorithm will automatically maintain an integer basic feasible solution and terminate with an integer solution. It is good to suspect that a lot of integer linear programming problems are actually just such network flow problems or nearly so. Once I used that stuff to say, for NASA, how to assign signals to satellite channels to minimize some signal interference -- it was an example of the bottleneck assignment problem which should be solvable very quickly by some post optimality tweaking with the network simplex algorithm. I enjoyed using the IBM OSL, but IBM withdrew it from marketing in about 2003, maybe in favor of marketing C-PLEX. But it appears that at about 2004 IBM donated the source of the OSL (with lots of pieces, network flow, stochastic programming, etc.) to Riverware which might distribute the open source. I got started with the OSL when I was in an AI group at IBM's Watson lab where the OSL was written. The Watson lab long had some high expertise in optimization -- Gomory (cutting planes, Gilmore-Gomory column generation, etc.) was head of the lab; there was Phil Wolfe (the Wolfe dual, etc.), Ellis Johnson (group theory and integer programming), etc. So, in particular, if still want to do some OR and optimization, get some quite well written software, and save some money, then might look into getting all the IBM OSL code open source.

johnjwang 7y ago

We run into this for customer support (www.assembled.com) and one of the things we've learned is that the ability to solve the fully constrained problem in the real world is not quite enough, at least for our customers. Quite often, people are looking for the right set of constraints to apply so they're kind of running a meta problem on top of the NSP. How many back-to-back shifts should I allow? Should people's shifts always start at the same time? Can I give some people regular 9-5 schedules? All of the above questions will decrease the strict optimality of the solution, but increase the happiness and long term retention of your workforce. Thus, the question really become, how much do each of these cost in terms of optimality and what are the tradeoffs. We've found that developing a very fast heuristic algorithm for the NSP allows people to iterate quickly on these types of questions (even though it's not quite as optimal as a SAT solver). We use a greedy algorithm with a heuristic that is relatively specific to our problem domain to ensure that we have a reasonable combination of speed and optimality.

MatthewWilkes 7y ago

DevRel was a mistake.

lonelappde 7y ago

Why was the title changed to something less informative?

coleca 7y ago

Interesting project, I'd like to see it take into account decades of ambiguous union contracts, past practices, seniority, preferences, time off requests, preferences, training and certification levels, and not to mention the various local, state and federal labor laws. Scheduling isn't an easy problem to solve in the real world vs the lab where there are far less constraints and consequences for getting it wrong. Kronos (kronos.com) is the recognized leader in this space and even their software has a hard time keeping it all straight.

cerved 7y ago
CP solvers are excellent at handling side constraints, at least as long as they can be expressed as a boolean, discrete or linear relation.

whatever1 7y ago

IBM makes an even faster (than google or) cp optimizer https://arxiv.org/pdf/1909.08247.pdf https://arxiv.org/pdf/1909.08247.pdf

deleted 7y ago

[deleted]

dzink 7y ago

We had to find a solution for doctors to manage 22 different peers distributing 30 shifts a month. The schedule had to abide by each employees vacation requests and distributed undesirable shifts like weekends and holidays in some equitable manner, and be easily interpreted by staff. The solution was an excel spreadsheet with a lot of auto-fill logic and formulas to show shift and burden counts for each doctor so the person managing the sheet could move around shifts when needed and ensure equitable distribution still remained. Excel really helped where python and other tools would require a lot more code and be a lot less flexible to operator changes.

hipjiveguy 7y ago
Since it's a spreadsheet, is there any way you can share it? I assume the Dr's names could be easily changed so it's generic?

froindt 7y ago

I have been building a employee scheduling system in a factory environment. New employees need to be trained on machines, for a certain number of shifts, with a limit of how many employees can train on a machine at a time. A question becomes "how many new employees could we handle?". I looked at some solutions, but landed on an Excel spreadsheet with a small macro for spreadsheet setup, conditional formatting to call out an employee being allocated to 2 positions on the same shift, and a visual way to show for each operator, how long it takes to be fully trained. HR or a manager can setup training schedules by manually allocating people to training slots. There were some constraints the business wanted (train on machine #1 before #2, do 2 days of training if you haven't already trained on _x_ machine). They would have been hard to accommodate in a way the end user could configure, so I have a notes section they can fill in (and they have to manually observe these constraints). Totally open to other ideas people have on how to approach the proble.

mushufasa 7y ago
This sounds like a good solution to me. I can imagine some HN readers might comment 'ew Excel!' but it truly is the right tool for something where you have to transparently demonstrate the logic to non-technical stakeholders in a way they can easily edit and adapt. Of course, you could build or buy a web app that handles this specific scenario more powerfully and scaleably, but if this is a quarterly problem rather than a everyday problem then the additional overhead of the different interface / logins may not be worthwhile. My only comments would be 1) macros are too hard for nontechnical users in my experience, even just w/r/t setup (excel prompts you a security warning to enable macros that is scary). I think you could maybe do this using the what-if analysis tables, simple ifelse formulas, and conditional formatting. 2) another improvement might be a cloud-based version where there is a link at which others can easily view + collaborate, like Google Sheets or Airtable. I think Excel is supposed to have this feature as part of the 365 subscription but I've never used it.
cerved 7y ago
Using Excel sounds like a pain to maintain but if it works it works. Your problem sounds like a JSP (job shop scheduling problem). If it is you could use MiniZinc https://www.minizinc.org/ https://www.minizinc.org/ and look at Håkan Kjellstrans MiniZinc page http://www.hakank.org/minizinc/ http://www.hakank.org/minizinc/, it has a couple of different JSP models.

aerovistae 7y ago

What is this? There's no introduction

cerved 7y ago
It's an example model of how to use the or-tools CP-SAT solver to solve employee scheduling problems. It's part of the or-tools library which is a framework for solving scheduling, routing and other NP-hard discrete optimization problems https://developers.google.com/optimization/introduction/overview https://developers.google.com/optimization/introduction/over...

JustSomeNobody 7y ago

This doesn’t take into account certain people are more productive when paired up (and less productive when paired with other people).

cerved 7y ago
No it doesn't. It's an extremely basic model to introduce the CP-SAT solver to people with little to no experience in scheduling problems or CP. Pairing up people based on such criteria requires turning the problem into a MOCO or incorporating it with the current objective function.

mcguire 7y ago

"OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions."

closeparen 7y ago

My team used to have an absolutely wild script for oncall scheduling. People would enter their availability weeks, and then we'd run a genetic algorithm, scoring the fitness of each schedule "offspring" according to the number of availabilities violated and then making random mutations to the most promising. It would slam CPU for several hours and still produce clearly ridiculous solutions. Brute force would have been better. I'll have to play with this.

dghughes 7y ago

The problem with employee schedules where employees work in shifts is communication. At one place it was done using Excel as I'm sure it's still done today in many organizations. You always have two people trading shifts but never telling anyone. Then the one who was supposed to work doesn't show up they forgot they traded shifts. Human nature is half the problem.

jonbaer 7y ago

Maybe a little OT, but why aren't the OR-tools in general more focused (or more "marketed") towards GPU/TPU clouds since they seem like the exact problems which they are made for? More focus seems to be towards TF/PT/NN and not the real problems like what OR-tools and solvers in general push for.

mochomocha 7y ago
Typical algorithms solving combinatorial problems are usually heavily branching, so not so much vectorizable. For example for a branch-and-cut MIP solver, you could run the LP-relaxed problems on GPU, but most of the logic lives in branching and cutting heuristics that are much harder to parallelize.
7thaccount 7y ago
A lot of OR stuff can be parallelized, but it isn't a panacea. Those techniques don't necessarily get you the best answer sometimes. My company does some massive optimization problems and although we have lots of cores for all the simulations, any one is pretty much single core + a lot of RAM. It doesn't work well on GPU like some heuristic optimization problems can. Edit: Someone smarter than me says it better below :)
cerved 7y ago
For starters, CP and SAT are based on integers and boolean variables. Secondly, local search and systematic search are just no way near parallelizable to the degree required to see gains running GPU/TPU.

mighty_plant 7y ago

Google or-tools are quite fun although a little bit of a pain to setup and get started at least if you want to use the JVM and support different OS. Just to share a little anecdote about my use case: The department I work in consists of about 40 developers and once a year we had a day together just to form new teams in a self organized manner. Management wanted about one third of a team to move to a different team to spread and gather knowledge but completely backed off during that day. We had a special coach and scrum masters supporting us but still it was very exhausting and a lot of the developers didn't like it. The devs that showed motivation to change teams were more or less forced to go to the teams which were disliked the most (either because of their domain or the already present members). So in the end there was not much rotation and the whole thing was quite expensive so that this year it was cancelled. That's when I started to use Google or-Tools to write a little tool that suggests teams based on some constraints like size, at least one experienced dev / software architect per team and an optimization function based on preferences of each dev for a certain domain as well as their sympathy towards other devs When I announced it it got almost no attention and was dismissed as "inhuman".

IndexPointer 7y ago

Well now I want to spend a few hours using it to solve the peaceable queens problem: https://youtu.be/IN1fPtY9jYg https://youtu.be/IN1fPtY9jYg

cerved 7y ago
Sounds similar to n-Queens, check out http://www.hakank.org/google_or_tools/nqueens.py http://www.hakank.org/google_or_tools/nqueens.py http://www.hakank.org/google_or_tools/nqueens2.py http://www.hakank.org/google_or_tools/nqueens2.py http://www.hakank.org/google_or_tools/nqueens3.py http://www.hakank.org/google_or_tools/nqueens3.py for inspiration
- hakank 7y ago
  Actually, the Peaceable Army (or Armies) of Queens problem is a separate problem and much harder than the n-queens problem. Here is a MiniZinc model: http://hakank.org/minizinc/peaceableArmyOfQueens.mzn http://hakank.org/minizinc/peaceableArmyOfQueens.mzn , and a Picat model: http://hakank.org/picat/peaceableArmyOfQueens.pi http://hakank.org/picat/peaceableArmyOfQueens.pi (Also: Thanks for your links to my site.)

westurner 7y ago

From "Ask HN: What algorithms should I research to code a conference scheduling app" https://news.ycombinator.com/item?id=15267804 https://news.ycombinator.com/item?id=15267804 : > Resource scheduling, CSP (Constraint Satisfaction programming) CSP: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem https://en.wikipedia.org/wiki/Constraint_satisfaction_proble... Scheduling (production processes): https://en.wikipedia.org/wiki/Scheduling_(production_processes) https://en.wikipedia.org/wiki/Scheduling_(production_process... Scheduling (computing): https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Scheduling_(computing) ... To an OS, a process thread has a priority and sometimes a CPU affinity. From http://markmail.org/search/?q=list%3Aorg.python.omaha+pyschedule#query:list%3Aorg.python.omaha%20pyschedule+page:1+mid:enenp7smhvr5636g+state:results http://markmail.org/search/?q=list%3Aorg.python.omaha+pysche... : Pyschedule: - Src: https://github.com/timnon/pyschedule https://github.com/timnon/pyschedule From https://github.com/timnon/pyschedule https://github.com/timnon/pyschedule : > pyschedule is python package to compute resource-constrained task schedules. Some features are: - precedence relations: e.g. task A should be done before task B - resource requirements: e.g. task A can be done by resource X or Y - resource capacities: e.g. resource X can only process a few tasks Previous use-cases include: - school timetables: assign teachers to classes - beer brewing: assign equipment to brewing stages - sport schedules: assign stadiums to games ... https://en.wikipedia.org/wiki/Slurm_Workload_Manager https://en.wikipedia.org/wiki/Slurm_Workload_Manager : > Slurm is the workload manager on about 60% of the TOP500 supercomputers.[1] Slurm uses a best fit algorithm based on Hilbert curve scheduling or fat tree network topology in order to optimize locality of task assignments on parallel computers.[2] ... https://en.wikipedia.org/wiki/Hilbert_curve_scheduling https://en.wikipedia.org/wiki/Hilbert_curve_scheduling : > [...] the Hilbert curve scheduling method turns a multidimensional task allocation problem into a one-dimensional space filling problem using Hilbert curves, assigning related tasks to locations with higher levels of proximity.[1] Other space filling curves may also be used in various computing applications for similar purposes.[2]

tracker1 7y ago

Now do that with a few thousand employees, vacation request ranking/status and three different sets of thousands of pages of union contracts. The above is something I actually worked on before.. The bitter irony, is they all just traded their vacation weeks as it came up anyway.

reportgunner 7y ago

This looks nice but actually doesn't adress the actual challenges of scheduling. It's rather easy to generate a schedule and most of the feasible variants are available online already (there aren't infinite possibilities on how to schedule shifts) - you fit it to a 7 day or a 28 day (or a multiple of 7) cycle and then copy paste. The scheduling challenges occur when people need to take unexpected vacations or during vacation period when staffing is low. Another challenge is the skill level of the individual employees which is usually not binary - can do work / cannot do work - since employees come to work to perform tasks and they don't always learn all of the tasks the first day.