论文部分内容阅读
在经典的离线排序问题中,在排序之前已经知道工件的所有信息.本文主要研宄的是按时在线排序^也就是指工件的各种信息在加工之前并不清楚,而是随着时间推移逐个到达之后才被了解. 在本文中,主要研究平行分批在线排序的若干问题.平行分批排序是排序研究领域中一类非常重要的问题。平行机排序模型中共有m台机器。一台分批机器可以一批同时加工至多b个工件。批的加工时长由该批中的最长工件决定.按照批的容量,可以分为两类平行分批排序:有界的情形和无界的情形. 在第二章中,对单机上最小化最大加权完工时间的分批在线排序问题,当批容量为1时,给出竞争比为2的最好可能的在线算法. 在第三章中,考虑平行机上单位长度工件最小化最大加权完工时间的分批在线排序问题.对批容量有界情形,引用三参数表示法可以表示为(此处公式省略)我们给出竞争比(此处公式省略)的最好可能的在线算法.同时证明了该问题稠密算法竞争比的下界为2,给出了达到该竞争比的稠密算法.批容量无界时,对问题(此处公式省略),我们给出竞争比为办的最好可能的稠密算法,这个结果在工件间无序约束关系时同样成立^ 在第四章中,考虑平行机上权重相同的单位工件具有不相容工件组和前瞻区间的无界分批在线排序问题.具有前瞻区间表示,在时刻尤,在线算法可以看到在化(此处公式省略)时间内到达的工件信息.不相容工件组表示来自不同工件组的工件不可以在同一批次加工.当所有工件的权重相同时,最大加权完工时间即转化为最大完工时间^对问题(此处公式省略),我们给出最优的在线算法.对问题(此处公式省略),我们给出竞争比为1+αk的最好可能的在线算法,其中他是方程(此处公式省略)对更一般的情形,我们证明了稠密算法的下界,并给出了最好可能的稠密算法.