最大化接收工件总权值的批处理机在线排序
- 分享到:
摘要:
研究m台无界批处理机上的在线排序问题.每个工件J_j具有一个相同的加工时间p>0,一个到达时间r_j≥0,一个权值w_j>0,一个必须交货期d_j>0.无界批处理机是指一台机器可以同时加工任意多个工件,目标是确定一个工件允许被中断重启的在线排序使得接收工件的总权值最大化.主要设计了一个在线算法并证明其竞争比为3-1/m-(4m-2)(2m^2-m)1/2/(2m^2-m).
This paper studies the online scheduling on m unbounded batch machines. Each job Jjhas a common processing time p 0,an arriving time rj≥0,a weight wj 0,a deadline dj 0. ＂Unbounded batch machines＂means that one machine can process up to countless jobs simultaneously as a batch. The goal is to determine a preemption-restart schedule which maximizes total weight of the accepted jobs. In this paper,we first design an online algorithm,and then prove that it has a competitive ratio of 3-1/m-（ 4m-2）（ 2m^2-m）^1/2/（ 2m^2-m）.
作者:
李文杰 熊建栋 翟红村
机构地区:
洛阳师范学院数学科学学院 betway官方app 数学与信息科学学院
出处:
《betway官方app 学报：自然科学版》 CAS 北大核心 2017年第1期8-14,共7页
基金:
国家自然科学基金(11501279) 河南省科技攻关计划项目(162102210265) 河南省基础与前沿技术研究计划项目(162300410085)
关键词:
在线排序 竞争比 批处理机 接收工件总权值
online scheduling competitive ratio batch machines total weight of the accepted jobs
分类号:
O224 [理学—运筹学与控制论]
