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

被引：7

作者：

Zhang, An ^{[1
]}

Wang, Hongjun ^{[1
]}

Chen, Yong ^{[1
]}

Chen, Guangting ^{[2
]}

机构：

[1] Hangzhou Dianzi Univ, Inst Operat Res & Cybernet, Hangzhou 310018, Zhejiang, Peoples R China

[2] Taizhou Univ, Taizhou 317000, Zhejiang, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 213卷

基金：

中国国家自然科学基金;

关键词：

Parallel machine scheduling; Single server; SPT algorithm; Worst-case analysis; COMMON SERVER; ALGORITHM;

D O I：

10.1016/j.dam.2016.05.014

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 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 + root m-1/root m+root m-1 < 1.5 for the equal-processing-time problem. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：196 / 206

页数：11

共 16 条

[1] A survey of scheduling problems with setup times or costs [J].