检索结果-内蒙古大学图书馆

PREEMPTIVE SCHEDULING ALGORITHMS WITH nested processing set RESTRICTION

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2009年第6期20卷 1147-1160页

作者： Huo, Yumei Leung, Joseph Y-T Wang, Xin CUNY Dept Comp Sci Staten Isl NY 10314 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA Bloomberg LP R&D Dept New York NY 10022 USA

We consider the problem of preemptively scheduling n independent jobs {J(1),J(2), ..., J(n)} on m parallel machines {M(1),M(2), ..., M(m)}, where each job J(j) can only be processed on a prespecified subset M(j) of machines called its processing set. The machines are linearly ordered, and the processing set of J(j) is specified by two machine indexes a(j) and b(j);i.e., M(j) = {M(aj),M(aj+1), ..., M(bj)}. The processing sets are nested;i.e., for i not equal j, we have M(i) subset of M(j), or M(j) subset of M(i),or M(j) boolean AND M(i) = phi..Our goal is to minimize the makespan. We first give an O(n logn)-time algorithm to find an optimal schedule. We then give an O(mn + nlogn)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t>0.

关键词： Preemptive scheduling nested processing set inclusive processing set makespan minimization polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast approximation algorithms for job scheduling with processing set restrictions

引用

THEORETICAL COMPUTER SCIENCE 2010年第44-46期411卷 3947-3955页

作者： Huo, Yumei Leung, Joseph Y-T New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA CUNY Dept Comp Sci Staten Isl NY 10314 USA

We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Tree-hierarchical processing set Inclusive processing set nested processing set Makespan minimization Polynomial-time approximation algorithm NP-hard Nonpreemptive scheduling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：