The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general -hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines (
$$Q|HM|C_{\max }$$
Q
|
H
M
|
C
max
) is -hard already with 6 job types, and that the related Cutting Stock problem is -hard already with 8 item types. For the more general unrelated machines model (
$$R|HM|C_{\max }$$
R
|
H
M
|
C
max
), we show that if the largest job size
$$p_{\max }$$
p
max
or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity
$$|I|^{{{\,\mathrm{\textrm{poly}}\,}}(k)}$$
|
I
|
poly
(
k
)
. Our main result is that this is unlikely to be improved because
$$Q||C_{\max }$$
Q
|
|
C
max
is
$$\mathsf {W[1]}$$
W
[
1
]
-hard parameterized by k already when n,
$$p_{\max }$$
p
max
, and the numbers describing the machine speeds are polynomial in |I|; the same holds for
$$R||C_{\max }$$
R
|
|
C
max
(without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives
$$\ell _2$$
ℓ
2
-norm minimization of the load vector and, partially, sum of weighted completion times
$$\sum w_j C_j$$
∑
w
j
C
j
. Along the way, we answer affirmatively the question whether makespan minimization on identical machines (
$$P||C_{\max }$$
P
|
|
C
max
) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for
$$Q||C_{\max }$$
Q
|
|
C
max
, this implies that the complexity of
$$P|HM|C_{\max }$$
P
|
H
M
|
C
max
is the only remaining open case.
