双目标排序的近似算法

基本信息
批准号:11401604
项目类别:青年科学基金项目
资助金额:22.00
负责人:冯琪
学科分类:
依托单位:中原工学院
批准年份:2014
结题年份:2017
起止时间:2015-01-01 - 2017-12-31
项目状态: 已结题
项目参与者:刘海玲,顾聪,张喆,李燕楠
关键词:
代理双目标排序近似算法
结项摘要

Bicriteria scheduling is an important research direction in scheduling theory, which received rapid development in recent years, and obtained much attention by the researchers. This project studies the two-agent scheduling problems with assignable due dates and two-agent scheduling problems with job rejection. For the related problems, we present complexity analysis, and for the NP-hard problems, based on totally new theoretical tools, we design efficient polynomial-time approximation algorithms. In the aspect of the expression of the achievements,we will provide related research results for bicriteria approximation algorithms and establish fundamental theoretical framework.

双目标排序的近似算法是排序领域的重要研究方向,近年来发展迅速,得到国内外同行的广泛关注。本项目研究工期可分配的两个代理排序问题和带有拒绝费用的两个代理排序问题。我们对相关问题进行计算复杂性分析、并对NP-困难问题在全新的理论工具的基础上寻求有效的多项式时间近似算法。在成果表现方面,对双目标排序的近似算法给出相关的研究结果,并建立基本的理论构架。

项目摘要

双目标排序和在线排序是排序理论中的重要研究部分,其中包括模型的建立, 问题的复杂性,NP-困难性证明,多项式时间算法的设计,近似算法的设计,在线算法的设计。我们研究了带有禁用区间的双代理标排序问题、两个工件类的双代理排序问题、工期可分配的双代理排序问题、工件可拒绝的双代理排序问题、在线排序问题等。受本项目资助共发表学术论文15篇。其中代表性成果如下:(1)对机器具有禁用区间的两个代理排序问题给出了多项式时间算法和拟多项式时间算法。(2) 对于具有提前费用的两个代理排序问题给出了多项式时间算法。(3)对具有两个工件类的两个代理排序问题给出了多项式时间算法或拟多项式时间算法。 (4) 研究了单机上具有相同工期分配和累积退化的排序问题。(5)研究了单机上带有拒绝和退化维修活动的排序。(6)对工件具有退化效应且需要考虑工件运输的在线排序问题给出了相应的在线算法。(7)对于等长工件在m台容量无限的平行批处理机上加工的在线排序问题设计出了一个最好可能的在线算法。(8) 对带有友好释放时间在线排序问题, 给出最好的在线算法。

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

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

暂无此项成果

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

其他相关文献

1

一种基于多层设计空间缩减策略的近似高维优化方法

一种基于多层设计空间缩减策略的近似高维优化方法

DOI:10.1051/jnwpu/20213920292
发表时间:2021
2

基于自适应干扰估测器的协作机器人关节速度波动抑制方法

基于自适应干扰估测器的协作机器人关节速度波动抑制方法

DOI:10.13973/j.cnki.robot.210412
发表时间:2022
3

孕期双酚A暴露与自然流产相关性的Meta分析

孕期双酚A暴露与自然流产相关性的Meta分析

DOI:10.7507/1672-2531.202205002
发表时间:2022
4

基于多代理系统的主动配电网多故障动态修复策略研究

基于多代理系统的主动配电网多故障动态修复策略研究

DOI:
发表时间:2017
5

A Fast Algorithm for Computing Dominance Classes

A Fast Algorithm for Computing Dominance Classes

DOI:
发表时间:2016

冯琪的其他基金

相似国自然基金

1

网络上的排序问题的近似算法研究

批准号:11301184
批准年份:2013
负责人:余炜
学科分类:A0406
资助金额:23.00
项目类别:青年科学基金项目
2

带有维护时段的平行机排序问题近似算法研究

批准号:11226235
批准年份:2012
负责人:陈永
学科分类:A0406
资助金额:3.00
项目类别:数学天元基金项目
3

排序问题的博弈分析和多目标排序

批准号:10971191
批准年份:2009
负责人:谈之奕
学科分类:A0406
资助金额:24.00
项目类别:面上项目
4

装配型排序理论- - 计算复杂性、近似算法和随机算法

批准号:10371112
批准年份:2003
负责人:原晋江
学科分类:A0406
资助金额:17.00
项目类别:面上项目