Scheduling jobs with equal processing times and a single server on parallel identical machines
Scheduling jobs with equal processing times and a single server on parallel identical machines
复制标题
在并行的相同机器上调度具有相同处理时间和单个服务器的作业
DOI：
10.1016/j.dam.2016.05.014
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Chen Guangting
中科院分区：
文献类型：
--
作者：
Zhang An;Wang Hongjun;Chen Yong;Chen Guangting
研究了单台服务器的并行机排序问题。有一组作业要在一组m台平行且相同的机器上处理。在机器上处理之前，每个作业必须由单个服务器加载，这需要服务器和机器都花费一定的时间。不允许抢占。我们考虑的目标是最小化工件的完工时间之和。这个问题已经被证明是NP难的，即使所有作业具有相等的处理时间（Brucker等人，2002年）。本文证明了对于等处理时间问题，SPT算法的最坏情况比为1+ m− 1 m+ m− 1< 1.5。
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+ m− 1 m+ m− 1< 1.5 for the equal-processing-time problem.