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

作     者：Koutecky, Martin Zink, Johannes 

作者机构：Charles Univ Prague Prague Czech Republic Univ Wurzburg Wurzburg Germany 

出 版 物：《JOURNAL OF SCHEDULING》 (J. Scheduling)

年 卷 期：2025年第28卷第1期

页      面：139-156页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0802[工学-机械工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Charles University project UNCE [24/SCI/008] GACR [24-10306 S] DFG [Wo758/11-1] Projekt DEAL 

主　　题：High-multiplicity jobs Cutting stock Hardness Parameterized complexity 

摘      要：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|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q|HM|C_{\max }$$\end{document}) 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|Cmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R|HM|C_{\max }$$\end{document}), we show that if the largest job size pmax\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\max }$$\end{document} or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity |I|poly(k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|I|{{{\,\ma