Online scheduling on parallel machines with two GoS levels
Online scheduling on parallel machines with two GoS levels
复制标题
DOI：
10.1007/s10878-007-9095-z
复制
发表时间：
2006-06
影响因子：
1
通讯作者：
Yiwei Jiang
中科院分区：
文献类型：
--
作者：
Yiwei Jiang
本文研究了并行机和同型机上的在线排序问题，该问题具有一个新的特点，即来自不同客户的服务请求被赋予许多不同的服务等级（GoS）。因此，每个作业和机器都标有GoS级别，并且只有当作业的GoS级别不低于机器的GoS级别时，每个作业才能由特定机器处理。我们的目标是最小化makespan。在本文中，我们考虑了两个GoS水平的问题。它假设firstkmachines和lastm-kmachines的GoS级别分别为1和2。每个工作都有一个GoS级别1或2。我们首先证明所考虑的问题的下界至少是2。然后讨论了Azar等人提出的算法AW的性能。(J. Algorithms 18：221-237，1995），并证明它有一个紧界4−1/m。最后，我们提出了一个具有竞争比的近似算法。
This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the firstkmachines and the lastm−kmachines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithmAWpresented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio.