最小化加权完工时间和的在线排序研究

发布时间：2020-11-09 19:40

　　 在线排序研究具有重要的理论意义和实际应用价值。近二十年来,在线排序得到国内外同行的广泛关注和深入研究,并促使其成为现代排序领域中发展最为迅速的方向之一。本文所说的“在线”是指时间在线(online over time)。也就是说,工件是随着时间依次到达的,并且事先不知道它的一切信息。求解在线问题的算法称为在线算法。对一个最小化目标函数的在线排序问题,在线算法A的竞争比定义为ρA=sup{A(I)/OPT(I):I是满足OPT(I)0的任一实例}.由此可见,竞争比越接近于1,就表明在线算法的性能越优良。如果不存在其他的竞争比小于A的竞争比的在线算法,就称在线算法A是最好可能的(best possible)。工件的加权完工时间和是排序的主要优化指标之一。本学位论文研究了若干与最小化工件的加权完工时间和相关的在线排序问题。学位论文共有六章:第一章主要介绍了一些与组合最优化以及排序问题相关的概念,并介绍了在线排序的研究现状,特别是最小化加权完工时间和的在线排序的研究现状。第二章研究了工件可拒绝的在线排序,其中每个工件Jj或者被拒绝加工并支付拒绝费用ej,或者被机器接收并加工。目标是最小化接收工件的加权完工时间和加上被拒绝工件的拒绝费用和。?对于一台机器工件有相同的权重且加工时间和拒绝费用满足一致性条件的情形,给出了一个竞争比为2的最好可能的在线算法DSPTR。?对于一台机器上问题的一般情形,给出了一个竞争比为2的最好可能的在线算法DSWPTR,推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。该结果也是本章上一个结果的推广,但是论证技巧上截然不同。我们首先将在线算法柔性化,然后采用实例归结的技巧进行论证。?在多台恒同机(identical machines)上,我们给出了一个竞争比至多为4+的在线算法,在多台无关机(unrelated machines)上,我们给出了一个竞争比至多为8的在线算法。第三章研究了一台机器最小化时间表长和加权完工时间和的在线折衷排序问题。我们引入了最小化f1和f2的在线折衷排序。称一个在线算法A是(ρ1,ρ2)-竞争的,如果最小化f1时A是ρ1-竞争的而最小化f2时A是ρ2-竞争的。对于一个(ρ1,ρ2)-竞争的在线算法A,如果不存在(ρ1,ρ2)-竞争的在线算法A满足(ρ1,ρ2)≤(ρ1,ρ2)并且有ρ1ρ1或者ρ2ρ2,则在线算法A被称为是不可支配的(nondominated).?对于该问题,我们给出了一个参数在线算法,并利用两种不同的方法分别证明了该算法对于满足0α≤1的任意α是一个竞争比为(1+α,1+1/α)的不可支配的在线算法。此结果推广了Anderson和Potts发表于《Mathematics of Operations Research,2004》的结果。第四章研究了多台平行批机器上批容量有限目标函数为最小化加权完工时间和的在线排序问题。?在一致机(uniform machines)上,当机器台数m为常数时,我们得到了一个竞争比至多为4+的在线算法。?在恒同机上,当机器台数m任意时,我们也得到了一个竞争比至多为4+的在线算法。该项工作改进了Zhang等人发表于《Journal of Industrial and Management Optimization,2007》对此问题给出的竞争比至多为8的在线算法。第五章研究了一台机器上工件加工时间可退化的最小化加权完工时间和的在线排序问题。在该问题中,工件Jj的加工时间为pj=αj(A+Bsj),其中A≥0,B≥0,A和B至少有一个非零,αj≥0是工件Jj的退化率,sj≥0是工件Jj的开工时间。?我们给出了一个竞争比为1+λ(A)+αmaxB的最好可能的在线算法,其中αmax=max1≤j≤nαj,而λ(A)=0或λ(A)=1取决于A=0或A0。该项工作将Liu等人发表于《Theoretical Computer Science,2012》的简单线性退化并且工件权重都相等时的结果推广到了线性退化并且工件权重不同的更一般的情形。第六章总结了本学位论文所研究的主要内容和取得的一些主要结果,并指出了存在的一些问题以及未来的一些研究方向。
【学位单位】：郑州大学
【学位级别】：博士
【学位年份】：2015
【中图分类】：O223
【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 排序问题
    1.2 排序问题的三参数表示
    1.3 离线排序
    1.4 在线排序
    1.5 相关文献综述
        1.5.1 最小化加权完工时间和的时间在线排序问题
        1.5.2 带工件拒绝的的机器排序
        1.5.3 分批排序
        1.5.4 工件加工时间可退化的机器排序
        1.5.5 本文结果
第2章 工件可拒绝的在线排序问题
    2.1 引言
    2.2 本章的结构
    2.3 一致条件下权重相同的情形
    2.4 一般情形
        2.4.1 准备工作
        2.4.2 算法和分析
    2.5 平行机情形
        2.5.1 准备知识
        2.5.2 算法和分析
第3章 在线折衷排序问题研究
    3.1 引言
    3.2 准备工作
    3.3 实例归结方法证明
        3.3.1 准备知识
        3.3.2 竞争比分析
    3.4 组合方法证明
        3.4.1 两个辅助问题的定义
        3.4.2 缺口工件的性质
        3.4.3 为问题 （E） 创建一个可行排序
        3.4.4 主要结果的证明
    3.5 算法的非支配性证明
第4章 最小化加权完工时间和的平行机在线分批排序
    4.1 引言
    4.2 相关工作
    4.3 问题MSWP（Qm-batch） 的对偶FPTAS
    4.4 问题MSWP（P -batch） 的对偶PTAS
第5章 工件线性退化的在线排序研究
    5.1 引言
    5.2 相关工作
    5.3 准备工作
    5.4 算法及分析
第6章 结论与展望
参考文献
个人简历、在学期间完成的学术论文与研究成果
致谢

【相似文献】

相关期刊论文 前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期

相关博士学位论文 前6条

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

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

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

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

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

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

相关硕士学位论文 前7条

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

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

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

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

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

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

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

本文编号：2876881