带有分段线性递减加工时间和拒绝工件的单机排序问题  

Single Machine Scheduling with Piecewise Linear Decreasing Processing Times and Rejection Jobs

作　　者：隋敏[1] 赵传立[1] 

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

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

基　　金：辽宁省教育厅科学研究基金(No.L2014433)

摘　　要：讨论了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中,工件的实际加工时间是关于开始时间的分段线性递减函数,目标函数是极小化被接受工件的最大完工时间和被拒绝工件的总惩罚之和。这一问题是NP-难的。基于对问题的分析,给出了一个全多项式近似策略。全多项式近似策略的计算复杂性为O(n4 L4/ε3)。This paper considers single-machine scheduling with piecewise linear decreasing processing times and rejection. In this model, the actual processing time of a job is a piecewise linear decreasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. The problem is NP-hard. Based on the analy- sis of the problem, we give a fully polynominal time approximation scheme. The complexity of the fully polynominal time approxi- mation scheme is O（n4 L4 /ε3 ）.

关 键 词：单机排序 分段线性递减 拒绝 全多项式近似策略 

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