等级约束下的两类负载均衡问题

发布时间：2021-07-24 15:06

　　等级约束下的负载均衡问题是组合优化领域的经典难题之一,其在近十年里得到了广泛的研究。等级约束下的负载均衡问题即把若干个带等级的工件分配给一些带等级的机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化,这里的负载一般定义为工件的加工时间或加工工件所需的各种资源。本文主要研究了等级约束下的负载均衡问题的两类广义形式:多重负载均衡问题和多维负载均衡问题。等级约束下的多重负载均衡问题即给定若干个客户和一些带等级的机器,每个客户提交若干个带等级的工件给这些机器加工,工件可以在等级不低于自己的机器上加工,且每个工件只能被一台机器不间断的加工。目标是寻找一种分配方案使得最大机器负载最小化。对等级约束下的多重负载均衡问题,当机器台数m = 2时,本文设计了一个5/4-近似算法,一个5/3-最优在线算法和一个在所有工件加工时间之和的一半已知的情况下的3/2-最优半在线算法并分析了近似比;当机器台数m ≥ 3时,本文设计了一个2-1/m-1-近似算法并分析了近似比。m-1等级约束下的多维负载均衡问题即把若干个带等级的工件分配给... 

【文章来源】：云南大学云南省 211工程院校

【文章页数】：42 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 引言
    §1.1 基本知识
    §1.2 研究背景
    §1.3 主要结果
    §1.4 论文结构
第二章 等级约束下的多重负载均衡问题
    §2.1 问题描述
    §2.2 离线算法
    §2.3 最优在线算法
    §2.4 最优半在线算法
第三章 等级约束下的多维负载平衡问题
    §3.1 问题描述
    §3.2 2d-近似算法
    §3.3 全多项式时间近似方案
结论
参考文献
攻读硕士学位期间完成的研究成果
致谢


【参考文献】：
期刊论文
[1]lp范数下具有等级约束的负载均衡问题[J]. 李伟东,李陈筠然,李建平.  计算机科学与探索. 2016(08)
[2]平行机上订单半在线排序的LS算法的性能比分析[J]. 唐峰,聂劲.  系统工程. 2016(06)
[3]排序问题的定义、分类和在国内的某些研究进展[J]. 唐国春.  运筹学杂志. 1990(02)

博士论文
[1]当代工业中的若干排序问题研究[D]. 季敏.浙江大学 2006

硕士论文
[1]单机半在线排序算法竞争比分析[D]. 陶冶.上海交通大学 2010



本文编号：3300888