Semi-online scheduling on a single machine with unexpected breakdown

详细信息    查看全文

• 作者：Imed Kacem^a ; ^{imed.kacem@univ-lorraine.fr" class="auth_mail" title="E-mail the corresponding author} ; Hans Kellerer^b ; ^{hans.kellerer@uni-graz.at" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Semi-online scheduling ; Unexpected breakdown ; Competitive analysis
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：20 September 2016
• 年：2016
• 卷：646
• 期：Complete
• 页码：40-48
• 全文大小：392 K

文摘

In this paper, we consider a single machine scheduling problem where a breakdown period occurs in an online way. Two main objective functions are studied: the makespan and the maximum lateness. We propose two approximation algorithms for the makespan minimization for solving two variants of the problem: with different release dates or without release dates. We show that the competitive ratio of the two algorithms is 3/2 and that this bound is the best possible for the makespan minimization. For the maximum lateness minimization we propose a $(1+\sqrt{2}/2)\approx 1.70$-approximation algorithm capable to solve the problem with delivery times but no release dates. This ratio is tight for the proposed algorithm and allows us to establish a precise window for the best possible ratio, which belongs to $[3/2,1+\sqrt{2}/2]\approx [1.50,1.70]$.