Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/323374 
Erscheinungsjahr: 
2025
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 28 [Issue:] 1 [Publisher:] Springer US [Place:] New York, NY [Year:] 2025 [Pages:] 139-156
Verlag: 
Springer US, New York, NY
Zusammenfassung: 
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 Q
Cmaxis W[1]-hard parameterized by k already when n , pmax, and the numbers describing the machine speeds are polynomial in Ithe same holds for R
Cmax(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 ( P
Cmax) is fixed-parameter tractable parameterized by k , extending our understanding of this fundamental problem. Together with our hardness results for Q
Cmax, this implies that the complexity of PMmaxis the only remaining open case.
Schlagwörter: 
High-multiplicity jobs
Cutting stock
Hardness
Parameterized complexity
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.