您好,欢迎来到绿色技术银行!
登录 注册
成果库
精选库
新型排序问题的理论与算法研究

0

登记号:G20200844

所属行业:科学研究和技术服务业

学科分类:组合最优化;

关键词: 竞争比 排序 复杂性 算法 性能比

绿色分类:其他资源效率提升;

  • 基本信息
成果名称: 新型排序问题的理论与算法研究
成果登记号: G20200844 学科分类: 组合最优化;
绿色分类: 其他资源效率提升; 项目关键词: 竞争比  排序  复杂性  算法  性能比
推荐单位:

华东理工大学

成果所处阶段: 成熟应用阶段
合作方式: 合资合作, 成果所属行业: 科学研究和技术服务业
国家/地区: 中国 知识产权: 发明专利,其他
简介: 点击查看

本研究项目属于数学、运筹学和理论计算机科学的交叉领域,主要研究在线排序、网络排序、批处理排序和代理排序等新型排序问题,建立问题的数学模型,分析问题的复杂性与可解性,设计高效的最优算法、近似算法或在线算法,分析算法的性能比或竞争比或进行数值模拟。项目的主要科学贡献是:(1) 关于在线排序,开展了在线单机和平行机极小化完工时间和问题、在线批处理机排序问题、在线流水作业排序问题的开拓性研究,提出了问题的下界,设计了最优算法,成功解决了Stougie教授于1995年提出的猜想等;在等待策略、最小反例和gap技巧等研究方法上有深入的发现与应用。(2) 在国内最早对网络排序这一组合最优化研究的前沿领域进行研究,并取得突破性研究成果。研究了线型网络上带有正则目标函数的网络排序和路径问题,基本彻底地解决了其复杂性分类,并设计了高效的近似算法;证明了树形网络上两台机器流水作业问题的NP困难性,从而解决了Averbakh和Berman的猜想;证明了一般网络上两台机器流水作业问题存在同顺序最优解这一重要结论;就若干网络排序问题给出了当前最好的近似算法。(3) 在国内最早进行批处理机排序研究,解决了无容量限制的批处理机排序问题的复杂性分类,解决了工件有就绪时间约束时极小化最大完工时间这一基本问题的复杂性,并首次给出了在线算法的竞争比下界。在无容量限制的多台批处理机最大完工时间问题的在线算法研究方面,给出了第一个最优算法。(4) 项目组是国内最早进行代理排序研究的小组之一,在平行机两代理排序研究方面,就一个代理的时间表长为约束,极小化另一个代理的时间表长或完工时间和的情形,提出了FPTAS算法,就同时极小化两个代理的时间表长得到了当前最好的近似算法;关于两台平行机上的多代理最大完工时间问题,设计了一个具有最好性能比的近似算法,并证明了该性能比是紧的。项目组的原创新性研究成果主要发表在Journal of Scheduling、Operations Research Letters、Discrete Applied Mathematics、Networks 、European Journal of Operational Research、Annals of Operations Research、Theoretical Computer Science等国际重要专业学术期刊上。项目组以第一作者或通讯作者发表的论文被SCI数据库收录论文54篇,总计Web of Science核心合集引用次数为485,8篇代表性论文的Web of Science核心合集引用次数为185,其中SCI他引次数为163。

姓名: 鲁习文 性别:
出生日期: 2020-08-27 职务:
国籍(地区): 中国 联系地址: 上海市徐汇区梅陇路130号
电子邮件: cg@ecust.edu.cn
相似的成果
匹配的需求

无记录

相关专家
绿色科技信息网