Employee Scheduling

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.

Of course optimization went back at least to Newton and his work to find the shape of a frictionless wire that would let a bead slide down in least time. That problem was a seed for the field of calculus of variations and later deterministic optimal control.

But the optimization of operations research was different, e.g., less central use of calculus: Some of the surprising history is in a book review at

https://www.jstor.org/stable/2975180?seq=1#page_scan_tab_con...

And that is not really the beginnings of such things since there was the Kantorovich work on the cutting stock problem.

In that book review will see that linear programming (LP) had a launch as a big splash. Broadly it appeared that LP was so close to so many important practical problems -- military, commercial, maybe more -- that it was bound to become a big thing for a long time. And, can check, IIRC several Nobel prizes in Economics were given for LP and more topics in optimization applied to economics.

And there are connections with two sided optimization, i.e., the theory of two person games (e.g., paper, scissors, rock) since the basic saddle point result, IIRC first proved by von Neumann, follows easily from the duality part of basic theory of LP. So, again LP looked good.

Can't leave out the Hugh Everett work: He had a company around DC working on military problems -- best allocation of resources. Everett's theorem is a cute version of Lagrange multipliers and supposedly the foundation of his Lambda Corporation. Yes, that Everett, physics student of J. Wheeler where Everett worked up the many worlds interpretation of quantum mechanics.

Operations research had a more general big push during WWII, e.g., with some of the work of F. Dyson.

So, by the 1950s, it looked like operations research (OR) and its tools of optimization, especially LP, were to be big things.

Problems:

(1) Real Problems. What real problems were to be solved? Too commonly the problems were not really linear or were linear but linear integer (which led to the question of P versus NP).

(2) Data. Too often it was a struggle to get the needed real data.

(3) Software. The IBM OSL I mentioned was good software, and so are C-PLEX, Gurobi, and more, but in the 1950s the software situation was grim.

(4) Computing. The 1950s computers, e.g., the IBM 709, were clumsy to use, slow, and expensive.

Then (1)-(4) too easily resulted in projects with not so good fits with reality, over budget, and later than promised. Reputation fell.

Another problem, no surprise, was that the real business problem commonly evolved faster than the optimization software could keep up.

But for selected and sufficiently valuable applications, e.g., running an oil refinery, by 1970 LP could be a big money maker.

There were claims that companies that mixed animal feed did well with LP in, say, the 1970s or so.

In the 1980s the situation on LP software and computing was good enough to permit some better -- project time and budget -- results on real problems.

By the 1980s, B-school accreditation called for a course in LP. So, a lot of B-school students got a good introduction to LP.

But there was very little down to essentially no instruction to turn out well skilled professionals in OR or LP. The college profs concentrated on publishing papers, e.g., about P versus NP, and were discouraged from working on real, non-academic problems from outside academics, i.e., were not like MDs in medical teaching/research hospitals who were also clinical and professional. So, the OR/LP workers who were available still needed some years of hands on experience to become competent professionals for important practical applications.

The standard attitude in the C-suites was a special case of C-suite attitudes more generally -- don't spend money on chancy, risky stuff. Instead, if there is to be a development project, then time, budget, good ROI, etc. needed to be reliable. So, in the C-suites, LP and OR got reputations as "dead fields", flops. Or maybe no middle manager ever got fired declining to pursue an OR/LP project. Neither the C-suite nor a middle manager wanted to have their career at risk from an OR/LP project they didn't understand.

The problem of P versus NP also hurt: Or, the dream was that in business we should need only to formulate an optimization problem, type that into some software to get the problem ready for some solver software, and then have the solver produce an optimal solution quickly and reliably. Well, with the P versus NP issue, we saw that at least for now such a solver was asking for too much.

[My experience was that it was usually necessary and effective to take the problems one by one and exploit special structure.]

Giving up that way was mostly a mistake: If the real business problem is a $100 million project, an optimal solution might save $15 million, the problem is a case of NP-complete so that saving all the $15 million to the last penny, guaranteed, in reasonable time, is also in this particular case (not necessarily the worst case of the P versus NP issue) not reasonable but saving $14 million is reasonable, then still commonly people regarded the challenge of P versus NP and showing that anything about optimization for the real problem was unreasonable and would also believe that the challenge of P versus NP meant that the $14 million was also beyond hope. People just gave up.

But in broad terms from 100,000 feet up, the original observation that business needs optimization was correct then and still, now. For such problems, a lot of what has long been known in LP and optimization more generally is uniquely powerful, relevant stuff.

So, there's money to be saved.

The main question is, do C-suites want to fund the relevant projects?

My guess is that the C-suites and middle managers have not changed much and, no, rarely want to fund the relevant projects.

See also the story of Staffjoy mentioned in another comment (https://news.ycombinator.com/item?id=22583653) YC fellowship, they couldn't find a market, and shut down: https://hn.algolia.com/?q=staffjoy

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.

I suspect that the big thing there is negotiation and social skills. It is not just about making schedule, it is also about talking with people, making them compromise, making them happy despite not gaining everything they wanted, explaining them that what they wanted they wont like actually, making them understand others too.