Author
Listed:
- Martin Koutecký
(Charles University)
- Johannes Zink
(Universität Würzburg)
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 NP-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 NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-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.
Suggested Citation
Martin Koutecký & Johannes Zink, 2025.
"Complexity of scheduling few types of jobs on related and unrelated machines,"
Journal of Scheduling, Springer, vol. 28(1), pages 139-156, February.
Handle:
RePEc:spr:jsched:v:28:y:2025:i:1:d:10.1007_s10951-024-00827-8
DOI: 10.1007/s10951-024-00827-8
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:28:y:2025:i:1:d:10.1007_s10951-024-00827-8. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.