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

作     者：荣建华 侯丽英 Rong Jianhua Hou Liying

作者机构：石家庄铁道大学四方学院河北石家庄051132 南京农业大学理学院江苏南京210095 

出 版 物：《嘉兴学院学报》 (Journal of Jiaxing University)

年 卷 期：2016年第28卷第6期

页      面：74-77,130页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金数学天元基金(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,并证明算法的竞争比为关于参数α的分段函数,且为紧界.