.png){kind=icon}
返回
Single-machine scheduling of multiple projects with controllable processing times
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2023.01.026.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper studies the single-machine multiple-project scheduling problem with controllable processing times, in which the cost of a project refers to the total compression cost of its jobs plus the weighted number of tardy jobs in a schedule satisfying some given precedence constraints. It involves four specific problems: (i) minimizing the total cost of an arbitrary number of projects, (ii) being the same as (i) except the jobs from the same project having a common due date, (iii) having a fixed number of projects and minimizing the cost of one project subject to the cost of each of other projects not exceeding a given threshold, and (iv) being the same as (iii) except all jobs having identical weights. We show that a special version of (i) in which each project has only two jobs and all jobs have unit weights and cannot be compressed is strongly NP-hard (it implies the strong NP-hardness of (i)), (ii) is weakly NP-hard and admits a pseudo-polynomial algorithm and a fully polynomial time approximation scheme, (iii) is pseudopolynomially solvable by a two-phase transformation, and (iv) is weakly NP-hard even if there are only two projects and all jobs have identical maximum compression amounts and identical processing times. (c) 2023 Elsevier B.V. All rights reserved.
Keyword:
Scheduling
Controllable processing times
Multiple projects
Compression cost
Pseudo -polynomial algorithm
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容