三机流水作业问题若干特殊情形的NP困难性(英文)

本文研究以加工总长为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工件在第二台机器上有相同的加工时间；所有工件在第一和第三台机器上有相同的加工时间；每个工件至少有一个零工序；每个工件有一个丢失的工序。

含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性

本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性.在批处理机上同时加工的工件组成一个工件批,一个工件批的所有工件同时开始、同时结束.当批处理机的容量有限时,我们证明了下列情形为强NP困难的;第一台机器是批处理机、其余两台机器是单机;第二台机器是单机、其余两台机器是批处理机;第三台机器是批处理机、其余两台机器是单机.

故障诊断中传感器配置优化的复杂性分析

为分析故障诊断中传感器(或测试点)配置优化问题的复杂性,在系统有向图模型中引入传感器配置掩码,定义了系统掩码有向图模型和多故障源集合的传感器配置掩码,利用传感器集合运算表达式形式化描述了系统故障可检测性和多故障可分辨性两个诊断性能指标,在此基础上提出了故障诊断传感器最优配置存在问题为NP困难问题的复杂性定理。通过归约到可满足问题(SAT)对提出的定理进行了严格证明,并设计一种自底向上的搜索算法寻找满足多故障可诊断性的传感器近似优化配置。

基于故障树结构函数的可靠性仿真

由于系统可靠性分析中的 NP困难 ,传统方法在处理大型复杂可维修系统可靠性问题时将面临计算量过大的问题。提出了基于故障树结构函数的可靠性数值仿真方法 ,将大型复杂可维修系统的动态仿真过程分解为一系列静态过程 ,从而解决这一问题。某舰船平台系统可靠性计算表明 ,该方法对可靠性模型的适应性强 。

求解带平衡约束圆形Packing问题的快速局部搜索算法

带平衡性约束的圆集在圆容器内的布局优化问题,属于NP困难问题。针对此问题,提出了一种快速的局部搜索算法。该算法首先构造出等价的物理模型,定义系统的能量函数,再利用最速下降法对能量函数进行优化,从而间接得到问题的近似解。在局部搜索算法中引入加速策略,提高了计算效率。最后通过两个算例的数值计算,验证了该方法的可行性和有效性。

Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.

现代物流技术中装卸工问题的拟多项式时间可解情况

装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展,促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题,本文研究限制情形下的装卸工问题,并证明是拟多项式时间可解的。

关于工件组的两机自由作业时间表问题

讨论关于工件组的两机自由作业时间表的加工全长问题。无论是对于成组加工情形还是分组情形 ,该问题都可以被证明是 NP困难的。对于成组加工的情形 ,设计了一个性能比为 5/4的近似算法 ,该算法生成的时间表作为分组情形的解 ,性能比仍能保持为 5/4。此外 ,还讨论了如何最优地求解只有一个工件组的情形。

成组加工的单机延误工件个数问题

证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制情形，由于输入规模的减少，证明了其是普通意义下ＮＰ困难的。

无容量限制的批处理机时间表问题

研究无容量限制的批处理机时间表问题 ,在工件有到达时间和工期约束下 ,证明了当工件的到达时间和工期 ,或到达时间和加工时间一致单调时 ,该问题是多项式时间可解的 ;当加工时间和工期一致单调时 ,该问题是

网络1-重心反问题的计算复杂性研究

在网络中顶点的权值可以改变的情况下,对哈明距离下以及l1模下1-重心问题的反问题进行研究。通过将哈明距离下网络1-重心问题的反问题归约为0-1背包问题,证明即使是在链式网络中,在哈明距离下该问题仍是NP困难的,并给出l1模下在一般网络中求解1-重心反问题的多项式时间算法。

一种基于扩张矩阵理论的规则学习算法

本文给出的扩张矩阵合并问题是ＮＰ困难问题的一种新的证明。由此得到了析取式最小问题是ＮＰ困难问题的新的证明。之后给出了两个扩张矩阵合并的完备策略，在此基础上给出了扩张矩阵合并的启发函数策略。

单机工件运输排序问题上界的改进

在单机排序和工件运输问题的模型中,在2T1≥T3限制下,我们证明了最劣性能比可改进为27/14.

扩张矩阵的启发式学习算法的研究

本文给出了析取式最小问题是NP困难问题的新的证明，之后给出了两个扩张矩阵合并的完备策略，在此基础上给出了扩张矩阵合并的启发函数策略，最后提出了一种新的示例学习算法—扩张矩阵的启发式学习算法．

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时，该问题等价于图上的最大匹配问题，因此存在组合强多项式时间算法；但量当机器台数为3或者多于3时，该问题是强NP困难的．

一类三机器流水作业极小化加工全长问题

一般的三台机器流水作业的加工全长问题为强NP困难的 .本文讨论它的特殊情形 ,即第二台机器上工件的加工时间均相等 .我们证明了该问题仍为强NP困难的 ,并构作了一动态规划算法 。

基于改进启发式优化算法的无线网络资源分配

无线通信网络资源的分配优化通常可描述为混合整数非线性规划(Mixed integer nonlinear programming,MINLP)问题,其本质是非凸的非确定性多项式(Nondeterministic polynomial,NP)困难问题。为了降低计算复杂度,确保分配方案的最优性能,提出利用二进制鲸鱼优化算法进行无线资源分配。在原鲸鱼优化算法(Whale optimization algorithm,WOA)的基础上,基于数值1和0之间的切换进行位置更新。根据座头鲸螺旋移动计算出的概率,来决定当前位的变化。同时,使用不同的传递函数将连续搜索空间映射到离散动作,引入惩罚方法和优化约束处理。实验分析了两个无线网络资源分配案例:保密率最大化的功率分配问题和移动边缘计算迁移。结果表明所提方法综合性能优秀,取得与同类方法相当的效果,但收敛速度更快,复杂度更低。

基于矩阵的故障树分析方法

为开发大型通用故障树分析程序、优化程序算法、降低NP困难问题,将矩阵引入到故障树分析过程中,基于矩阵对故障树进行结构编码和参数转化。阐述了应用矩阵求解故障树最小割集、最小路集、不交化最小割集、顶事件发生概率和底事件重要度的方法和步骤。使用MATLAB软件开发了相应的故障树分析程序,并将其应用于风机齿轮箱失效的研究中,程序运行速度快、计算结果准确,表明基于矩阵的故障树分析方法是有效可行的。

哈明距离下1-重心问题的反问题

主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。

一类串行工件同时加工排序问题的研究

研究目标为带权总完工时间的串行工件同时加工排序问题,证明该问题在分批数固定时的NP困难性,并基于数学规划提出随机化算法。最后,对特殊分批进行了讨论。