特殊情形下的两台可拒绝同类机在线排序问题  

A Special Case of On-line Scheduling on Two Uniformly Machines with Rejection

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

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

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

基　　金：国家自然科学基金数学天元基金(No.11426133);南京农业大学青年科技创新基金(No.0506J0116);河北省高等教育教学改革研究与实践项目(No.2015GJJG293)

摘　　要：研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为1和s,s∈[1,+∞),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例α(α≥0),即p_j=αt_j。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法URLS,并证明该算法的竞争比和下界均为关于参数α的分段函数,且当α∈[0,(s+1)^(1/2)/s+1)∪[1,+∞)时上下界相吻合,算法达到最优。This paper investigates the on-line scheduling problem on two uniform machines with rejection.Supposing two uniform machines with speed 1and s,s∈[1,＋∞）.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 make span produced by the accepted jobs and the total penalty of the jobs which have been rejected.Preemption is not allowed.For this version,we present an online algorithm URLS and prove the competitive ratio.A lower bound of this problem is proposed which shows that in the interval of α∈[0,（s＋1）（1/2）/s＋1）∪[1,＋∞）our algorithm is optimal.

关 键 词：竞争比 在线排序 同类机 拒绝费用 不可中断 

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