Pm||C_(max)问题的算法A_(KK)的一个改进的最坏情况性能比(英文)

本文考虑的是平行机排序问题Pm||Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1+(1-1/m/1+|k/m|),而且当k(?)0(modm)时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比:1+max{1-1/m/1+k1+1/m,1-1/m-k2/1+k1},其中k1和k2为非负整数且k1m+k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.

带机器准备时间的两台同型机复合半在线排序问题(英文)

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.

具有特殊工件的平行机在线排序问题(英文)

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M_1.我们提供了竞争比为(2m^2-2m+1)/(m^2-m+1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1+33^(1/33))/4≈1.686.