.png){kind=icon}
返回
Fast approximation algorithms for uniform machine scheduling with processing set restrictions
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2017.01.013.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider the problem of nonpreemptively scheduling a set of independent jobs on a set of uniform machines, where each job has a set of machines to which it can be assigned. This kind of restriction is called the processing set restriction. In the literature there are many kinds of processing set restrictions that have been studied. In this paper we consider two kinds: the inclusive processing set and the tree-hierarchical processing set. Epstein and Levin (2011) have given Polynomial Time Approximation Schemes (PTAS) to solve both classes. However, the running times of their PTAS are rather high. In this paper, we give fast approximation algorithms for both cases and show that they both have a worst-case performance bound of 4/3. Moreover, we show that the bounds are achievable. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Scheduling
Uniform machines
Inclusive processing set
Tree-hierarchical processing set
Makespan
Worst-case bound
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容