首页>
外文OA文献
>Fast approximation algorithms for uniform machine scheduling with processing set restrictions
【2h】
Fast approximation algorithms for uniform machine scheduling with processing set restrictions
展开▼
机译:快速近似算法,用于具有处理集限制的统一机器调度
展开▼
免费
页面导航
摘要
著录项
相似文献
相关主题
摘要
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.
展开▼