带有拒绝工件和机器具有不可用区间的单机排序问题  

Single Machine Scheduling Problem with Rejection Jobs and a Machine Non-Availability Interval

作　　者：赵升华 罗成新[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《重庆师范大学学报（自然科学版）》2014年第2期5-9,共5页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.11171050)

摘　　要：本文考虑带有拒绝工件和机器具有不可用区间的单机排序问题。目标是最小化被接受工件的特定加权总完工时间与被拒绝工件总费用的和。工件有不同的释放时间和权,权等于它们的加工时间。这个问题是一般NP-难的。为了能在较少的运行时间内得到该问题较好的近似解,利用削减状态空间的方法得到了一个全多项式时间近似方案(FPTAS),该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n3/ε2),其中n为输入工件的个数,ε是误差界。In this paper, we consider a single machine scheduling problem with rejection jobs and a machine non availability interval. The objective is to minimize the sum of the total special weighted completion times of the accepted jobs and the total rejection penal- ty of the rejected jobs. Jobs have different release dates and weights, the weight of a job equals to its processing time. The problem is NP-hard in the ordinary sense. To get a better approximation solution in a polynomial running time, we propose a fully polynomi- al-time approximation scheme （FPTAS） by trimming the state spaces. This FPTAS is a better approximation algorithm and its run- ning time is strongly polynomial, the running time is O（n^3/ε^2 ） , where n is the number of jobs and eis the required error bound.

关 键 词：释放时间 拒绝工件 不可用区间 特定加权流时间 全多项式近似方案 

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