-
题名两个逆网络选址问题的计算复杂性
被引量：8
- 1
-
-
作者
杨晓光
张建中
蔡茂诚
-
机构
中国科学院数学与系统科学研究院系统科学研究所
香港城市大学数学系
-
出处
《系统科学与数学》
CSCD
北大核心
2002年第3期321-327,共7页
-
基金
香港高校基金会(CERG CITYU-9040651)
国家自然科学基金(70071045
19971001)资助课题.
-
文摘
本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.
-
关键词
计算复杂性
网络选址
逆问题
强np困难
中心选址问题
连通图
-
Keywords
Network location, reverse problem, strongly np-hard.
-
分类号
O157.5
[理学—数学]
O224
[理学—基础数学]
-
-
题名罩式退火过程中的多吊机调度问题
被引量：4
- 2
-
-
作者
谢谢
李彦平
-
机构
沈阳大学 辽宁省装备制造综合自动化重点实验室
-
出处
《沈阳大学学报（自然科学版）》
CAS
2012年第1期12-19,共8页
-
基金
国家自然科学基金资助项目(61104029)
辽宁省教育厅基金资助项目(L2011207)
-
文摘
研究了钢铁企业罩式退火中的多吊机调度问题,目标函数是最小化最后一个板卷的退火完工时间.通过考虑机器和吊机位置,建立了混合整数规划模型,并提出了一种整合的方法以降低问题的难度同时保持问题的本质.然而,即使是整合后的问题也是强NP难的.进一步提出了包括分配和调度的两阶段启发式算法.在分配阶段,利用动态规划先将每个吊机分配给唯一的子区块,再进行机器的分配.调度阶段采用最早需要操作阶段优先的策略.最后,算法的有效性通过绝对性能分析的角度给出了估测.
-
关键词
吊机调度
罩式退火过程
强np难
启发式
绝对性能分析
-
Keywords
crane scheduling
batch annealing process
strongly np-hard
heuristics
absolute performance analysis
-
分类号
TG156.2
[金属学及工艺—热处理]
-
-
题名带有机器卸载不延误约束的多吊机调度问题
被引量：4
- 3
-
-
作者
谢谢
郑勇跃
-
机构
沈阳大学装备制造综合自动化重点实验室
辽宁省标准化研究院
-
出处
《沈阳大学学报（自然科学版）》
CAS
2017年第2期118-124,共7页
-
基金
国家自然科学基金资助项目(71672117)
辽宁省自然科学基金资助项目(201602526)
辽宁省高等学校杰出青年学者成长计划资助项目(LJQ2014133)
-
文摘
针对钢铁企业冷轧阶段罩式退火过程,考虑了一类带有机器卸载不延误约束的多吊机调度问题.给出了避免吊机碰撞和保证机器卸载不延误的一些可行性质.基于这些性质,提出了一个启发式算法,该算法的计算复杂性与吊机、工件和机器的数目有关.同时,给出了问题的一个下界.分别通过理论分析和计算实验,证明了启发式算法的最坏性能和平均性能.
-
关键词
罩式退火过程
吊机调度
强np难
启发式算法
最坏性能分析
-
Keywords
batch annealing process
crane scheduling
strongly np-hard
heuristic algorithm
worst case analysis
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名钢卷仓库中的吊机调度问题
被引量：2
- 4
-
-
作者
谢谢
李彦平
-
机构
沈阳大学装备制造综合自动化重点实验室
-
出处
《沈阳大学学报（自然科学版）》
CAS
2014年第2期159-165,共7页
-
基金
国家自然科学基金资助项目(71201104)
-
文摘
研究了钢铁企业冷轧原料库中的吊机调度问题.将吊机的运输和倒垛操作集成考虑,目标函数为将全部需求板卷运输到指定位置的时间最小化.对于该问题,首先提出了一个混合整规划模型,进一步证明了该问题是强NP难的.基于对问题性质的分析,针对无倒垛操作的特殊情况,提出了多项式时间可解的最优算法.对于问题的一般情况,提出了一个启发式算法并分析了它的最坏情况.
-
关键词
吊机调度
仓库
强np难
启发式
最坏情况分析
-
Keywords
crane scheduling
warehouse
strongly np-hard
heuristics
worst-case analysis
-
分类号
TG156.2
[金属学及工艺—热处理]
-
-
题名一维装箱问题的交叉算法分析
- 5
-
-
作者
李杉林
-
机构
台州学院数学与信息工程学院
-
出处
《台州学院学报》
2009年第3期1-5,共5页
-
文摘
2004年孙春玲等研究了一维装箱问题,给出了一个近似程度最好的近似值为3/2的近似算法-交叉算法.遗憾的是他们的交叉算法的近似值分析是错误的,本文通过两个反例说明了他们的错误所在,并给出一个正确的近似值分析.
-
关键词
装箱问题
强np-难
近似算法
反例
-
Keywords
Bin-Packing problem
strongly np＇hard
approximation algorithm
counterexample.
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名单机工件运输排序问题上界的改进
- 6
-
-
作者
汪松玉
陈友军
-
机构
河南农业大学信息管理学院
华北水利水电学院数学与信息科学学院
-
出处
《河南科学》
2008年第3期268-271,共4页
-
基金
河南省自然科学基金(2007110013)
-
文摘
在单机排序和工件运输问题的模型中,在2T1≥T3限制下,我们证明了最劣性能比可改进为27/14.
-
关键词
启发式算法
最劣性能比
强np困难
-
Keywords
heuristic
worst-case performance
strongly np-hard
-
分类号
O157.5
[理学—数学]
-
-
题名两类极小化最大加权完工时间排序问题研究
- 7
-
-
作者
臧西杰
李士生
-
机构
郑州大学数学与统计学院
中原工学院理学院
-
出处
《佛山科学技术学院学报（自然科学版）》
CAS
2014年第3期18-20,共3页
-
基金
国家自然科学基金数学天元基金资助项目(11326191)
河南省自然科学基金资助项目(132300410392)
-
文摘
研究两个单机排序问题,目标函数均是最大加权完工时间。对于问题1‖maxwjcj,证明了LW规则序是最优排序,而问题1|rj|maxwjcj,用3-划分问题归结,证明是强NP困难的。
-
关键词
最大加权完工时间
排序
到达时间
LW规则
强np困难
-
Keywords
maximum weighted completion time
scheduling
release date
LW rule
strongly np-hard
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名具有多个受限制可用时间段的单机供应链排序问题
- 8
-
-
作者
范静
-
机构
上海第二工业大学理学院
-
出处
《上海第二工业大学学报》
2016年第1期45-49,共5页
-
基金
上海第二工业大学青年教师培养科研项目(No.201513)资助
-
文摘
在文中所研究的单机供应链排序问题中,机器可用时间段的长度不大于给定常数,且每个不可用时间段长度确定。工件仅可以在机器的可用时间段内被加工,完工后可与其他完工工件组成一批,由一个容量无限制的运输工具发送给客户。运输工具在机器的每个可用时间段结束时间进行发送,且每次发送的费用固定。问题的目标是安排工件的加工、发送,以及机器的不可用时间段,以使总发送时间与总发送费用之和达到最小。对于工件允许中断的情况,可在多项式时间O(n log n)内得到最优序(n为工件的个数)。对于工件不允许中断的情况,证明了问题是强NP-难的,并提出了2-近似算法。
-
关键词
可用时间段
供应链排序
强np-难
近似算法
-
Keywords
availability interval
supply chain scheduling
strongly np-hard
approximation algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名虚拟网映射问题的计算复杂性分析
被引量：5
- 9
-
-
作者
余建军
吴春明
-
机构
衢州职业技术学院
浙江大学计算机系统结构与网络安全研究所
-
出处
《计算机科学》
CSCD
北大核心
2018年第11期87-91,共5页
-
基金
浙江省自然科学基金资助项目(LY14F020010)
国家863高技术研究发展计划项目(2015AA015602
2015AA016013)资助
-
文摘
虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。
-
关键词
虚拟网映射
计算复杂性
强np难问题
优化问题
-
Keywords
Virtual network mapping
Computational complexity
strongly np-hard problems
Optimization problem
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名两台机器流水作业中带成组加工的最大迟后问题
被引量：2
- 10
-
-
作者
陈跃
孙世杰
宋政芳
何龙敏
-
机构
上海大学数学系
-
出处
《应用科学学报》
CAS
CSCD
2004年第2期247-251,共5页
-
文摘
考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为Lmax.文中指出该问题为NP-hard后给出了其多项式可解的特例并构造了相应的动态规划算法.
-
关键词
排序
批处理机
最大迟后
强np-hard
多项式可解
流水作业
成组加工
-
Keywords
scheduling
batch processor
maximum lateness
strong np-hard
polynomial time algorithm
-
分类号
TH162.1
[机械工程—机械制造及自动化]
O223
[理学—运筹学与控制论]
-
-
题名运输与倒垛集成的多吊机调度问题
被引量：1
- 11
-
-
作者
谢谢
李彦平
-
机构
沈阳大学装备制造综合自动化重点实验室
-
出处
《沈阳大学学报（自然科学版）》
CAS
2014年第3期208-215,共8页
-
基金
国家自然科学基金资助项目(71201104)
-
文摘
考虑了钢铁企业仓库管理中经常出现的多吊机调度问题.根据实际存储的需求,每个板卷已经被放在了预先指定的按两层摆放的位置上.当给定一些需求板卷时,如果一个需求板卷在上层或无板卷阻碍的下层,它可以被直接运输到指定位置(运输操作);否则,阻碍板卷需要首先被运到另外的位置(倒垛操作).所研究的问题为由吊机协调调度运输和倒垛操作.在以前研究的文献中,这两种操作都是分开研究的.目标为最小化最后一个运输到指定位置的板卷完成时间,这与最后结束操作的吊机的最早可能完工时间一致.为了更清楚地描述问题,提出了一个混合整线性规划模型(MILP).由于证明了所研究问题的特殊情况是强NP难的,这意味着所研究的问题也是强NP难的,因此提出了问题的启发式算法,给出了下界并进一步分析了算法的最坏性能.
-
关键词
吊机调度
仓库
强np难
启发式
最坏情况分析
-
Keywords
crane scheduling
warehouse
strongly np hard
heuristics
worst-case analysis
-
分类号
TG156.2
[金属学及工艺—热处理]
-
-
题名一类三机器流水作业极小化加工全长问题
- 12
-
-
作者
陈秀宏
-
机构
淮阴师范学院数学系
-
出处
《淮阴师范学院学报（自然科学版）》
CAS
2002年第2期1-5,共5页
-
基金
江苏省教育厅自然科学基金资助项目 (0 0KJD110 0 0 1)
南京大学博士后基金资助项目 (0 2 0 3 0 0 3 0 2 2 )
-
文摘
一般的三台机器流水作业的加工全长问题为强NP困难的 .本文讨论它的特殊情形 ,即第二台机器上工件的加工时间均相等 .我们证明了该问题仍为强NP困难的 ,并构作了一动态规划算法 。
-
关键词
流水作业
强np困难
动态规划法
可求解情形
-
Keywords
flop shop
strongly np hard
dynamic programming algorithm
solvable cases
-
分类号
O224
[理学—运筹学与控制论]
-
