一致机上最小化时间表长的在线排序问题

摘要

在离线排序问题中，机器的性质是多样的，其中研宄比较多的主要为恒同机、一致机以及无关机。所谓恒同机是指机器的速度是一样的，工件的加工时间只与工件自身的长度有关，而与机器无关；一致机是指机器的速度是不同的，一个工件的加工时间既与工件自身有关又与所排的机器速度有关;无关机是指机器的速度与所加工的工件也存在着联系.
　　本文研究一致机上的在线排序问题，工件在到达之前的所有信息都是未知的。在线包括按时到达和按序列到达。按时到达即每个工件都有各自的到达时间，按序列到达即工件是一个接着一个到的，下一个工件只有在前一个工件排序之后才能到达。每个工件一旦到达，工件的所有信息就变成已知。
　　在第二章中，研究了m台一致机上批容量无界的工件长度为1在线排序问题Qm|online，p-batch,b=∞,pj=1|Cmax(m≥2),其中前m-1台机器的速度为1,最后一台机器的速度为v(0< v<1)。在线指的是工件按时间到达，在工件到达之前，该工件的所有信息是未知的。每个工件的加工时间均为1。分批指的是一台分批机器可以一批同时加工至多b个工件。批的加工时长由该批中的最长工件决定。按照批的容量，可以分为两类平行分批排序：有界的情形和无界的情形。这里我们研究批容量无界的情形。我们给出竞争比为1+α1,0＜v≤1/2,1+α={1+α2,1/2＜v≤1.的最好可能的在线算法。其中α1满足等式（1+α)m=2+α;α2满足等式（1+α)(m+1)=(1/x-1)(1+α)(m-1)+2+α。
　　在第三章中，我们考虑2台一致机上的分层可中断在线排序问题。Q2|online-list，g=2，pmtn|Cmax,工件是按序列到达，即后一个工件的信息只有在前一个工件排序之后才能知道。第一台机器的速度为1,第二台机器的速度为v。该问题所研宄的工件分为两层，对于Jj工件来说，gj=1表示该工件只能在第一台机器上加工，gj=2表示该工件可以在任意一台机器上加工。进一步，排在速度为1的机器上的工件的实际加工时间为该工件自身的加工时间，而排在速度为v的机器上的工件的加工时间等于该工件的标准加工时间与机器速度的比值。在任意时刻，每个机器最多只能加工一个工件，每个工件最多只能被一台机器加工。可中断即工件可以分成若干个片段在不重叠的时间内在不同的机器上加工。这里所研宄的可中断是不允许有空闲时间的，后到达的工件必须紧着前面排好的工件去排。在实际应用中的一些情况下，可能不允许有空闲时间是必须的，这也使得本文有研宄价值。本章对于当v≤1时给出竞争比的下界为1+ v/(v+1),当 v≤1且满足v3+v2≥1时给出竞争比为1+1/v2+v的在线算法；当v≥1时给出了竞争比的下界为1+1/v+1,并给出竞争比为1+v/v+1击的在线算法。

目录

封面

声明

英文摘要

目录

第一章引言

§ 1.1问题背景

§ 1.2预备知识

§1.3 相关文献综述

§1.4 本文的主要结果

第二章m 台一致机上单位工件分批在线排序

§ 2.1引言

§ 2.2问题的下界

§2.3 在线算法

第三章2台一致机上无空闲时间的可中断分层在线排序

§3.1 引言

§3.2 问题的下界

§3.3在线算法

后记

参考文献

致谢