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

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

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在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