On lazy bureaucrat scheduling with common deadlines |
| |
Authors: | Ling Gai Guochuan Zhang |
| |
Institution: | (1) Department of Mathematics, Zhejiang University, Hangzhou, 310027, China |
| |
Abstract: | Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which
has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66,
2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer
science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A
k
and B
k
both having worst-case ratio of
, for any given integer k>0, under the objective functions min-makespan] and min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all
jobs share the same release time.
A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics,
pp 515–523, 2006.
Research of G. Zhang supported in part by NSFC (60573020). |
| |
Keywords: | Sheduling Approximation scheme NP-hardness |
本文献已被 SpringerLink 等数据库收录! |
|