论文摘要
本文主要研究关于平行工件（parallel jobs）的排序（scheduling）问题。有2m台一致平行机，其中m台速度为1，另外m台速度为s（s＞1）。每个平行工件Jj要求必须在mj（m≥mj≥1）台机器上同时加工这个工件，但每个工件只能选取同一种速度的机器。工件在零时刻都已到达，但他们的加工时间是未知的，只有当工件加工完成时才可知道。这种在线模型称为无预见的（nonclairvoyant，简记为ncv），目标是极小化最大完工时间(Cmax)。用三参数表示法，我们的问题可以表示为Q2m|rj=0，mj，on-line-ncv|Cmax。我们对该排序问题提出了相应的在线算法，并采用国际上通用的算法评价标准竞争比（competitive ratio）来衡量、分析给出的算法。通过构造坏的实例，我们给出了问题的下界（lower bound）。同时研究了该模型在一定限制下的特殊情形，得到了更好的竞争比。本文的主要结果如下：（1）对于排序模型Q2m|rj=0，mj,on-line-ncv|Cmax，给出了其下界（2）对于排序模型Q2m|rj=0，mj，on-line-ncv|Cmax给出一个竞争比为的在线算法，其中（3）对于排序模型Q2m|rj=0，mj，on-line-ncv|Cmax，在P≥m（s+1）pmax限制下，给出了一个竞争比为(s′=(m+（3m2+2m）1/2)/（m+1）)的算法。其中（4）对于排序模型Q2m|rj=0，mj，on-line-ncv|Cmax，在限制下，使用等效化（Virtualization）这一手段，给出了一个竞争比为的算法。其中