单机上简单线性退化工件的随机在线调度问题

• 作者: 刘辉冉 马冉
• 来源期刊: 信阳师范学院学报（自然科学版）
• 学科: 数学
• 关键词: 排序 单机 随机在线 简单线性退化
• 年，卷（期）: 2018,（4）
• 所属期刊栏目: 基础理论研究
• 页码范围: 535-538
• 页数: 4页
• 分类号: O223
• 字数: 4170字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0972.2018.04.005

摘要

研究了单机上工件具有简单线性退化效应的随机在线调度问题.工件以时间在线的方式到达,决策者对将来到达工件的信息一无所知,当工件到达之后,决策者立刻知道工件加工时间的期望,且工件加工时间的期望是开工时间的简单线性函数,直到工件完工才能知道工件的实际加工时间.目标函数是最小化工件总完工时间和的期望.对于这个随机在线调度问题,通过改变工件的释放时间给出了竞争比为1+bmax的SHIFTSDR在线算法.这与LIU M等人所研究的确定性情形的下界相匹配,因此可以证明,对所研究的问题给出的在线算法是最好可能的在线算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马冉	河南理工大学数学与信息科学学院	21	10	2.0	2.0
2	刘辉冉	河南理工大学数学与信息科学学院	5	1	1.0	1.0