课题基金基金详情
在线和离线折衷排序研究
结题报告
批准号:
11271338
项目类别:
面上项目
资助金额:
60.0 万元
负责人:
原晋江
依托单位:
学科分类:
A0406.离散优化
结题年份:
2016
批准年份:
2012
项目状态:
已结题
项目参与者:
慕运动、张利齐、马冉、范新爱、冯琪、李文杰、刘海玲、刘其佳
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
客服二维码
微信扫码咨询
中文摘要
折衷排序是排序领域的重要研究方向,近年来又有新的发展。针对多个排序指标,在离散情形,折衷排序要求刻画所有Pareto最优点,而在连续的情形,折衷排序要求刻画trade-off曲线。本项目研究多指标下的在线和离线折衷排序,包括经典折衷排序、多代理折衷排序以及折衷重新排序。目的是在全新的理论工具的基础上寻求有效的多项式时间算法、近似算法和在线算法。对离线情形进行复杂性分析、并设计多项式时间算法及多项式时间近似算法生成问题的所有Pareto最优点或trade-off 曲线。对在线情形在分析时间位势与优化指标之间的内在联系的基础上设计具有良好trade-off竞争比的在线算法。在成果表现方面,对离线折衷排序给出完整的研究结果,并对在线折衷排序建立基本的理论构架。
英文摘要
Trade-off scheduling is an important research direction in scheduling theory, which received new development in recent years. For multiple criteria of scheduling, in the discrete version, trade-off scheduling asks to find all Pareto optimal points, and in the continuous version, trade-off scheduling asks to find the trade-off curve. This project studies the online and off-line trade-off scheduling under multi-criteria, which includes the classical trade-off scheduling, multi-agent trade-off scheduling and trade-off rescheduling. The goal of the project is to develop efficient polynomial-time algorithms, approximation algorithms and online algorithms, based on totally new theoretical tools. For the off-line version, we present complexity analysis, and design polynomial-time algorithms and polynomial-time approximation algorithms to generating all Pareto optimal points or trade-off curves. For the online version, based on the analysis for the interrelationships between the time potentials and the optimization criteria, we design online algorithms with good trade-off competitive ratios. In the aspect of the expression of the achievements,we will provide complete research results for off-line trade-off scheduling and establish fundamental theoretical framework for online trade-off scheduling.
折衷排序是排序领域的重要研究方向,发展新的研究方法并用来求解各种具有理论意义和应用前景的多指标排序模型是本项目的实施要点。本项目对折衷排序进行了深入的研究,得到了较为系统的研究进展。对离线折衷排序我们在发展各种ε-约束变异方法的前提下对重新排序、双代理排序、分批排序等模型中的多个典型的折衷排序问题给出了强多项式时间算法,部分结果突破了文献中的弱多项式时间算法;在双指标排序的计算复杂性研究中我们解决了多个历史遗留问题并对以最大延迟作为基准目标的排序反问题以及具有工件最大允许错位的重新排序模型进行了系统的研究;在折衷排序的在线算法和近似算法方面,我们研究了“时间表长与加权完工时间和的折衷”、“时间表长与最大延迟的折衷”、“总完工时间和与拒绝费用的正组合”、“加工与送货两阶段排序”等排序问题,得到了性能良好的在线算法和近似算法。受本项目资助共发表SCI期刊学术论文40篇。代表性成果如下:(1)对最小化工件错位总和与时间表长的 Pareto 最优重新排序,创建了跳跃式ε-约束变异方法,并由此得到求解全部 Pareto 最优点的强多项式时间算法;(2)对工件具有到达时间并可中断最小化两个代理的最大延迟的Pareto 最优排序问题,建立了Pareto 最优排序的EDD顺序下的Pmtn-List排序结构,然后利用工件轮廓的构思确定出所有的Pareto 最优点,进而在多项式时间求解了所研究的问题;(3)证明了单机最小化总提前及延误量问题以及GDD假设下单机最小化工件加权总误工问题的强 NP-困难性,从而解决了两个上世纪80年代遗留至今的计算复杂性问题;(4)提出并研究了折衷在线排序,并对单机同时最小化时间表长与加权完工时间和的折衷在线排序问题给出了具有最好可能的Trade-off竞争比的在线算法。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:10.1016/j.orl.2015.12.006
发表时间:2016
期刊:Oper. Res. Lett.
影响因子:--
作者:Yuan Gao;Jinjiang Yuan
通讯作者:Yuan Gao;Jinjiang Yuan
Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time
在相同机器上进行抢先调度并进行交付协调,以最大程度地缩短最大交付完成时间
DOI:10.1016/j.tcs.2015.03.046
发表时间:2015-06
期刊:Theoretical Computer Science
影响因子:1.1
作者:Youjun Chen;Lingfa Lu;Jinjiang Yuan
通讯作者:Jinjiang Yuan
On Graphs with a Unique Perfect Matching
论具有唯一完美匹配的图
DOI:--
发表时间:2015
期刊:Graphs and Combinatorics
影响因子:0.7
作者:Wang, Xiumei;Shang, Weiping;Yuan, Jinjiang
通讯作者:Yuan, Jinjiang
DOI:10.1142/s0217595914500304
发表时间:2014-08
期刊:Asia Pac. J. Oper. Res.
影响因子:--
作者:Chengwen Jiao;Wenhua Li;Jinjiang Yuan
通讯作者:Chengwen Jiao;Wenhua Li;Jinjiang Yuan
DOI:10.1007/s10255-015-0475-3
发表时间:2015-06
期刊:Acta Mathematicae Applicatae Sinica, English Series
影响因子:--
作者:Xiumei Wang;Jinjiang Yuan;Yixun Lin
通讯作者:Xiumei Wang;Jinjiang Yuan;Yixun Lin
分级指标排序与折衷指标排序研究
  • 批准号:
    --
  • 项目类别:
    面上项目
  • 资助金额:
    52万元
  • 批准年份:
    2020
  • 负责人:
    原晋江
  • 依托单位:
多指标排序研究
  • 批准号:
    11671368
  • 项目类别:
    面上项目
  • 资助金额:
    48.0万元
  • 批准年份:
    2016
  • 负责人:
    原晋江
  • 依托单位:
平行机分组工件排序的多面体方法
  • 批准号:
    10971201
  • 项目类别:
    面上项目
  • 资助金额:
    24.0万元
  • 批准年份:
    2009
  • 负责人:
    原晋江
  • 依托单位:
多代理多工序排序理论:计算复杂性与可近似性
  • 批准号:
    10671183
  • 项目类别:
    面上项目
  • 资助金额:
    23.0万元
  • 批准年份:
    2006
  • 负责人:
    原晋江
  • 依托单位:
装配型排序理论- - 计算复杂性、近似算法和随机算法
  • 批准号:
    10371112
  • 项目类别:
    面上项目
  • 资助金额:
    17.0万元
  • 批准年份:
    2003
  • 负责人:
    原晋江
  • 依托单位:
图的树分解参数与子式理论
  • 批准号:
    19871078
  • 项目类别:
    面上项目
  • 资助金额:
    6.5万元
  • 批准年份:
    1998
  • 负责人:
    原晋江
  • 依托单位:
国内基金
海外基金