有序流水作业时间表问题是NP-困难的

讨论两台机器上的有序流水作业时间表问题 ,证明两台机器上的有序流水作业时间表问题是NP -困难的 .

一个具有两类工件的多目标排序的NP-困难性

文章考虑具有两个工件集的单机排序问题.第一个工件集J1以加权完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小,并证明该问题是强NP-困难的.

单可变资源最小化加权完工时间和排序问题的强NP-困难性(英文)

Baker和Nuttle提出了下述单可变资源排序问题:n个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.

有向网络中最大容量支撑树形图扩容问题

针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA),采用权重差最小换弧方法设计时间复杂度为O(mn)的多项式时间算法。

动态网络最短路问题的复杂性与近似算法

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.

一种快速求解TSP问题的遗传算法

文章受求最短路径算法的启发,提出一个启发算子用于遗传算法求解TSP问题,通过50,144,150等城市的TSP问题求解,表明该算法求解速度快并且解的质量也非常好。

并行分批排序问题综述

并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序问题的最新进展作了全面的介绍,指出了许多尚未解决的问题和许多新的研究方向,给出了丰富的参考文献,旨在把感兴趣的读者迅速带到此研究领域的前沿.

求解Hamming距离下的最短路改进问题的一个近似算法

研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法.

Hamming距离下树型网络的最短路改进问题

研究Hamming距离下树型网络的最短路改进问题,通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题并求解.该研究方法在一定程度上推广了已有的结果.该问题的研究有助于设计求解一般的Hamming距离下的最短路改进问题的有效近似算法.

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

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

含装卸工调配的物流车辆配送路径问题的研究

考虑到物流配送车辆路径问题中要涉及货物的装卸作业,将装卸工调配问题和车辆路径问题相结合提出了含装卸工调配的物流车辆配送路径问题,给出了以总运输费用最小、总装卸工人数最少为目标函数的双目标0-1混合整数规划问题的数学模型.按目标函数的主次分2个阶段对该问题进行求解;最后,将装卸工人数最少转化为装卸费用最小将该模型进行了推广。

有区间约束单机延误排序问题

研究一类推广的从准备时间ｒｉ到交工期ｄｉ的多重ｒ／ｄ区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是ＮＰ—困难的，对问题的特殊情形证明了它是多项式时间可解的。

求解Hamming距离下单位型单发点树型网络最短路改进问题的算法

给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法.

带单服务器和相同加工时间的流水作业排序问题

研究带单服务器和相同加工时间的两台机器的流水作业排序问题,证明该问题是强NP-困难的,引入一个简单的贪婪算法证明其紧界是3/2.

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.

m台机器上流水作业时间表问题的复杂性及一种新的启发式算法(英)

研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的。给出一种新的启发式算法,并证明该算法的最坏性能比是(m+1)/2,且上界是紧的。

关于Menger图和Menger数的若干结果

该文研究Menger图和Menger数.主要结果如下(1)对任意的n≥4,n立方体Qn不是Menger图.解决了Sampathkumar提出的未解问题2.(2)如果G是一个偶图,则m(G)=β0(G),其中m(G)是G的Menger数,β0(G)是G的独立数.部分解决了Sampathkumar提出的未解问题3.(3)“确定图的Menger数”问题是NP-困难的.

具有准备时间和延迟时间的自由作业问题的复杂性

讨论具有准备时间和延迟时间的自由作业问题 。

带有固定工件的一个单机排序问题

本文考虑带有固定工件的一个单机排序问题,证明了该问题是NP-困难的并给出了它的一个动态规划算法,证明该问题是拟多项式时间可解的。

带运输时间的Flow-shop时间表问题

研究带运输时间的流水作业时间表问题,同一工件在一台机器上完工之后,在另一台机器上开始加工,且运输过程只能由机器R完成,证明在只有两台机器的情况下,该问题是强NP-困难的,并构造一个启发式算法,证明该算法的紧界为2.