THE COMPLEXITY OF SHOP-SCHEDULING PROBLEMS WITH 2 OR 3 JOBS

This paper deals with the n/m/J/C(max) problem of optimal makespan scheduling n jobs with fixed routines on m machines. It is shown that the 3/m/J/C(max) problem with identical routines of jobs and the 3/5/J/C(max) problem are NP-hard. The same results are obtained for the 3/m/J/SIGMA-C(i) problem of minimizing mean flow time of three jobs on m machines. The problem of optimal scheduling of two jobs with any regular criterion is shown to be solved by an O(r3) algorithm if preemptions of operations are allowed and by an O(r2 log2r) algorithm, otherwise. Here the parameter r denotes the maximal number of operations per job.