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

Online Scheduling on Three Identical Machines with Rejection

作　　者：荣建华[1] 侯丽英[2] Rong Jianhua Hou Liying(Sifang College, Shijiazhuang Tiedao University , Hebei, Shijiazhuang 051132, 2. College of Sciences, Nanjing Agricultural University, Nanjing, Jiangsu210095)

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

出　　处：《嘉兴学院学报》2016年第6期74-77,130,共5页Journal of Jiaxing University

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

摘　　要：研究了工件带有拒绝费用的三台同类机在线算法:假定有三台同类机,速度分别为s_1=s_2=1,s_3=s(s≥1).n个工件J_1,J_2,…,J_n,每个工件的加工时间与拒绝费用成固定的比例α(α≥0),即p_j=αt_j.当α较大时,即工件的拒绝费用相对于加工时间较大,则将此工件接收加工;当α较小时,即每个工件的拒绝费用相对于其加工时间较小,此时将工件拒绝.目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小.工件的加工不可中断.设计了在线算法URL,并证明算法的竞争比为关于参数α的分段函数,且为紧界.An on-line scheduling issue on three identical machines with rejection is researched. Supposing there are three identical machines with their speeds of s1=s2=1,S3=s（s≥1）andnjobs： n J1,J2,…,Jn,and （ a≥O）, and the proportion of the processing time and rejection of each job, is given, i. e. pj = atj. Whena becomes bigger, a job is rejected. 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 not allowed. For this version, an on-line algorithm URL is presented and a competitive ratio is given.

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

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