一个可中断三台可拒绝平行机半在线排序问题  

Preemptive Semi On-line Scheduling on Three Identical Machines with Rejection

作　　者：荣建华[1] 彭丽[1] 张玲玲[1] 侯丽英[2] 

机构地区：[1]石家庄铁道大学四方学院,石家庄051132 [2]南京农业大学理学院,南京210095

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

基　　金：国家自然科学基金数学天元基金(No.11426133);河北省高等教育科学研究课题(No.GJXH2015-289);河北省高等教育科学研究课题(No.GJXH2015-291);河北省高等教育教学改革研究与实践项目(No.2015GJJG293)

摘　　要：研究了工件带有拒绝费用的3台平行机半在线算法。工件逐个到达,当工件到达时可以被接收加工,消耗一定的加工时间,也可以被拒绝,但此时要付出一定的拒绝费用。进一步假定工件的加工时间与拒绝费用事先成固定比例α(α≥0)。目标为被接收工件的最大完工时间与被拒绝工件的总罚值之和最小。针对工件加工可中断情形,设计出半在线算法ARH,并证明算法ARH的竞争比为关于参数α的分段函数,且为紧界。Investigates the semi on-line scheduling problem on three identical machines with rejection.The job comes one by one,and when a job arrives,it can be accepted and scheduled on some machine or rejected by paying its penalty.And it is further assumed that the processing time of each job and its penalty forms the regular proportion denoted byα（α≥0）in advance.The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected.Preemption is allowed.For this version,we present an semi on-line algorithm ARH and prove the competitive ratio.

关 键 词：同型机 拒绝费用 中断加工 在线排序 竞争比 

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