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