Scheduling two jobs with fixed and nonfixed routes (Q1316587)

The paper continues the complexity study of scheduling problems with a fixed number of jobs. The shop-scheduling model with two jobs and \(m\) machines is considered under the condition that the machine order is fixed in advance for the first job and nonfixed for the second job. This model belongs to the class of the so-called nonhomogeneous shop (or super shop) models which have been only recently investigated. The problems of makespan and mean flow time minimization are proved to be NP-hard if operation preemption is forbidden. In the case of preemption allowance for any given regular criterion the \(O(n_ *)\) algorithm is proposed. Here, \(n_ *\) is the maximum number of operations per job. The paper is well written and is of interest to specialists in the field of scheduling theory.