Complexity of scheduling few types of jobs on related and unrelated machines

What the paper says

Abstract 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 }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>|</mml:mo> <mml:mi>H</mml:mi> <mml:mi>M</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> ) 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 }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>|</mml:mo> <mml:mi>H</mml:mi> <mml:mi>M</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> ), we show that if the largest job size $$p_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:math> or the number of jobs n is polynomially bounded in the instance size | I |, there are algorithms with complexity $$|I|^{{{\,\mathrm{\textrm{poly}}\,}}(k)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>I</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>poly</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> . Our main result is that this is unlikely to be improved because $$Q||C_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> is $$\mathsf {W[1]}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>W</mml:mi> <mml:mo>[</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> -hard parameterized by k already when n , $$p_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>p</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:math> , and the numbers describing the machine speeds are polynomial in | I |; the same holds for $$R||C_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> (without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives $$\ell _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> -norm minimization of the load vector and, partially, sum of weighted completion times $$\sum w_j C_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∑</mml:mo> <mml:msub> <mml:mi>w</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> </mml:math> . Along the way, we answer affirmatively the question whether makespan minimization on identical machines ( $$P||C_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> ) is fixed-parameter tractable parameterized by k , extending our understanding of this fundamental problem. Together with our hardness results for $$Q||C_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>|</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mi>C</mml:mi> <mml:mo>max</mml:mo> </mml:msub> </mml:mrow> </mml:math> , this implies that the complexity of $$P|HM|C_{\max }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>|</mml:mo> <mml:mi>H</mml:mi>