带机器故障的两台机带权误工数排序问题  

Minimization of the weighted number of tardy jobs of two parallel machines scheduling with machine disruptions

作　　者：胡觉亮[1] 张玮虹[1] 蒋义伟[1] 

机构地区：[1]浙江理工大学理学院,浙江杭州310018

出　　处：《高校应用数学学报（A辑）》2010年第4期393-395,共3页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(11001242;11071220);浙江省自然科学基金(Y6090554;Y6090175)

摘　　要：讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.The problem of two parallel machines scheduling with machine disruptions is discussed. It is assumed that each job is of unit-length.The goal is to minimize the weighted number of tardy jobs. For the case when the transfer time t = 0,an optimal algorithm is presented.Base on this algorithm, an approximation algorithm for the case when t≠0 is proposed.It is proved that the weighted number of tardy jobs of the latter algorithm is at most one more than that of the optimal solution.

关 键 词：排序算法 机器故障 带权误工数 

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