Hacker News Reader

Comment by philip1209 | Hacker News Reader

ML is more statistical - good for forecasting. We were doing optimization mathematics with hard constraints for the scheduling.

One of the issues that we encountered was that a generalized algorithm was tough. Different companies had different requirements for an algorithm, and it started to feel like a consulting company. For instance, if a big box retailer would rather be slightly underscheduled at peak time rather than adding additional employees (and being over-scheduled near the peak time). A high-end boutique retailer (like a diamond shop) might be the opposite - each sales brings in so much money that they overstaff at non-peak hours so that they can service customers during peak hours.

View on HN

As a consultant, sounds like my bread and butter (specialized problem, no generalized tools).

For a product company, sounds like a nightmare - no one's paying you by the hour to meet their unique requirements.

Thanks for sharing your story!

Sounds like a machine learning problem. The dependent variable is profit, not budget.

scheduling is a classic mgmt. science problem.

But once you get into the modeling of how many customers come in at what hour and how likely they are to purchase how much conditioned on the staff present, it's a learning problem.

It's a pipeline. Check out this [1] paper about the Taco Bell scheduling system. It's forecasting (stats, but would probably be called ML if paper wasn't in 1998) -> queuing theory (markov chains, sometimes formula-based, sometimes simulated) -> scheduling (normally mixed integer linear programming)

[1] http://pubsonline.informs.org/doi/abs/10.1287/inte.28.1.75

Eh, what the heck, with enough layers (and enough data) a neural network will eventually create a neuron for each of those tasks. Just let it train for a few years.

BTW, that was a joke.

Not really machine learning.

https://en.wikipedia.org/wiki/Nurse_scheduling_problem

Above is a nice example. There has been some nice contests with the above problem and the ILP solvers work extremely fast and great and solve them to optimality. Although Staffjoy constraints might have been more general.

Either way you could easily attack any custom problem with an ILP solver. It depends how long it would take to get a feasible solution and then how long to minimize the costs or fit the budget.

In order to speed up the solver you might use ML but that would require previous data. Probably the only way to speed up the solver is to learn it through reinforcement learning on a batch of data. Takes time and time and time. Not to mention that your ILP solver has to be equipped to merge with any ML machinery you are using.

But deciding how many nurses to have at what time, based on the probability of how many and what kind of patients and the likelihood of a good medical outcome is a different problem.

It is, but saying it's machine learning hides the combinatorial issues and combinatorial search that has to happen. Machine learning model can't replace the necessity for search.

Scheduling problem (the general one) maps easily to the vehicle routing problem. Vehicles are routed and service customers. On-demand requirements and scheduling are probably easier to conceptualize in that framework (think Uber but with ride-sharing bus sized cars, or team picking up and delivering food from restaurants to locations, or repairmen doing stuff at people homes).

All needs combinatorial search and machine learning is only one little piece of the puzzle.

I usually say it the other way -- optimization is just one part of machine learning.

ML includes optimization/search, dimensionality reduction (aka unsupervised learning), prediction (aka supervised learning), and reinforcement learning. And I'm probably forgetting a category.

ML does not include integer linear programming (nothing learnable there) and similar mathematical optimizations. ML can be a part of it but is not integral to it. Just like finding the shortest paths between two points does not include ML. ML can be used to learn the weights through time (traffic sensitive routing) but the search part is separated from it.

IMO, ML is nowhere close to useful in these problems when most of the clients just use pen and paper. It should be fairly easy to beat that with some simple search heuristics.

Simple is better than complex. I agree with that.

Check out slides 43-46 here from a talk I previously gave: https://speakerdeck.com/philipithomas/decision-algorithms-in...

In the old days, everything was a hard constraint. However, free trial users don't always put in problems that are solvable. I would get paged at 4AM about infeasible models, only to discover things like "this employee has zero availability but a minimum of 40 hours per week of work".

So, we turned into more of a "scoring" system where all minimums were soft constraints (e.g. minimum hours per week) whose violations caused a large point decrease [1]. Maximums were a hard constraint. The system made it impossible to input an infeasible model, and worked fairly well.

Splitting the scheduling problem into separate steps (forecast->unassigned shifts, then unassigned->assigned shifts) also sped up the algorithms (and allowed for people to create unassigned shift templates).

[1] https://en.wikipedia.org/wiki/Big_M_method

Isn't it just an ILP (Integer linear programming) problem? You want to minimize the cost while satisfying the scheduling problem.

Reply on news.ycombinator.com