Optimal algorithms for online single machine scheduling with deteriorating jobs

详细信息	查看全文 | 推荐本文 |

• 作者：Ming Liu^a ; Feifeng Zheng^b ; ^c ; ^{zhengff@mail.xjtu.edu.cn} ; Shijin Wang^a ; Jiazhen Huo^a
• 关键词：Scheduling ; Online algorithm ; Deteriorating job ; Competitive analysis
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：3 August, 2012
• 卷：445
• 期：Complete
• 页码：75-81
• 文件大小：220 K

摘要

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job鈥檚 deterioration effect. Such effect is unexplored in the context of online environment. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness.