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) 对带有友好释放时间在线排序问题, 给出最好的在线算法。
{{i.achievement_title}}
数据更新时间:2023-05-31
一种基于多层设计空间缩减策略的近似高维优化方法
基于自适应干扰估测器的协作机器人关节速度波动抑制方法
孕期双酚A暴露与自然流产相关性的Meta分析
基于多代理系统的主动配电网多故障动态修复策略研究
A Fast Algorithm for Computing Dominance Classes
网络上的排序问题的近似算法研究
带有维护时段的平行机排序问题近似算法研究
排序问题的博弈分析和多目标排序
装配型排序理论- - 计算复杂性、近似算法和随机算法