最大化接收工件总利益的在线排序研究

基本信息
批准号:11501279
项目类别:青年科学基金项目
资助金额:18.00
负责人:李文杰
学科分类:
依托单位:洛阳师范学院
批准年份:2015
结题年份:2018
起止时间:2016-01-01 - 2018-12-31
项目状态: 已结题
项目参与者:李士生,魏春艳,杜智慧,陈仁霞,李晓辉,李倩
关键词:
接收工件总利益批处理机在线算法在线排序竞争比
结项摘要

Online scheduling is one of the fastest developed research direction in modern scheduling. Online schedule to maximize total profit of the accepted jobs is a very important online scheduling problem, which can be widely applied to network service and information technology. This project mainly studies the scheduling problem of maximizing total profit of the accepted jobs in the environment of semi online or batch online scheduling, and we try to derive some innovative contributions from the following two aspects: On one hand, by exploring the new methods and new techniques to improve the two new results for the problem of online batching schedule to maximize total profit of the accepted jobs in the literature; On the other hand, by establishing the new semi online scheduling models to further study the schedule problem to maximize total profit of the accepted jobs, and plans to look for ideal lower bounds on this kind of problem, by applying adversary method and computer data analysis, then using the methods such as, delay method, multiple method, instance reduction method, and charging method, to design and analysis best possible online algorithms matching the established lower bounds.

在线排序是现代排序领域中发展最为迅速的研究方向之一。最大化接收工件总利益的在线排序是一类非常重要的在线排序问题,被广泛的应用于网络服务和信息技术领域之中。本项目主要研究半在线或批处理在线环境下的最大化接收工件总利益排序问题,并力求在以下两方面取得若干创新性成果:一、探索新方法和新技巧改进文献中关于最大化接收工件总利益批处理在线排序问题的两个最新研究结果;二、通过建立新的半在线排序模型,更深入的研究最大化接收工件总利益排序问题,并计划将计算机数据分析和对手法相结合来寻找此类问题的理想下界,然后利用延迟法、倍数法、实例归结法、Charging法等方法,设计和分析与下界相匹配的最好可能的在线算法。

项目摘要

在线排序是现代排序领域中发展最为迅速的研究方向之一。最大化接收工件总利益的在线排序是一类非常重要的在线排序问题,被广泛的应用于网络服务和信息技术领域之中。本项目对工件具有友好释放时间的半在线环境以及批处理在线环境下的最大化接收工件总利益排序问题和最小化传统指标排序问题进行了系统研究。 对最大化接收工件总权值的批处理在线排序问题设计出了一些新的在线算法并改进了文献中已有的若干研究结果;对本项目中建立的“工件具有友好释放时间”这一新的半在线排序模型,分别研究了最大化接收工件总利益排序问题和最小化传统指标排序问题,并得到一系列最好可能在线算法; 对最大化接收工件总利益的若干离线排序问题,进行了全面的复杂性分析。 受本项目资助共发表期刊学术论文11篇,其中SCI论文8篇。代表性成果如下:(1) 对工件可以被中断抢先的最大化接收工件总权值的单机Lookahead在线排序问题,设计出了新的在线算法并改进了文献中的已有研究结果;(2) 对最大化接收工件总权值的多台批处理机在线排序问题,推广了文献中的结果并设计出了新的在线算法改进了文献中的部分结果;(3) 对多组工件具有友好释放时间的单机批处理最小化Makespan半在线排序问题,设计出了最好可能的在线算法;(4) 对工件具有友好释放时间的批处理机最小化最大加权完工时间和的半在线排序问题,设计出了最优在线算法以及特殊情形下的最好可能的在线算法;(5) 对工件具有友好释放时间的最大化接收工件总权值单机半在线排序问题,根据工件长度不同设计出了若干性能良好的在线算法。

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

DOI:{{i.doi}}
发表时间:{{i.publish_year}}

暂无此项成果

数据更新时间:2023-05-31

其他相关文献

1

基于铁路客流分配的旅客列车开行方案调整方法

基于铁路客流分配的旅客列车开行方案调整方法

DOI:
发表时间:2021
2

新型树启发式搜索算法的机器人路径规划

新型树启发式搜索算法的机器人路径规划

DOI:10.3778/j.issn.1002-8331.1903-0411
发表时间:2020
3

"多对多"模式下GEO卫星在轨加注任务规划

"多对多"模式下GEO卫星在轨加注任务规划

DOI:10.19328/j.cnki.2096-8655.2022.02.002
发表时间:2022
4

长链基因间非编码RNA 00681竞争性结合miR-16促进黑素瘤细胞侵袭和迁移

长链基因间非编码RNA 00681竞争性结合miR-16促进黑素瘤细胞侵袭和迁移

DOI:
发表时间:2021
5

吹填超软土固结特性试验分析

吹填超软土固结特性试验分析

DOI:10.13544/j.cnki.jeg.2014.06.004
发表时间:2014

李文杰的其他基金

批准号:81603664
批准年份:2016
资助金额:17.00
项目类别:青年科学基金项目
批准号:61474132
批准年份:2014
资助金额:84.00
项目类别:面上项目
批准号:81173184
批准年份:2011
资助金额:54.00
项目类别:面上项目
批准号:81573151
批准年份:2015
资助金额:70.00
项目类别:面上项目
批准号:81801222
批准年份:2018
资助金额:21.00
项目类别:青年科学基金项目
批准号:81872626
批准年份:2018
资助金额:59.00
项目类别:面上项目
批准号:51209241
批准年份:2012
资助金额:27.00
项目类别:青年科学基金项目
批准号:81172716
批准年份:2011
资助金额:50.00
项目类别:面上项目
批准号:51679019
批准年份:2016
资助金额:63.00
项目类别:面上项目

相似国自然基金

1

工件可拒绝的折衷排序和在线排序

批准号:11426094
批准年份:2014
负责人:张利齐
学科分类:A0406
资助金额:3.00
项目类别:数学天元基金项目
2

工件允许重启的在线排序研究

批准号:11701148
批准年份:2017
负责人:刘海玲
学科分类:A0406
资助金额:20.00
项目类别:青年科学基金项目
3

工件可拒绝或可外包的折衷排序、在线排序和博弈排序研究

批准号:U1504103
批准年份:2015
负责人:张利齐
学科分类:A0406
资助金额:27.00
项目类别:联合基金项目
4

工件排序问题的研究

批准号:78770031
批准年份:1987
负责人:潘家轺
学科分类:G0106
资助金额:1.00
项目类别:面上项目