Employee Scheduling

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.

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/

Many small-medium businesses wouldn't want such a tool because it eliminates managerial leverage. I'm not being snide either. In many places I've worked the boss's tyrannical power over the schedule was a form of control.

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.

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)