A PTAS for Scheduling Unrelated Machines of Few Different Types
A PTAS for Scheduling Unrelated Machines of Few Different Types
复制标题
DOI：
10.1007/978-3-662-49192-8_24
复制
发表时间：
2016-01
影响因子：
3.9
通讯作者：
Jan Clemens Gehrke;K. Jansen;S. Kraft;Jakob Schikowski
中科院分区：
文献类型：
--
作者：
Jan Clemens Gehrke;K. Jansen;S. Kraft;Jakob Schikowski
不相关机器上的排序问题是一个经典的优化问题，其中工件必须被分配到多台机器上。每一件工作都需要机器加工时间。目标是最小化完工时间，即运行时间最长的机器的最大完工时间。除非，这个问题不允许多项式时间近似算法的比率优于。然而，一个自然的场景是，许多机器都是相同类型的，比如CPU和GPU集群：对于每种K机器类型，相同类型的机器k满足所有作业j。本文针对机型数K为常数的情况，提出了一种近似方案，即近似比算法，其改进的运行时间仅为单指数。
Scheduling on Unrelated Machines is a classical optimization problem wherenjobs have to be distributed tommachines. Each of the jobshas on machinea processing time. The goal is to minimize the makespan, i.e. the maximum completion time of the longest-running machine. Unless, this problem does not allow for a polynomial-time approximation algorithm with a ratio better than. A natural scenario is however that many machines are of the same type, like a CPU and GPU cluster: for each of theKmachine types, the machinesof the same typeksatisfyfor all jobsj. For the case where the numberKof machine types is constant, this paper presents an approximation scheme, i.e. an algorithm of approximation ratiofor, with an improved running time only single exponential in.