问题1|d_j=d|Σw_jT_j的一个全多项式近似方案

本文对具有相同工期的单机最小化加权总误工问题进行了讨论.利用强NP-困难问题1ΣwjTj的一个O(n2)时间的近似算法,把该算法得到的目标值作为问题1|dj=d|ΣwjTj的一个上界,对问题1|dj=d|ΣwjTj给出全多项式近似方案(FPTAS).已知问题1|dj=d|ΣwjTj是一般意义下的NP-困难问题,并且已经有人对该问题给出了拟多项式时间算法,本文对已有结果进行了扩充.

具有禁用区间的平行机排序时间表长问题的全多项式近似方案

近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进:提出一种新的构造方法,使应用于该算法的"补丁引理"结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.

曲面上旅行商问题的多项式时间近似方案

欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.

一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术 .应用该技术设计多项式近似方案分为两步 :( 1)对欧氏平面进行随机分割 ;( 2 )对随机分割的结果利用动态规划技术计算近似最优解 .近年来Arora利用该技术获得了TSP ,Steiner树 ,K median三个著名NP hard问题的多项式近似方案 .经验表明 ,该技术适用于欧氏平面上对“距离和”优化的NP hard问题 ,并可十分容易地推广到多维欧氏空间 .

共享制造环境下的同类机排序问题

考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本.对于机器台数是固定常数情况,该文对经典加工模型和简单退化加工模型分别提出了基于程序划分的全多项式时间近似方案.对总服务成本不超过给定上界的限制下最小化最大完工时间问题,给出了其整数规划模型.

关于工期分配与加权误工数的双指标排序问题（英文）

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型.主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果.通过这些结果,一个多目标优化问题的特征得以完整地刻画.

极小化加权总完工时间的可拒绝单机排序问题

在经典的排序问题中,工件的加工时间是固定不变的。然而,在实际生产中,工件的实际加工时间会发生变化。同时,机器通常需要进行保养,或发生故障时进行维修等原因,导致机器在某一时间段内无法工作,即机器的不可用区间。研究带有到达时间、退化效应和拒绝工件,及机器带有不可用区间的单机排序问题。在这一模型中,工件的开始加工时间越晚,其实际加工时间越大,实际加工时间是与其开始加工时间有关的函数。该问题中工件允许被拒绝。如果工件被拒绝,那么需要支付拒绝惩罚。讨论的目标函数是接受工件的加权总完工时间与所有拒绝工件的拒绝惩罚之和。首先说明该问题是一般意义NP-难的,进而利用划分程序的方法给出了一个全多项式近似方案,最后分析了该近似方案的时间复杂性。

地理位置相关移动感知系统任务分配问题研究

随着智能手机应用的普及,移动感知技术已被认为是一种高效且成本低廉的环境数据收集方式.移动感知系统中地理位置相关的最优任务分配问题是一个NP难问题.为了解决该问题,提出了一种多项式时间的近似最优的任务分配算法.该算法首先引入了单位圆盘模型中移动划分的思想,将整个监测地理空间划分为若干个子区间,并使得子区间内的最优分配方案的集合是划分前最优解的1/1+ε,这表明所设计的近似算法是一个多项式时间近似机制.随后,证明了最优任务分配问题在每个子区间内是多项式时间可解的,并设计了枚举算法求出该问题的最优解.最后,仿真实验结果表明所设计的近似最优任务分配算法的实际性能与理论分析相吻合.

极小化加权完工时间和的无界批量机器并行调度问题(英文)

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).

极小化完工时间和的有界批调度问题(英文)

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.

求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS(英文)

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题.这个问题来源于半导体制造过程中对芯片煅烧工序的排序.煅烧炉可以看成一个能同时最多加工B(<n)个工件的处理机.此外,每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间.该问题就是将工件分批后再依批次的排序加工,使得所有工件都交付后所需的时间最短.我们设计了一个用时O(f(1/ε)n5/2)的多项式时间近似方案,其中关于1/ε的指数函数f(1/ε)对固定的ε是个常数.

带有退化工件和机器维修区间的单机排序问题

考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。

带有不可用区间中断可恢复的平行机排序问题

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε>0为误差精度。

机器带不可用时间限制的简单线性恶化供应链排序问题

研究的单机供应链排序问题中,机器有一个不可用时间限制,工件的加工时间与恶化率及其开工时间有关,且工件的加工不可恢复.一个或多个完工工件可组成一个发送批由车辆发送给客户,且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送.问题的目标是最小化总发送时间与总发送费用之和.证明问题是NP-难的,提出了伪多项式时间的动态规划算法.进一步,在确定问题目标函数值的上界及下界之后,设计了一个完全多项式时间近似方案(FPTAS).

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.

环网络中的呼叫接纳控制

呼叫接纳控制是通讯网络设计与运营中的一个重要优化问题.环网络中,这一问题的目标是对于给定的具有边容量的环网络和任意利润的呼叫的集合,确定最大利润的呼叫子集并为其中每一个呼叫安排路径,使得任一边容量不被违反.对于无向和有向环网络呼叫接纳控制问题,均给出了多项式时间近似方案.

恢复鲁棒带惩罚费用的呼叫控制问题

基于带惩罚费用的呼叫控制问题,进一步讨论恢复鲁棒带惩罚费用的呼叫控制问题,并设计出一个1.58-近似算法.特别地,当赋权线路上边数为2,情景数为2时,设计了一个动态规划算法,最后基于动态规划算法思想,设计出一个全多项式时间近似方案解决该问题.

工件具有累积效应的两台同类机排序问题

研究了具有累积效应的两台同类机排序问题,目标是极小化机器总载重.半积函数在组合优化通常用于算法设计与分析.对该文中涉及的问题,用该函数设计了一个γ-完全多项式近似方案,并进行了算法分析.

带树层次加工集约束的调度问题

研究工件带释放时间、送货时间和树层次加工集约束的调度问题。工件的加工开始时间不能早于它的释放时间,送货开始时间等于它的加工完成时间。所有机器形成一个树层次结构:若某机器能加工某工件,则该机器在树上的所有祖先均能加工该工件,这些机器构成该工件的加工集。目标是极小化最大送货完成时间。对于工件释放时间和送货时间任意的一般情形,给出了一个多项式时间近似方案(PTAS)。