两类加权幂和形式的分批排序问题

论文摘要

平行分批排序和在线排序是两个发展迅速的排序模型。平行分批排序是指机器可以同时成批加工多个工件（有限或无限）。每批包含的工件同时开工同时完工。每批的加工时间是这批工件的最大加工时间。在线排序是指工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变。本文主要考虑了目标函数是和式的分批排序问题。首先研究了目标是最小化加权完工时间平方和的分批在线排序问题。在这个问题中,我们有一台批处理机,有n个按时在线到达的工件1,2,…,n.每个工件的加工时间为pj,权重为wj,到达时间为rj.根据批容量b是无界还是有界,我们所考虑的模型可分别记为1|on-line,rj,p-batch|∑wjCJ2与1|on-line,rj,p-batch,b＜n|∑wjCj2.对这一问题本文得到如下结果。（1）给出了问题1|on-line,rj,p-batch,b＜n|∑wjCj2的一个竞争比为16+O（ε）（（?）ε＞0）的在线算法。（2）给出了问题1|on-line,rj,p-batch|∑wjCj2的一个竞争比为11.3429的在线算法。其次,本文对目标是加权完工时间常数次幂和的单机平行分批排序问题进行了研究。这里我们只考虑了批容量无界的情形。所研究问题可表示为1|p-batch,rj|∑wjCjh（h≥1为固定常数）.文中通过利用划分时间轴和几何舍入的方法,把原始实例转化为较为简单的实例,并利用已有的拟多项式时间算法,最终给出了1|p-batch,rj|∑wjCjh（h≥1为固定常数）的一个全多项式时间近似方案。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 排序的介绍
• 1.2 在线排序和分批排序
• 1.3 算法和计算复杂性
• 1.4 相关结果及本文主要结果
• 第二章 最小化加权完工时间平方和的在线分批排序问题
• 2.1 准备工作
• 2.2 有界批模型的一个常数上界
• 2.3 无界批模型的一个在线算法
• 第三章 最小化加权完工时间常数次幂和的分批排序问题
• 3.1 准备工作
• 3.2 几个重要引理
• 3.3 一个全多项式时间近似方案
• 后记
• 参考文献
• 致谢