具有特殊工件的平行機在線排序問題

本文研究一類具有特殊工件的平行機在線排序問題,目標是最小化最大完工時間.此模型有兩種工件:正常工件和特殊工件.正常工件能夠在m臺平行機的任何一臺機器上加工,而特殊工件僅能夠在它唯一被指定的機器上加工.文中所有特殊工件的指定機器為M1.我們提供了競爭比為(2m2-2m+1)/(m2-m+1)的在線近似算法.當m=2時,算法是最好可能的.當m=3時,算法的競爭比為13/7≈1.857,并且提供了競爭比的下界(1+(平方根33))14≈1.686.

作 者： 劉瑞芳 Liu Ruifang   作者單位： Department of Mathematics, East China Normal University, Shanghai 200241, China  刊 名： 運籌學學報  ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS  年，卷(期)： 2008 12(3)  分類號： O22  關鍵詞： 運籌學   平行機排序   列表在線   特殊工件   競爭比   Operations research   parallel machine scheduling   on-line-list   special jobs   competitive ratio  

【具有特殊工件的平行機在線排序問題】相關文章：

遠程培訓在線教學支持的問題及對策研究04-28

數學排序教案01-07

有趣的排序教案01-28

在線詞典大全05-04

平行的教案01-16

中班數學《排序》05-10

大小排序的教案01-25

在線上課簡報12-23

尼康單反D200相機常見問題集10-14

小班數學排序反思03-10