.png){kind=icon}
.png){kind=icon}
返回
Single Machine Scheduling with Precedence Constraints and Bounded Maximum Delay Value
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-026-01411-w.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
考虑具有最小、精确或最大延迟的优先约束下，单机调度问题在最小化完工时间方面的参数化复杂性。我们研究了这些问题相对于最大延迟值ℓmax的参数化复杂性，并补充了该领域的成果。我们证明，在具有精确延迟或最小延迟的问题的几种特殊情况中，相对于ℓmax是para-NP-complete或XNLP-hard的。特别是，在优先链和单位加工时间的情况下，我们确定在精确延迟下该问题是para-NP-complete，而在最小延迟下是XNLP-hard，但在最大延迟下是多项式时间可解的。随后，我们研究了ℓmax与优先图宽度的组合，并试图为三种类型的延迟绘制固定参数可解性的界限。我们表明，对于这些组合参数，在链的情况下，最大延迟的问题是多项式时间可解的，而对于最小延迟，即使具有单位加工时间和仅两个可用的延迟阈值，它也是XNLP-complete。如果假设一般优先图，我们还确定在最小延迟下该问题是XNLP-complete，即使对于单位加工时间和相等延迟，而对于精确延迟，它属于FPT。最后，我们考虑具有时间窗口的问题，并针对具有无界加工时间、一般优先图和所有类型延迟的问题，提出了一个相对于ℓmax与任务最大松弛的组合参数的固定参数可解算法。
Keyword:
Scheduling
Parameterized complexity
Precedence delays
查看更多机构