We study the problem of scheduling N independent jobs in a job-shop environment. Each job must be processed on at most M machines according to individual routes. The objective is to minimise the maximum completion time of the jobs. First, the job-shop problem is reduced to a flow-shop problem with job precedence constraints. Then, an extension of Johnson's rule is defined to solve it. The optimality of the extended Johnson's rule is proved for two machine job-shop problems and the rule efficiency for some three and four machine job-shop problems is shown.
