.png){kind=icon}
返回
Scheduling problems with position dependent job processing times: computational complexity results
.png){kind=icon}
OA
AI
DOI：10.1007/s10479-012-1098-1.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we analyse single machine scheduling problems with learning and aging effects to minimize one of the following objectives: the makespan with release dates, the maximum lateness and the number of late jobs. The phenomena of learning and aging are modeled by job processing times described by non-increasing (learning) or non-decreasing (aging) functions dependent on the number of previously processed jobs, i.e., a job position in a sequence. We prove that the considered problems are strongly NP-hard even if job processing times are described by simple linear functions dependent on a number of processed jobs. Additionally, we show a property of equivalence between problems with learning and aging models. We also prove that if the function describing decrease/increase of a job processing time is the same for each job then the problems with the considered objectives are polynomially solvable even if the function is arbitrary. Therefore, we determine the boundary between polynomially solvable and strongly NP-hard cases.
Keyword:
Scheduling
Learning effect
Aging effect
Computational complexity
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.5
论文数:
8.1K
被引数:
2.1W
机构
暂无机构信息
引用论文
.png){kind=icon}
The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: Past, present, and future经济制造/订货量 (EMQ/EOQ) 和学习曲线: 过去、现在和未来
PREAI
分享收藏The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times具有到期日分配和依赖资源的处理时间的单机提前-迟到调度问题
PREAI
分享收藏
查看更多内容