最小化最大加权完工时间的平行分批在线排序问题

发布时间：2020-08-22 06:19

【摘要】：在经典的离线排序问题中,在排序之前已经知道工件的所有信息.本文主要研究的是按时在线排序.也就是指工件的各种信息在加工之前并不清楚,而是随着时间推移逐个到达之后才被了解.在本文中,主要研究平行分批在线排序的若干问题.平行分批排序是排序研究领域中一类非常重要的问题.平行机排序模型中共有m台机器.一台分批机器可以一批同时加工至多b个工件.批的加工时长由该批中的最长工件决定.按照批的容量,可以分为两类平行分批排序：有界的情形和无界的情形.在第二章中,对单机上最小化最大加权完工时间的分批在线排序问题,当批容量为1时,给出竞争比为2的最好可能的在线算法.在第三章中,考虑平行机上单位长度工件最小化最大加权完工时间的分批在线排序问题.对批容量有界情形,引用三参数表示法可以表示为：Pm|online,p-batch,b∞,Pj= 1|WCmax我们给出竞争比为攀#≈1.618的最好可能的在线算法.同时证明了该问题稠密算法竞争比的下界为2,给出了达到该竞争比的稠密算法.批容量无界时,对问题Pm|online,p-batch,prec,b=∞,Pj=1|WCmax和Pm|online,p-batch,prec,b=∞,Pj=1|∑wjcj,我们给出竞争比为(?)的最好可能的稠密算法,这个结果在工件间无序约束关系时同样成立.在第四章中,考虑平行机上权重相同的单位工件具有不相容工件组和前瞻区间的无界分批在线排序问题.具有前瞻区间表示,在时刻t,在线算法可以看到在㈦t+序]时间内到达的工件信息.不相容工件组表示来自不同工件组的工件不可以在同一批次加工.当所有工件的权重相同时,最大加权完工时间即转化为最大完工时间.对问题Pm|online,p-batch,b= ∞,Pj=1,LKβ,f-families,β≥[f/m]Cmax,我们给出最优的在线算法.对问题Pm|online, p-batch,b=∞,Pj=1,LKβk,f_families,f=km,βk∈[k-1,k)|Cmax,我们给出竞争比为1+α七的最好可能的在线算法,其中α七是方程kαk2+αk(βk+1)+βk-k=0的正根.对更一般的情形,我们证明了稠密算法的下界,并给出了最好可能的稠密算法.
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【相似文献】

相关期刊论文 前10条

1 李曙光,李国君,赵浩;无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案(英文)[J];运筹学学报;2004年04期

2 王玉青;孙世杰;;单机最小化加权总完工时间的产品加工问题(英文)[J];Journal of Shanghai University(English Edition);2007年02期

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

4 曹国梅;石忠和;;加工时间相同的分族分批排序加权总完工时间问题[J];安阳工学院学报;2009年04期

5 李曙光;李国君;赵洪銮;;极小化完工时间和的有界批调度问题(英文)[J];应用数学;2006年02期

6 李曙光;杨振光;亓兴勤;;极小化最大完工时间的单机分批加工问题(英文)[J];运筹学学报;2006年01期

7 王珍;曹志刚;张玉忠;;极小化最大完工时间及拒绝费用的单机可拒绝分批排序[J];曲阜师范大学学报(自然科学版);2007年02期

8 金霁;顾燕红;唐国春;;最大完工时间排序的两人合作博弈[J];上海第二工业大学学报;2011年01期

9 郭晓;冯密罗;慕运动;;时间错位限制下最小化总完工时间的继列分批重新排序[J];郑州大学学报(理学版);2012年01期

10 刘园园;许小艳;郝峗;慕运动;;时间期望错位限制下完工时间和的随机重新排序[J];河南科学;2012年07期

相关会议论文 前2条

1 张树霞;曹志刚;张玉忠;;极小化最大完工时间的离散可控排序(英文)[A];中国运筹学会第八届学术交流会论文集[C];2006年

2 陈克兵;高成修;;可变加工时间的单机排序(英文)[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

相关博士学位论文 前6条

1 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

2 李曙光;批调度与网络问题的组合算法[D];山东大学;2007年

3 马冉;最小化加权完工时间和的在线排序研究[D];郑州大学;2015年

4 何程;多目标分批排序及其相关课题[D];郑州大学;2009年

5 张国辉;柔性作业车间调度方法研究[D];华中科技大学;2009年

6 郑俊丽;船舶分段制造车间的模块空间调度模型及算法[D];上海交通大学;2011年

相关硕士学位论文 前9条

1 孔祥玉;作业时空受限的生产与运输调度问题研究[D];沈阳大学;2015年

2 柴幸;最小化最大加权完工时间的平行分批在线排序问题[D];郑州大学;2015年

3 卫志刚;可自由离线批处理机最小化加权完工时间和排序[D];郑州大学;2011年

4 尹婷;钢铁生产中连续批调度的策略研究[D];武汉科技大学;2011年

5 夏劲伟;GPU中针对任务完工时间最小化问题的研究[D];东北大学;2012年

6 曹志刚;分批排序、可拒绝排序及离散可控排序中的若干问题[D];曲阜师范大学;2006年

7 曹顺娟;同类机半在线机器覆盖问题研究[D];浙江大学;2006年

8 谢芳;机器带激活费用的有限资源博弈排序[D];曲阜师范大学;2012年

9 苗许娜;关于重新排序的一些结果[D];郑州大学;2006年

本文编号：2800367