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

作     者：荣建华 侯丽英 RONG Jianhua;HOU Liying

作者机构：石家庄铁道大学四方学院基础部石家庄051132 南京农业大学理学院南京210095 

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

出 版 物：《重庆师范大学学报（自然科学版）》 (Journal of Chongqing Normal University:Natural Science)

年 卷 期：2016年第33卷第5期

页      码：7-11页

摘      要：研究了工件带有拒绝费用的两台同类机在线算法,两台机器的速度分别为1和s,s∈[1,+∞),工件逐个到达,当工件到达时,可以选择被分配到机器上进行加工并花费一定的加工时间;也可以被拒绝,但此时需付出一定的拒绝费用。进一步假定每个工件的加工时间与拒绝费用成固定比例α(α≥0),即p_j=αt_j。目标函数为使被加工工件的最大完工时间与被拒绝工件的总罚值之和最小,工件的加工不可中断。本研究设计一种在线算法URLS,并证明该算法的竞争比和下界均为关于参数α的分段函数,且当α∈[0,(s+1)^(1/2)/s+1)∪[1,+∞)时上下界相吻合,算法达到最优。

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.11721/cqnuj20160509

馆 藏 号：203190235...