NP-难相关论文
本文研究了供应链管理中的集成配送和加工的两阶段分批调度问题,在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加......
排序问题是一类经典的组合优化问题,受到了许多行业的从业人员与理论研究者的密切关注.它已成为当今世界上发展研究最为活跃、应用......
随着社会的发展,科技的进步,数据挖掘、机器学习等新型技术已经融入人们的日常生活,使生活更加便利。但随着数据量的增大,数据类型......
排序问题又称时间表理论,是组合优化的重要组成部分.它和我们的生活密切相关,在运输,冶炼,制造等方面都有广泛的应用.随着市场经济......
学位
散装物料堆场是连接内陆运输和海上运输的中转站,在出口业务中扮演着重要角色,尤其是场区的可连续作业、散料可同时堆取等优势,更......
团簇是由许多原子在原子间作用力的基础上形成的稳定形态。二元Morse团簇的启发式优化就是使用各种高效的启发式算法,寻找团簇的最......
考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件Jj都具有一个加工位置上限(k)j.也就是说,如......
最小支撑树形图问题是一类经典的组合优化问题,我们分别有朱-刘算法和Edm-onds算法来解决。本论文主要研究在有向图上支撑树形图的......
旅行商问题(Traveling Salesman Problem,简记为TSP)一直是近似算法研究领域中的一个经典的问题,然而TSP的单一的条件往往不能满足多......
在Max-sum形式的多重背包问题的基础上,研究了最小效益尽可能大的多重背包问题。我们得到了如下的结果;(1)通过三划分问题的归约证明了......
负载平衡问题是组合最优化领域中最经典的问题之一,它在网络设计、资源分配、工业管理及信息传播等问题中有着非常广泛的应用。经典......
本文主要研究了几种离散选址模型的算法。首先,本文简单阐述了设施选址问题的重要性、设施选址问题的发展及随机选址问题的研究现......
设G=(V,E)是图,D是的V子集.若不在D中的每个点都至少和D中一点相邻,则称D为G的控制集,对于不含孤立点的图G,若控制集D中的每个点也至少......
κ-平均问题是计算机科学和组合优化领域的经典问题之一.κ-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖......
考虑带有拒绝工件和机器维修区间的单机排序问题.目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要......
传统的设施选址问题一般假设所有顾客都被服务,考虑到异常点的存在不仅会增加总费用(设施的开设费用与连接费用之和),也会影响到对......
柔性车间作业调度问题(FJSP)作为经典车间作业调度问题(JSP)的扩展,早在上个世纪已经被证明为是NP-难的问题。目前启发式搜索方法作为......
讨论一类工件的加工时间受资源约束的单机排序问题1|pj=bj-ajuj,∑uj≤U|∑wjCj,给出它的最优解的两个性质,证明该类问题是NP-难的......
讨论了转换瓶颈(SB)算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的......
PCP定理是近十年来计算复杂性领域内的重要成果之一,介绍了从图灵计算模型到概率可验证明(PCP)计算模型的演变过程、PCP系统的基本理......
车间作业调度算法是影响车间生产效率的重要因素之一。由于调度算法属于NP-难问题,至今仍然没有办法在有限时间内找到最优解。文章......
考虑了具有数目约束的负载平衡问题的一种特殊情形,称之为2-半匹配问题。分析了此问题在3种目标函数下的计算复杂性,并设计了相应......
介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题——“最......
簇图编辑问题是一个重要的NP-难问题。作为相关性聚类问题的一个特例,它在计算生物等领域有着重要的应用。参数计算理论出现后,参......
研究了一类具有准备时间和移出时间约束的单服务器并行机调度问题.这个问题概括了工件仅需要准备操作的经典单服务器并行机调度问......
排序是为加工若干个工件或者完成若干项任务而对资源按时间进行高效率的分配,本文讨论一个工件的情况下对多台机器进行排序,从而使......
为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研......
UFCLP问题是在经典p-中位问题上去掉中位点个数的限制,并且在目标函数中加入设施的建设费用。目前有很多启发式算法用来解决这类NP......
本文描述了一种解决车间作业调度最短完工时间问题的有效禁忌搜索算法,建立了该问题的数学模型,并提出了新的邻域构造方法。该算法利......
供应链排序研究了两个部分的问题,第一部分是权重不一致的工件在一台机器上加工,第二部分是把加工完的工件分成若干批按照某种运输......
描述了一种解决作业车间调度最短完工时间问题的混合式算法.该算法基于禁忌搜索和转换瓶颈技术.算法中利用了多种禁忌搜索方法.为了得......
针对柔性作业车间调度问题(Flexible Job Shop Scheduling Problem,FJSP)的求解特点,提出了一种混合差分进化算法,该方法以最小化......
描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法.该算法基于禁忌搜索技术.算法中利用了新的禁忌搜索方法.从对一......
数据挖掘算法现面临挑战,这个挑战就是要处理日益增长的复杂对象。对于图数据,随机游走核是有力的容错图匹配方法。由于随机游走核......
We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the c......
研究了钢铁企业物流系统中的一类单吊机调度问题.在板坯仓库中,为了最小化全部板坯的总热量损失,通过优化吊机的操作,以确定阻碍板......
在板材切割的过程中,一个优秀的切割方案可以大大提高板材的利用率,从而减少板材的浪费,节约厂商的成本开销,为其带来更大的利润。......
科学技术正在迅速发展,计算机已经融入到国民生产的各个领域中,软件产品正在逐渐成为社会生产中不可缺少的辅助工具。排样问题广泛......
学位
选址问题是运筹学中的经典问题之一,在生产生活甚至军事中都有着非常广泛的应用。网络是大多数选址主体进行选址决策的载体,所以对......
研究资源定时投放的单机排序问题,目标为极小化工件的总完工时间,首先采用多项式时间归约法证明了该问题即使在每个工件的资源需求......
文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发......
研究了一类极小化加权总完工时间的可拒绝分批排序问题.首先证明了该问题是NP-难的,然后对于所有工件的加工时间相同的情况,给出了......
结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w,c)和一种长度为L的特定材料,要在图G中寻找一......
背包问题是组合最优化理论研究中的一个经典问题,也是一个重要问题。近些年,背包问题及其各种变形与推广问题都是研究热点。经典背......
以企业生产和内部物流为背景,研究生产前半成品运输与无界批处理机生产的协调调度问题.位于存储区的工件由运输机运送到批处理机上进......
研宄了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题.研宄中首先利用原始对偶技巧得到9-近似算法,然后利用贪婪增广......
研究了具有恶化加工时间和批处理机的一类超前有奖延误受罚的排序问题.由于 是NP一难的,主研究了单机和平行机的多项式时间可解情形,......
考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如......