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

Two approximation algorithms for three parallel machines scheduling with machine disruptions

作　　者：叶赛英[1] 徐弼军[1] 

机构地区：[1]浙江科技学院理学院,杭州310023

出　　处：《浙江科技学院学报》2016年第1期12-18,共7页Journal of Zhejiang University of Science and Technology

基　　金：浙江省<基础数学>重点学科建设学术研究子项目(20131029)

摘　　要：机器带故障的m台机的目标函数为最小化误工工件数的排序问题,在m≥2时是NP(nondeterministic polynomial)困难的问题,对m=3,当工件转移时间t=0和t≠0两种情况,提出了P3丨D=∞,t1=t2=0丨n-∑u′ij和P3丨D=∞,t1≠t2丨n-∑u′ij的近似算法,以及对应的渐进性能比,且证明了其界是紧的。We discuss the problem of m parallel machines scheduling with disruptions with the objective of minimizing the sum of unit penalties.If m≥2,the problem is NP-hard.When m=3and transfer time is t=0and t≠0,two approximation algorithms are proposed for the problems of P3 D = ∞,t1=t2 =0n-∑u′ijand P3 D = ∞,t1 ≠t2n-∑u′ijrespectively.And the paper proves that the upper bound is tight respectively.

关 键 词：排序 性能比 最小化误工工件数 机器带故障中断 近似算法 

分 类 号：O223[理学—运筹学与控制论]