机器带中断的误工问题的近似排序算法  

Scheduling Algorithm with Machines Disruption to Minimize the Number of Late Jobs

作　　者：叶春花[1] 沈灏[1] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2010年第1期96-98,共3页Journal of Hangzhou Dianzi University：Natural Sciences

摘　　要：该文讨论两台平行机排序问题,其中一台机器在不确定情况下中断,中断持续时间为D,目标为极小化误工工件数。当工件转移时间T=0时,该文提出该问题的最优算法。当转移时间T>0时为NP难问题,该文提出了一个差界为1的多项式时间的近似算法。该文讨论两台平行机排序问题,其中一台机器在不确定情况下中断,中断持续时间为D,目标为极小化误工工件数。当工件转移时间T=0时,该文提出该问题的最优算法。当转移时间T>0时为NP难问题,该文提出了一个差界为1的多项式时间的近似算法。

关 键 词：平行机排序 中断 近似算法 

分 类 号：TN-55[电子电信]