# Who was the first to define Flow Shop / Job Shop problem?

I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my master thesis.

I'm guessing that there may be no author of this problems but this information also would help me a lot.

• – Auberon May 14 '16 at 16:08
• It was already mention in Conway, Maxwell, and Miller (1967) about ten years earlier. And google scholar shows even earlier works. – Dcortez May 14 '16 at 16:21
• I think it's not important to refer to original definition (most likely there is none), but to a work that defines the problem clearly and is relevant to your thesis. Most likely you're going to claim that Job Flow is NP-complete in your thesis and I think the paper mentioned above is a nice one to support that claim. – Auberon May 14 '16 at 17:36

Coffman and Demming's famous Operating Systems Theory, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" of Job Shop scheduling. In the next paragraph, they introduce Flow Shop scheduling as a specialization of Job Shop, and cite

Johnson, S.M.; "Optimal two- and three-stage production schedules with set-up times included." Naval Research Logistics Quarterly, 1(1):61-68, 1954.

Naval Research Logistics Quarterly seems to be a Wiley pay-walled journal, but my library has a subscription to it. Johnson's paper begins:

Let us consider a typical multistage problem formulated in the following terms by R. Bellman:

"There are n items which must go through one production stage or machine and then a second one. There is only one machine for each stage. At most one item can be on a machine at a given time.

"Consider $2n$ constants $A_i, B_i, i = 1, 2, \cdots, n$. These are positive but otherwise arbitrary. Let $A_i$ be the setup time plus work time of the $i$th item on the first machine, and $B_i$ the corresponding time on the second machine. We seek the optimal schedule of items in order to minimize the total elapsed time."

He doesn't give the full reference to Bellman. Johnson's paper extends the definition in the obvious way to 3 machines.