机器带故障的两台机排序问题的一个近似算法  

An Approximation Algorithm for Two Parallel Machines Scheduling with Machine Disruptions

作　　者：叶赛英[1] 沈灏[1] 魏小兰[1] 

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

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

基　　金：浙江省教育厅科研项目(20050494);浙江科技学院科研基金项目(ZF200510)

摘　　要：讨论机器带故障中断的两台平行机排序问题,目标为极小化误工工件数,在转移时间t=0时的排序问题是问题P2|D=∞,t=0|∑ui′j,该文给出了相应的算法,并利用该算法,考虑了当工件转移时间t>0时的NP难的排序问题P2|D=∞,t≠0|∑ui′j。该文使用对前一问题的最优序π*当中的工件相交换,使得增加误工工件数尽量少的方法,提出了一个差界为1的多项式时间的近似算法,并给出了证明及算法的计算复杂性。The problem of two parallel machines scheduling with machine disruptions is discussed with the objective of minimizing the sum of unit penalties. If transfer time t=0, the problem P2｜D=∞,t=0｜∑u′ij is P problem, and an algorithm is proposed. Using this algorithm, we consider the NP - hard problem P2｜D=∞,t≠0｜∑u′ij. The method is exchanging the jobs of π^＊ and minimizing the adding sum of unit penalties. Then an approximation algorithm is proposed in this paper and its difference bound is 1.

关 键 词：近似算法 最坏情况界 机器中断 

分 类 号：O212[理学—概率论与数理统计]