几个带有可变加工时间排序问题的算法研究

发布时间：2017-10-20 16:04

  本文关键词：几个带有可变加工时间排序问题的算法研究

  更多相关文章： 排序 维修 学习和恶化 拒绝 资源

【摘要】：在实际问题中,由于机器的磨损、工人熟练程度的改变、分配资源等原因,工件的实际加工时间往往会受到影响。也就是工件的实际加工时间与其基本加工时间、加工过程中所排位置、开始加工时间和所分配的资源有关。同时,由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制。本文研究的可用性限制是不可恢复的,即如果工件在维修之前没有加工完,则在维修之后将重新开始加工。本文研究同时带有学习效应和恶化效应的排序问题。对于机器带有不可用区间的情况,分别讨论了工件可被拒绝和不拒绝的排序问题。同时还研究了带有多次维修且维修时间不固定的单机排序问题。具体内容概括如下:1)对于工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关,且机器带有一个不可用区间的情况,分别研究了工件不可以被拒绝加工及可被拒绝的问题。(1)对于工件不可以被拒绝的情况,研究了目标函数为总完工时间的单机和两台平行机排序问题。分别给出了拟多项式时间的动态规划算法,并分析了算法的复杂性。特别地,对于一台机器只在零时刻开始维修、另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为4O(n)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。(2)对于工件可以被拒绝的情况,研究了目标函数为拒绝工件的总惩罚与接受工件的总完工时间之和的单机和两台平行机排序问题。给出了对应的拟多项式时间的动态规划算法,并分析了算法的复杂性。2)工件的实际加工时间与其基本加工时间、加工过程中所排位置、开始加工时间和所分配的资源有关。机器需要进行多次维修,并且最大维修次数是给定的。对于每个工件的学习效应参数都相同的情况,讨论的目标函数分别为:(1)最大完工时间与资源分配总费用之和;(2)总完工时间与资源分配总费用之和。对于每个工件的学习效应参数都不相同的情况,研究的目标函数为最大完工时间与资源分配总费用之和。将上述问题都转化成指派问题,从而得到多项式时间的最优解。
【关键词】：排序 维修 学习和恶化 拒绝 资源
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 绪论7-12
• 1.1 排序问题研究背景7-8
• 1.2 带有学习效应和恶化效应的排序问题的研究现状8-9
• 1.3 带有可用性限制的排序问题的研究现状9-10
• 1.4 带有拒绝工件的排序问题的研究现状10
• 1.5 带有资源分配的排序问题的研究现状10-11
• 1.6 本文的主要研究内容11-12
• 第二章 带有可变加工时间和可用性限制的排序问题12-20
• 2.1 引言12
• 2.2 问题描述12
• 2.3 单机问题12-15
• 2.4 两台平行机问题15-19
• 2.5 结束语19-20
• 第三章 带有可变加工时间和维修单机排序问题20-31
• 3.1 引言20
• 3.2 问题描述20-21
• 3.3 相同学习效应参数的最大完工时间与资源分配总费用之和21-25
• 3.4 相同学习效应参数的总完工时间与资源分配总费用之和25-27
• 3.5 不同学习效应参数的最大完工时间与资源分配总费用之和27-30
• 3.6 结束语30-31
• 第四章 带有可变加工时间、可用性限制和拒绝的排序问题31-37
• 4.1 引言31
• 4.2 问题描述31
• 4.3 单机问题31-34
• 4.4 两台平行机问题34-36
• 4.5 结束语36-37
• 结论与展望37-38
• 参考 文献38-41
• 致谢41-42
• 个人简历及在学期间的研究成果和发表的学术论文42

【相似文献】

中国期刊全文数据库 前10条

1 周泓,张惠民;求解多目标作业排序问题的遗传算法[J];系统工程理论与实践;2001年08期

2 周泓,姬彬;求解作业排序问题的通用混合遗传算法研究[J];系统工程理论与实践;2001年12期

3 陈德伍,张 峰;一类新的可控排序问题(英文)[J];运筹学学报;2001年04期

4 张瑞,刘国珍;单机排序问题最优解方法[J];聊城师院学报(自然科学版);2001年02期

5 黎群;单台机器多目标作业排序问题的探讨[J];系统工程理论方法应用;2001年02期

6 方保昒,徐汉忠;用单亲遗传算法解具有窗口式交货期的多机加工排序问题[J];系统工程理论方法应用;2001年04期

7 宋政芳,孙世杰,吴春燕;一个超前有奖迟后受罚的排序问题(英文)[J];运筹学学报;2002年04期

8 赵传立,唐恒永;具有相关调整时间的排序问题[J];沈阳师范学院学报(自然科学版);2002年01期

9 郑自途;关于"三台以上机床作业排序问题"的算法[J];天津理工学院学报;2002年04期

10 张玉忠,苗翠霞;复制法及其在分批排序问题中的应用[J];曲阜师范大学学报(自然科学版);2004年02期

中国重要会议论文全文数据库 前10条

1 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

2 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 谭万达;;二元对比排序中的最少逆序原理[A];中国系统工程学会模糊数学与模糊系统委员会第五届年会论文选集[C];1990年

8 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国重要报纸全文数据库 前1条

1 山东 赵玉勇;数组，你的规律机器[N];电脑报;2004年

中国博士学位论文全文数据库 前10条

1 仲维亚;供应链管理中的若干排序问题研究[D];浙江大学;2008年

2 尹晓;基因组重组排序问题的算法研究[D];山东大学;2010年

3 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年

4 张安;带服务等级的在线排序问题及相关问题研究[D];浙江大学;2009年

5 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年

6 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

7 李好好;若干排序问题研究[D];浙江大学;2014年

8 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

9 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

10 王成飞;几类新型在线分批排序问题[D];曲阜师范大学;2011年

中国硕士学位论文全文数据库 前10条

1 董柳毅;与误工有关的多目标排序问题[D];重庆师范大学;2009年

2 王迅娣;成组加工排序和供应链在线排序问题[D];曲阜师范大学;2010年

3 王洁明;有关代理竞争排序问题的研究[D];华东理工大学;2011年

4 刘丽丽;分批排序问题[D];曲阜师范大学;2000年

5 鄢楚楠;2，4-逆序变换的置换排序问题[D];浙江大学;2006年

6 张兵权;单位加工时间的公共时间窗单机分组排序问题[D];浙江大学;2006年

7 姜冠成;分批排序问题和资源约束排序问题[D];苏州大学;2005年

8 胡荣;一类分装式排序问题的计算方法和计算复杂性研究[D];武汉科技大学;2006年

9 马蕾;带传递时间的通信模型中的树约束排序问题[D];兰州大学;2007年

10 王小明;不允许等待的混合流水两车间排序问题[D];清华大学;2002年

，

本文编号：1068057