预知工件大小上界的平行机排序问题

吴用;杨启帆

系统科学与数学 ›› 2010, Vol. 30 ›› Issue (4) : 441-448.

PDF(386 KB)
PDF(386 KB)
系统科学与数学 ›› 2010, Vol. 30 ›› Issue (4) : 441-448. DOI: 10.12341/jssms08959
论文

预知工件大小上界的平行机排序问题

    吴用(1), 杨启帆(2)
作者信息 +

Semi-Online Multiprocessor Scheduling with Bounded Jobs

    WU Yong(1), YANG Qifan(2)
Author information +
文章历史 +

摘要

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡, 大型计算中的并行计算,
柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:Cmax(极小化机器最大负载~makespan) 和~Cmin(极大化机器最小负载).在不同的目标下,针对~m 台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.

Abstract

Machine scheduling problems may occur in many applications such as load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc. In this paper, semi-online multiprocessor scheduling problems with bounded
jobs are considered. The model only known the upper bound of each job in
advance and the model known both the optimal value and the upper bound of each job in advance are analyzed. Motivated by issues of fair resource allocation and quality of service, two goals Cmax(minimize makespan) and Cmin(maximize the minimum machine load) for each model are studied. It is shown that the lower bound and design semi-online algorithm for each problem when the number of machine is m. Finally, optimal algorithms are given for some situations.

关键词

排序 / 半在线 / 算法设计与分析 / 竞争比.

Key words

Scheduling / semi-online / design and analysis of algorithm / competitive ratio.

引用本文

导出引用
吴用 , 杨启帆. 预知工件大小上界的平行机排序问题. 系统科学与数学, 2010, 30(4): 441-448. https://doi.org/10.12341/jssms08959
WU Yong , YANG Qifan. Semi-Online Multiprocessor Scheduling with Bounded Jobs. Journal of Systems Science and Mathematical Sciences, 2010, 30(4): 441-448 https://doi.org/10.12341/jssms08959
中图分类号: 90B35    68M20   
PDF(386 KB)

153

Accesses

0

Citation

Detail

段落导航
相关文章

/