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