在线平行机排序问题研究

论文摘要

排序（调度）理论是近年来组合优化方向很活跃的一个研究分支，受到众多学者的关注．对于排序问题的研究已有几十年的历史．本文研究了近十几年发展起来的若干在线排序问题．全书共分为六章，第一章主要介绍与排序问题相关的一些概念和预备知识．第二章主要研究工件具有相同的加工时间1，有到达时间和交货期且目标函数为极大化按时完工的工件个数的两台机在线排序问题．首先，我们对于m台机时的问题给出了该问题的一个下界；其次，我们对于m台机的情形给出了一个简单的具有竞争比为2的在线算法；最后，对于两台机的情形，我们给出了一个最好的在线近似算法，而且算法满足“立即通知”的性质．第三章研究上一章中当m≥2时的问题．为方便起见，我们考虑工件具有相同的整数加工时间p，且有非负整数到达时间和交货期，目标函数为极大化按时完工的工件个数的m台机在线排序问题．易知对于任意的p，该问题与上述问题具有等价性．对于该问题我们给出了一个具有“立即决定”性质的在线算法，并证明了该算法的竞争比为1／（1-（m／（m+1））m），其中当m趋向于无穷大时，该竞争比趋向于e／（e-1）≈1．582．另外，我们还给出了对于该问题具有“立即决定”性质的在线算法的一些下界．第四章研究工件的加工长度任意，有到达时间和交货期，且工件可以“中断-重新”开始加工，目标函数为极大化按时完工的工件个数的m台机在线排序问题．这里的可“中断-重新”开始加工指的是工件在加工过程中可以被中断，但当算法在下次执行此工件时必须从头开始加工．对于该问题，我们首先给出了一个4/3的下界，然后给出了一个竞争比为2的在线算法．第五章研究工件具有“任意”的到达时间，目标函数为最小化最大工件完工时间（makespan）的m（m≥2）台机的在线排序问题．这里的问题模型指的是工件按一定先后顺序出现，只有当前面的工件被安排后才知道下一个工件的信息．与经典在线模型不同的是前丽的工件的到达时间有可能比后面的工件到达时间要大．此问题可以看成是经典的在线模型（Jobs Arrive over list）的推广．对于机器台数m=2时的问题，我们给出了一个竞争比为2的最好的在线算法．对于一般的机器台数为m，并且所有工件都有单位时间加工长度时的问题，我们证明了LS算法的紧界为3/2．第六章为后记．简要的总结了一下本文的工作，讨论了未来的研究方向以及一些公开问题．

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 组合优化简介
• 1.2 排序问题
• 1.3 算法和计算复杂性
• 1.4 论文概述
• 第二章 工件具有到达时间和交货期的两台机的在线排序问题
• 2.1 引言
• 2.2 问题的下界
• 2.3 在线算法
• 2.3.1 两台机时的MEDF算法
• 2.3.2 MEDF算法的分析
• 第三章 工件具有到达时间和交货期的m台机的在线排序问题
• 3.1 引言
• 3.2 算法BestFit
• 3.3 立即决定（immediate decision）条件下问题的下界
• 3.4 工件的加工时间较小时的情形
• 第四章 工件可中断-重新开始加工的在线平行机排序问题
• 4.1 引言
• 4.2 问题的下界
• 4.3 算法SRPT
• 4.4 工件具有相同的交货期的情形
• 第五章 工件具有任意到达时间的在线平行机排序问题
• 5.1 引言
• 5.2 两台机时问题的一个最好的（best possible）算法
• 5.3 算法LS
• 第六章 后记
• 参考文献
• 致谢
• 在学期间完成的论文