The complexity of shop-scheduling problems with two or three jobs (Q1178530)

The author discusses job-shop, flow-shop and open-shop scheduling problems with two or three jobs. The performance criteria considered are the makespan, \(C_{max}\), mean flowtime and general regular criteria. Up to now, most of the scheduling models restrict the number of machines, but not the number of jobs. In this article the opposite approach is analyzed. The number of jobs is restricted to two or three and the number of machines may vary, but there are always more machines than jobs included. The results of the article are as follows. NP-hardness is proved for \(3| 5| J| C_{max}\) and \(3| 5| J, Pr| c_{max}\), both problems are job-shop problems with 3 jobs and 5 machines and the makespan as performance criterion, in the first problem job preemption is forbidden, whereas in the second problem jobs may be splitted. Next, NP-hardness is proved for \(3| m| F| C_{max}\), here a flow-job system with 3 jobs and an arbitrary number of machines is considered. Then NP-hardness is proved for \(3| 5| J|\sum C_ i\) and \(3| m| F|\sum C_ i\), both problems include the mean flowtime as performance criterion. Finally, some problems with only two jobs and a general regular performance measure, \(\Phi\), are discussed. Polynomial algorithms are developed for \(2| m| J|\Phi\), \(2| m| J\), \(Pr|\Phi\), \(2| m| F|\Phi\) and \(2| m| F\), \(Pr|\Phi\). These four problems can be transformed into a problem of finding shortest paths in special directed graphs.