-
题名罩式退火过程中的多吊机调度问题
被引量：4
- 1
-
-
作者
谢谢
李彦平
-
机构
沈阳大学 辽宁省装备制造综合自动化重点实验室
-
出处
《沈阳大学学报（自然科学版）》
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
- 2
-
-
作者
谢谢
郑勇跃
-
机构
沈阳大学装备制造综合自动化重点实验室
辽宁省标准化研究院
-
出处
《沈阳大学学报（自然科学版）》
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
- 3
-
-
作者
谢谢
周莉
郑勇跃
-
机构
沈阳大学装备制造综合自动化重点实验室
中国标准化研究院
辽宁省标准化研究院
-
出处
《沈阳大学学报（自然科学版）》
CAS
2018年第4期294-298,共5页
-
基金
国家自然科学基金资助项目(71672117)
辽宁省自然科学基金资助项目(201602526)
辽宁省高等学校杰出青年学者成长计划资助项目(LJQ2014133)
-
文摘
通过探究钢铁企业精炼车间具有不干涉约束的双吊机调度问题的结构,设计了求解问题的有效的启发式算法,证明了该算法在2台吊机情况下的最坏性能比是4/3.进一步通过计算实验,并使用实际生产数据对所提出的算法进行测试,结果证明算法在可接受的时间内可以产生近优解.
-
关键词
吊机调度
强np难
启发式算法
-
Keywords
crane scheduling
np hard
heuristic algorithm
-
分类号
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
[金属学及工艺—热处理]
-
-
题名运输与倒垛集成的多吊机调度问题
被引量：1
- 5
-
-
作者
谢谢
李彦平
-
机构
沈阳大学装备制造综合自动化重点实验室
-
出处
《沈阳大学学报（自然科学版）》
CAS
2014年第3期208-215,共8页
-
基金
国家自然科学基金资助项目(71201104)
-
文摘
考虑了钢铁企业仓库管理中经常出现的多吊机调度问题.根据实际存储的需求,每个板卷已经被放在了预先指定的按两层摆放的位置上.当给定一些需求板卷时,如果一个需求板卷在上层或无板卷阻碍的下层,它可以被直接运输到指定位置(运输操作);否则,阻碍板卷需要首先被运到另外的位置(倒垛操作).所研究的问题为由吊机协调调度运输和倒垛操作.在以前研究的文献中,这两种操作都是分开研究的.目标为最小化最后一个运输到指定位置的板卷完成时间,这与最后结束操作的吊机的最早可能完工时间一致.为了更清楚地描述问题,提出了一个混合整线性规划模型(MILP).由于证明了所研究问题的特殊情况是强NP难的,这意味着所研究的问题也是强NP难的,因此提出了问题的启发式算法,给出了下界并进一步分析了算法的最坏性能.
-
关键词
吊机调度
仓库
强np难
启发式
最坏情况分析
-
Keywords
crane scheduling
warehouse
strongly np hard
heuristics
worst-case analysis
-
分类号
TG156.2
[金属学及工艺—热处理]
-
-
题名工件带就绪时间的单机供应链排序问题
- 6
-
-
作者
范静
-
机构
华东理工大学数学系
上海第二工业大学数学系
-
出处
《系统科学与数学》
CSCD
北大核心
2011年第11期1439-1443,共5页
-
文摘
研究工件带就绪时间的单机供应链排序问题,即工件到达后按何种顺序在机器上加工,并将完工工件如何由运输工具发送给客户,使得生产费用与发送费用总和最少.这里,每个工件的生产费用为工件的发送时刻,多个工件可组成一批一次发送给客户,发送费用与发送次数成正比.对于工件允许中断加工的问题,基于SRPT规则给出多项式时间的动态规划算法求解最优序;对于工件不允许中断加工的问题,证明问题是强NP难的,并提出了性能比为2的近似算法.
-
关键词
供应链排序
SRPT规则
动态规划
强np难
-
Keywords
Supply chain scheduling, SRPT rule, dynamic programming, strong np-hard.
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名钢铁企业中具有柔性分组决策的多吊机集成调度问题
- 7
-
-
作者
谢谢
郑勇跃
杨文俊
-
机构
沈阳大学装备制造综合自动化重点实验室
辽宁省标准化研究院
西安交通大学电子与信息工程学院
-
出处
《沈阳大学学报（自然科学版）》
CAS
2017年第5期389-393,共5页
-
基金
国家自然科学基金资助项目(71672117)
辽宁省自然科学基金资助项目(201602526)
辽宁省高等学校杰出青年学者成长计划资助项目(LJQ2014133)
-
文摘
以钢铁企业炼钢过程为背景,研究了一类具有柔性分组决策的多吊机调度问题.由于该问题是NP难的,在对该问题性质分析的基础上提出了一个启发式算法,对于问题的一个限制情况,证明了启发式的最坏性能,对于一般情况,算法的性能通过计算实验进行了估测.实验结果表明,所提出的启发式算法可以在允许的时间内产生高质量的解.
-
关键词
吊机调度
强np难
启发式算法
-
Keywords
crane scheduling
np-hard
heuristic algorithm
-
分类号
TG338
[金属学及工艺—金属压力加工]
-
-
题名虚拟网映射问题的计算复杂性分析
被引量：6
- 8
-
-
作者
余建军
吴春明
-
机构
衢州职业技术学院
浙江大学计算机系统结构与网络安全研究所
-
出处
《计算机科学》
CSCD
北大核心
2018年第11期87-91,共5页
-
基金
浙江省自然科学基金资助项目(LY14F020010)
国家863高技术研究发展计划项目(2015AA015602
2015AA016013)资助
-
文摘
虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。
-
关键词
虚拟网映射
计算复杂性
强np难问题
优化问题
-
Keywords
Virtual network mapping
Computational complexity
Strongly np-hard problems
Optimization problem
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名一维装箱问题的交叉算法分析
- 9
-
-
作者
李杉林
-
机构
台州学院数学与信息工程学院
-
出处
《台州学院学报》
2009年第3期1-5,共5页
-
文摘
2004年孙春玲等研究了一维装箱问题,给出了一个近似程度最好的近似值为3/2的近似算法-交叉算法.遗憾的是他们的交叉算法的近似值分析是错误的,本文通过两个反例说明了他们的错误所在,并给出一个正确的近似值分析.
-
关键词
装箱问题
强np-难
近似算法
反例
-
Keywords
Bin-Packing problem
strongly np＇hard
approximation algorithm
counterexample.
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名具有多个受限制可用时间段的单机供应链排序问题
- 10
-
-
作者
范静
-
机构
上海第二工业大学理学院
-
出处
《上海第二工业大学学报》
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
[理学—运筹学与控制论]
-
-
题名带货盘流水作业加工全长问题
- 11
-
-
作者
陈秀宏
-
机构
淮阴师范学院数学系
-
出处
《佳木斯大学学报（自然科学版）》
CAS
2003年第3期252-255,共4页
-
基金
~~
-
-
关键词
flow-shop问题
加工全长
复杂性
货盘
流水作业
三维匹配
强np-难
-
分类号
O226
[理学—运筹学与控制论]
-
-
题名具有多个不可用时间段的单机供应链排序问题
- 12
-
-
作者
范静
张峰
-
机构
上海第二工业大学文理学部
-
出处
《运筹学学报》
CSCD
北大核心
2015年第3期116-122,共7页
-
基金
上海第二工业大学应用数学重点学科建设项目基金(No.XXKZD1304)
-
文摘
在单机供应链排序问题中,机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小.对于工件加工可恢复的情况,可在多项式时间O(n^2)内得到最优序.对于工件加工不可恢复的情况,证明了问题是强NP-难的,并提出了2-近似算法.
-
关键词
不可用时间段
供应链排序
强np-难
近似算法
-
Keywords
unavailability interval, supply chain scnec/ullng, strongly NF-naro, ap-proximation algorithm
-
分类号
O224
[理学—运筹学与控制论]
-
