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

摘要：

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

关键词：运筹学、平行机排序、列表在线、特殊工件、竞争比

所属期刊栏目：12

分类号：O22;O1

资助基金：Research supported by the National Nature Science Foundation of China under grant 10671074, 60673048, 10571117 and the Development Foundation of Shanghai Education Committee under grant 05AZ04

在线出版日期：2008-11-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：59-66