.png){kind=icon}
返回
An approximation scheme for rejection-allowed single-machine rescheduling
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2020.106574.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We study a novel rescheduling problem in which a set of jobs has been assigned an original schedule to minimize the total weighted completion time on a single machine, with the assumption but not with 100% certainty that all of them will be available when the planned processing begins. The need for rescheduling arises due to some jobs could not arrive in time; the decision-maker has to adjust the original schedule to account for the delayed jobs without causing excessive time disruption to the original schedule and to minimize their operational cost. While the decision-maker can choose to reject any of the delayed or non-delayed jobs, the total rejection cost and the tardiness of each accepted job in the adjusted schedule are strictly upper bounded by given thresholds, respectively. The total operational cost includes three components: the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the penalty on the maximum tardiness for the accepted jobs. We study this novel rescheduling problem from approximation algorithm perspective, as it generalizes several classic NP-hard scheduling problems; we design a pseudo-polynomial time dynamic programming exact algorithm and, when the total rejection cost is unbounded, we develop the exact algorithm into a fully polynomial time approximation
Keyword:
Rescheduling
Job delay
Job rejection
Dynamic programming
Approximation scheme
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6.5
论文数:
1.0W
被引数:
3.8W
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容