期刊
ANNALS OF OPERATIONS RESEARCH
卷 186, 期 1, 页码 345-356出版社
SPRINGER
DOI: 10.1007/s10479-011-0835-1
关键词
Single-machine scheduling; Learning effect; Performance ratio; Worst-case error
资金
- NSFC [10371071, 70731160015]
- SHKDCP [S30504]
- The Innovation Fund Project For Graduate Student of Shanghai [JWCXSL1001]
We consider single-machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker's learning through experiences. In the models we study, each job has its normal processing time. However, a job's actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据