NP-困难相关论文
针对有向网络中最大容量支撑树形图扩容问题（EMCSA）,由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并......
排序问题是组合优化领域的一个重要分支，它有着重要的应用背景和深刻的理论意义．而分批排序是继经典排序之后的较新排序模型之一．本文......
排序是一类重要的组合最优化问题,是运筹学中的一个重要分支。它产生的背景主要是机器制造,后来被广泛应用于计算机系统、运输调度......
排序论是组合最优化领域的一个重要研究方向.它有着广泛的应用背景和深刻的理论意义,常常应用于军事、经济、运输、管理和计算机科......
在最近的50年中,机器排序已经成为组合最优化中最重要和最活跃的研究课题之一.在大多数经典的排序文献中,所有的工件都必须安排在......
该文从集合划分的拟多项式算法入手,给出了扩展的集合划分的最优化问题的拟多项式算法,并以此解决了具有同一延迟时间、工序加工时......
本文的工作是Baker，Smith，Agentis等人的研究工作的发展。研究的目标函数有Cmax，∑Cj，Lmax，maxWjCj，∑WjCj以及maxVj。主要结果如下：定理1......
控制集问题是组合优化理论中一个有意义的，重要的研究领域。给定无向图G=(V, E)和顶点子集S(∪)V，如果对于Vv∈V，v∈S或v与S中的元素......
在工程项目的实施管理中,人们首先要关心的问题是,如何合理的安排和调度工程内部各项工序的施工,使整个工程尽可能快而省地完成。......
研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,...,n-1},每条边ei=(i,i+1)和......
关于共同宽容交货的单机排序问题,对于宽容区间大小给定,位置不固定的情况,给出了5条性质,证明该问题是NP-困难的.......
设计了解顶点覆盖问题的贪心算法，并证明其相对比率η≤H(d)，d为图中最大的顶点度数，H(d)=∑1/j(j=1，2，……，d).当d≤3时，解的精确度有明......
排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡，由此提出工期分配的双目标排序问题．关于工期分配与加权误工数的单机......
研究带单服务器和相同加工时间的两台机器的流水作业排序问题,证明该问题是强NP-困难的,引入一个简单的贪婪算法证明其紧界是3/2.......
研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条......
研究Hamming距离下树型网络的最短路改进问题，通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题......
部分控制集问题是对于给定的顶点赋权图G=（V，E；c）和正整数K，寻找图G-个顶点子集丁，使得在其控制下的顶点个数不小于K且T中顶点权和达到最......
研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的.给出一种新的启发式算法,并证明该算法的最坏性能比是(m......
在本文中,我们考虑了工件可拒绝的单机重新排序问题.假设有一批初始工件已经被排好顺序准备加工.然而,在开始加工之前,又有一批新......
研究一类推广的从准备时间ri到工期di的多重r/d区间排序问题-有区间约束单机延误排序问题，就该问题的一般情形而言证明了它是NP-困......
讨论转盘上的Flow-shop排序问题,当运送不相等且只有一台机器的情况下,转盘上的Flow-shop排序问题是强NP-困难的.......
本文考虑带有固定工件的一个单机排序问题，证明了该问题是NP-困难的并给出了它的一个动态规划算法，证明该问题是拟多项式时间可解的......
该文研究Menger图和Menger数. 主要结果如下(1)对任意的n≥4, n立方体Qn不是Menger图. 解决了Sampathkumar提出的未解问题2.(2)如......
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法，并研究了一般树型网络下该问题的性质．解......
建立数学规划模型来研究排序问题是一件有意义的工作.本文对单机分批带到达时间的最大完工时间排序问题1|B,rj|Cmax(属NP-困难,LIU......
在求解大规模NP-困难的最优化问题方法中，列生成技术越来越受到重视．本文研究工件带有与加工次序有关的安装时间的单机排序问题，首先......
本文对两个加工可拒绝的无界批量分批排序问题1｜B≥n，rej｜∑ωjTj＋TP和1｜B≥n，rej｜∑ωjUj＋TP进行了研究，对这两个问题分别给出了伪多项式时......
讨论两台机器上的有序流水作业时间表问题，证明两台机器上的有序流水作业时间表问题是ＮＰ－困难的。......
研究带运输时间的流水作业时间表问题，同一工件在一台机器上完工之后，在另一台机器上开始加工，且运输过程只能由机器R完成，证明在只有......
讨论具有准备时间和延迟时间的自由作业问题,利用三划分问题证明具有准备时间和延迟时间的自由作业问题是强NP-困难的.......
考虑到物流配送车辆路径问题中要涉及货物的装卸作业，将装卸工调配问题和车辆路径问题相结合提出了含装卸工调配的物流车辆配送路径......
研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输：加工阶段是一台加工机器逐个加工工件;运输阶段是无......
合作对策考虑的是如何将收益v(N)合理地分配给联盟N中的成员。根据不同的合理性要求产生了不同的对策解的概念,如核心,核子等等。......
在过去的六十年里,排序已经成为运筹学和组合最优化中最重要和最活跃的分支之一.然而,在大多数经典排序文献中,所有的工件都必须安......
在设计计算机网络和通讯网络时，为了避免和最大限度减少因网络通讯中断而带来的损失，设计者必须考虑网络的稳定性．因此，网络设计的基本......
拍卖模型可描述如下:设有物品集合M和竞价人集合为N;每个竞价人得到某些物品都会产生一定的利益,可用效用函数vi : 2M→R+ (i∈N)......
并行分批排序是兴起于上世纪末的一类新型排序问题，它最初来源于半导体生产中的芯片测试过程，有重要的应用价值，在理论上也有重要的意......
