This paper deals with the n/m/J/Cmax problem of optimal makespan scheduling n jobs with fixed routines on m machines. It is shown that the 3/m/J/Cmax problem with identical routines of jobs and the 3/5/J/Cmax problem are NP-hard. The same results are obtained for the 3/m/J/ΣCi 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(r2log2r) algorithm, otherwise. Here the parameter r denotes the maximal number of operations per job.
