Parallel machine scheduling with job assignment restrictions
Parallel machine scheduling with job assignment restrictions
复制标题
DOI：
10.1002/nav.20202
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
C. Glass;H. Kellerer
中科院分区：
文献类型：
--
作者：
C. Glass;H. Kellerer
在经典的多处理机排序问题中，独立的工件必须被分配到并行的、相同的机器上，目标是最小化最大完工时间。本文探讨了多处理机调度问题中任务分配限制对作业的影响。这意味着每个作业只能在特定的机器子集上处理。特别注意处理时间限制为两个值之一的情况，1和λ，相差最多2。提出了一种基于匹配的多项式时间ε-近似算法，其性能比趋于2-{1 \over 1+\lambda}$。该算法被证明具有最好的性能，倾向于3/2，处理时间1和2。对于嵌套处理集的特殊情况，即，当可以在其上分配单独作业的机器集合不重叠时，探索列表调度算法的行为。最后，分配限制的机器，如磁盘存储或内存约束的情况下，高性能计算的一个特性，我们贡献了一个算法，提供了一个3/2的最坏情况下的界限和运行的时间线性的工作数量。© 2006 Wiley Periodicals，Inc.海军研究后勤，2007年
In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to $2-{1 \over 1+\lambda}$ . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007