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

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

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

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

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

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

有趣的排序教案01-28

在線詞典大全05-04

平行的教案01-16

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

大小排序的教案01-25

在線上課簡(jiǎn)報(bào)12-23

尼康單反D200相機(jī)常見(jiàn)問(wèn)題集10-14

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