Flow-shop scheduling

Flow-shop scheduling is an optimization problem in computer science and operations research.

In the specific variant known as flow-shop scheduling, each job contains exactly m operations.

Flow-shop scheduling may apply as well to production facilities as to computing designs.

A special type of flow-shop scheduling problem is the permutation flow-shop scheduling problem in which the processing order of the jobs on the resources is the same for each subsequent step of processing.

In the standard three-field notation for optimal-job-scheduling problems, the flow-shop variant is denoted by F in the first field.

Problem definition implies that this job order is exactly the same for each machine.

The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan.

The flow shop contains n jobs simultaneously available at time zero and to be processed by two machines arranged in series with unlimited storage in between them.

The Johnson's rule for scheduling jobs in two-machine flow shop is given below.