Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Employee Scheduling

developers.google.com

Post reply on HN
Print view View original

61–70 of 137 posts

Re: Employee Scheduling

#61

Post by petters »

microcolonel wrote: post #28
petters wrote: post #15

State of the art for employee scheduling seems to be column generation; see benchmarks here: 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/line...

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?

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.

Re: Employee Scheduling

#62

Post by asdfasgasdgasdg »

cerved wrote: post #58
asdfasgasdgasdg wrote: post #48

Earlier quoted context omitted.

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 que…

Interesting. I imagine this was for exhaustive search? If 100ms is too long it sounds like a CP solver might be the wrong tool for the job.

Actually, we tried both exhaustive search and sufficient search (where we had a soft-deadline and accepted the best solution reached within the deadline). Even with this dark launch found queries in our stream that had unacceptable delays. We were in contact with the team through the development process, so we at least had some reason for belief that we were using best practices. And you're right that ultimately the CP solver wasn't the right tool for this job -- simplifying the problem and giving up some capabilities was the solution. We had hoped that a general solution would be feasible, as that would allow expressing some things efficiently which we couldn't in our existing setup. But it was not to be.

Re: Employee Scheduling

#63

Post by johnjwang »

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.

Re: Employee Scheduling

#65

Post by 6510 »

simulate wrote: post #53

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/ and here are some other optimization examples: https://forio.com/products/epicenter/example-applications/

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

Re: Employee Scheduling

#66

Post by duxup »

cosmodisk wrote: post #60
duxup wrote: post #54

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 priorit…

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

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.

Re: Employee Scheduling

#68

Post by coleca »

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.

Re: Employee Scheduling

#69

Post by toxik »

6510 wrote: post #65
simulate wrote: post #53

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/ and here are some other optimization examples: https://forio.com/products/epicenter/example-applications/

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

Turns out Gloria is an incredibly hard worker.

Re: Employee Scheduling

#70

Post by srean »

nappy-doo wrote: post #11
michaelt wrote: post #6

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.

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://www…

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.
Post reply on HN