Suppose there are n jobs that require processing on m machines.

Each job must be processed by machine 1, then by machine 2, . . . , and finally by machine m. Each machine can work on at most one job at a time and once it begins work on a job it mustwork on it until completion, without interruption. The amount of time machine j must process job i is denoted pij ≥ 0 (for i  1, 2, . . . , n and j  1, 2, . . . , m). Further suppose that once the processing of a job is completed on machine j , its processing must begin immediately on machine j+1 (for j ≤ m−1).

This is a flow shop with no wait-in-process.

Show that the problem of sequencing the jobs so that the last job is completed as early as possible can be formulated as an (n + 1)-city TSP. Specifically, show how the dij values for the TSP can be expressed in terms of the pij values.