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

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

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

【具有特殊工件的平行機(jī)在線排序問題】相關(guān)文章：

遠(yuǎn)程培訓(xùn)在線教學(xué)支持的問題及對策研究04-28

數(shù)學(xué)排序教案01-07

有趣的排序教案01-28

在線詞典大全05-04

平行的教案01-16

中班數(shù)學(xué)《排序》05-10

大小排序的教案01-25

在線上課簡報12-23

尼康單反D200相機(jī)常見問題集10-14

小班數(shù)學(xué)排序反思03-10