LP范数下若干排序问题算法研究

发布时间：2019-07-24 08:28

【摘要】：本文主要研究Lp范数下的半在线排序问题。问题描述如下,给定m台同型机,以及n个工件,我们需要将每个工件安排在这些机器中的一台或者若干台上进行加工,每一时刻每台机器上只能加工一个工件,每一工件在同一时刻在其需要的数量的机器上加工,每个工件加工时间不一定相同,工件需要的机器数量也可能不同,工件是按照列表顺序达到的,只有当前一个工件安排之后,后一个工件才到来,工件的具体信息只有当其到达之后才知晓。每个工件安排以后就必须加工完,不允许中断。我们的目标是将工件安排在这些机器上,使得处理机的完工时间向量(负载)的Lp范数最小。论文结构如下,第一、二章介绍了排序问题的背景知识。第三章和第四章讨论三台同型机的半在线排序问题,此处讨论的问题中每个工件只需要一台机器加工即可,目标是极小化机器负载的Lp范数,在第三章,针对总加工时间已知的情形,我们设计了竞争比至多为max{3/2,(?)}的半在线算法。在第四章针对的是最大加工时间已知情形,我们设计了竞争比至多为max{(?),(?)}的在线算法。在第五章,我们研究了 Lp范数下m台同型机并行工件半在线排序问题的算法,此处工件是并行工件,即每个工件加工需要的机器数可以不止一台,对已知最大加工时间的情形,我们给出了竞争比至多为40/3的算法,进一步分析表明该算法的竞争比至少为6。最后对论文进行了总结,分析了所得结果的不足之处以及进一步研究的方向和思路。
【图文】：

图３－２情况一的排序表逡逑
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【参考文献】

相关期刊论文 前10条

1 郭玲;赵传立;;带有公共交货期窗口和加工时间可控的单机排序问题[J];重庆师范大学学报(自然科学版);2012年06期

2 李岩;田海龙;;总完工时间最短的恒速机排序[J];吉林化工学院学报;2009年03期

3 胡觉亮;刘晨;;带服务等级约束的单位长度工件排序问题[J];浙江理工大学学报;2008年01期

4 张果桃;赵金雁;白中英;;基于LT-backfilling算法的集群作业调度系统[J];计算机工程;2007年21期

5 林凌;;l_p范数下两台同型机半在线问题的最优算法[J];浙江大学学报(理学版);2007年02期

6 蔡圣义;;预先知道总加工时间的一类特殊的三台平行同类机在线排序[J];温州师范学院学报(自然科学版);2006年05期

7 朱熙;杨启帆;;可中断半在线排序问题[J];浙江大学学报(理学版);2006年01期

8 蔡圣义;两台机在线均衡调度算法的改进[J];温州师范学院学报(自然科学版);2004年02期

9 何勇,杨启帆,谈之奕;平行机半在线排序问题研究(Ⅱ)[J];高校应用数学学报A辑(中文版);2003年02期

10 何勇,杨启帆,谈之奕;平行机半在线排序问题研究(Ⅰ)[J];高校应用数学学报A辑(中文版);2003年01期

，

本文编号：2518518