Scheduling is in the news again, so let's talk a little bit about the science behind it, since apparently a lot of people forgot that it even exists.

The canonical textbook is this beauty, here in all of its '70s splendor: Alex Rinnooy Kan: Machine Scheduling Problems, 1976.

Let's have a look inside the book. What is scheduling? In the shortest form, this: shepherding a bunch of jobs ("chains of operation") thru a production facility with multiple machines, from start to finish. And yes, that's a network flow.

Network flow problems are a variant of traveling salesman problems, and as it turns out, Alex Rinnooy Kan was also the coauthor of a book on the TSP, along with other stalwarts in the field of combinatorial optimization, Gene Lawler among them. I'll get back to that later.

A look at the table of contents gives us the types of problems studied: the nomenclature means:
n jobs to be performed on m machines (here m=1) under constraints with an objective function. (In most notations, the n is dropped.)

Constraints can come in all kinds of forms and convolutions, here is just a small subset. Also, the type of a scheduling problem is important: jobs need to be scheduled at a single machine or sequenced over multiple machines in a fixed or a free processing order.

Even more interesting is the list of proposed solution algorithms even in 1976, recognizing that most scheduling problems are complex in the computational complexity sense of the term. Heuristics are common and machine learning algorithms have a long history in the field.

So if you read something about "complexity economics" it should hark back to original machine scheduling problems, since that where the term originates.

Here's an older thread on how we moved from machine scheduling to machine learning. https://twitter.com/oliverbeige/status/1249430469202137094?s=20