期刊文献+

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

Stochastic Online Scheduling on a Single Machine with Simple Linear Deteriorating Jobs
下载PDF
导出
摘要 研究了单机上工件具有简单线性退化效应的随机在线调度问题.工件以时间在线的方式到达,决策者对将来到达工件的信息一无所知,当工件到达之后,决策者立刻知道工件加工时间的期望,且工件加工时间的期望是开工时间的简单线性函数,直到工件完工才能知道工件的实际加工时间.目标函数是最小化工件总完工时间和的期望.对于这个随机在线调度问题,通过改变工件的释放时间给出了竞争比为1+b_(max)的SHIFTSDR在线算法.这与LIU M等人所研究的确定性情形的下界相匹配,因此可以证明,对所研究的问题给出的在线算法是最好可能的在线算法. The stochastic online scheduling problem is considered on a single machine with simple linear deteriorating jobs.All jobs arrive online over time,the scheduler has no any information about the jobs that would arrive in the future.Only when the jobs arrive,the scheduler can know the expectation of job’s processing time immediately,and the expectation of processing time was a simple linear function that depends on the starting time of processing the job.Until the jobs are completed,their actual processing time could be known.The goal function of this problem is to minimize the expectation of total completion time of all jobs.An SHIFT-SDR algorithm is presented to this stochastic online problem by shifting the release time of jobs,with the competitive ratio 1+b max.This ratio matches the lower bound of deterministic case that is studied by LIU M et al.Thus,this can show that our algorithm is the best possible online algorithm for the problem that we studied.
作者 刘辉冉 马冉 LIU Huiran;MA Ran(School of Mathematics and Information Science,Henan Polytechnic University,Jiaozuo 454000,China)
出处 《信阳师范学院学报(自然科学版)》 CAS 北大核心 2018年第4期535-538,共4页 Journal of Xinyang Normal University(Natural Science Edition)
基金 国家自然科学基金项目(11501171) 河南省基础与前沿技术研究计划资助项目(172102310571)
关键词 排序 单机 随机在线 简单线性退化 scheduling single machine stochastic online simple linear deterioration
  • 相关文献

参考文献2

二级参考文献16

  • 1Vestijens A P A. Online machine scheduling[D]. Nether lands: Eindhoven University of Technology, 1997.
  • 2Hall L A, Schulz A S, Shmoys D B, etal. Scheduling to minimize average completion time: Off-line and online algorithms[J].Mathematics of Operations Research, 1997,22:513-544.
  • 3Chekuri C, Motwani R, Natarajan B, et al. Approximation techniques for average completion time scheduling[J]. SIAM Journal on Computing, 2001,31:146-166.
  • 4Correa J R, Wagner M R. LP-Based online scheduling: From single to parallel maehines[J]. Mathematical Programming, 2009,119(1) :109- 136.
  • 5Megow N, Schulz A S. Scheduling to minimize average completion time revisited: Determinstic online algorithms [J]. Operations Research Letters,2004,32:485-490.
  • 6Megow N, Uetz M, Vredeveld T. Models and algorithms for stochastic online scheduling[J]. Mathematics of Operations Research, 2006,31 (3) :513-525.
  • 7MOhring R H, Schulz A S, Uetz M. Approximation in stochastic scheduling: The power of LP-based priority policies [J].Journal of the ACM, 1999,46 : 924-942.
  • 8Edmonds J. Submodular functions, matroids and certain poly hedra[J].Lecture Notes in Computer Science, 2003,2570 : 11- 26.
  • 9Gupta J N D,Gupta S K.Single-facility scheduling with nonlinear processing time[J].Computer and Industrial Engineering,1988,14(4):387-393.
  • 10Mosheiov G.Scheduling jobs under simple linear deteriorating[J].Computer and Operations Research,1994,21(6):653-659.

共引文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部