Scheduling jobs with equal processing times and a single server on parallel identical machines

详细信息    查看全文

• 作者：An Zhang^a ; ^{anzhang@hdu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Hongjun Wang^a ; Yong Chen^a ; Guangting Chen^b
• 关键词：Parallel machine scheduling ; Single server ; SPT algorithm ; Worst-case analysis
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：196-206
• 全文大小：552 K

文摘

This paper studies the parallel-machine scheduling problem with a single server. There is a set of jobs to be processed on a set of m$m$ parallel and identical machines. Prior to processing on a machine, each job has to be loaded by a single server, which takes both the server and the machine a certain time. Preemption is not allowed. We consider the objective of minimizing the sum of jobs’ completion times. This problem has been shown to be NP-hard even when all jobs have equal processing times (Brucker et al., 2002). We prove in this paper that the SPT algorithm has a worst case ratio of $1+\frac{\sqrt{m-1}}{\sqrt{m}+\sqrt{m-1}}<1.5$ for the equal-processing-time problem.