Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/323374 
Year of Publication: 
2025
Citation: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 28 [Issue:] 1 [Publisher:] Springer US [Place:] New York [Year:] 2025 [Pages:] 139-156
Publisher: 
Springer US, New York
Abstract: 
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 ( QMmax) 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 ( RMmax), we show that if the largest job size pmaxor the number of jobs n is polynomially bounded in the instance size Ithere are algorithms with complexityoly(k). Our main result is that this is unlikely to be improved because Qmaxis W[1]-hard parameterized by k already when n , pmax, and the numbers describing the machine speeds are polynomial in Ithe same holds for Rmax(without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives ℓ2-norm minimization of the load vector and, partially, sum of weighted completion times ∑wjCj. Along the way, we answer affirmatively the question whether makespan minimization on identical machines ( Pmax) is fixed-parameter tractable parameterized by k , extending our understanding of this fundamental problem. Together with our hardness results for Qmax, this implies that the complexity of PMmaxis the only remaining open case.
Subjects: 
High-multiplicity jobs
Cutting stock
Hardness
Parameterized complexity
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version
Appears in Collections:

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.