针对序列问题的一类快速插入算法

发布时间：2017-06-25 15:10

  本文关键词：针对序列问题的一类快速插入算法，由笔耕文化传播整理发布。

【摘要】：组合优化是数学优化领域最活跃的课题,而数学优化领域又包括运筹学,算法理论和计算复杂性理论等方面。而在组合优化这个大课题中序列问题又是其中研究最广泛的问题。序列问题就是根据一定的要求将已有的操作或是序列进行排序,进而获得一个优化的序列。在这篇论文中,我们将讨论2种序列问题:图形布局问题和调度问题。因为这两种问题之间有很强的相关性,我们甚至可以使用一个析取图模型,将调度问题模型化成图形布局问题。所以我们就把这两个问题放在一个论文,并一起讨论它们。图形布局问题在数值分析,计算生物学,调度问题等方面都有广泛的应用。而调度问题在供应链和生产规划方面发挥了重要的作用。对于图形布局的问题,我们将讨论对非定向的树线性排列的问题,这是一种最小线性排列的问题。这个问题的目标是根据一个非定向树找到一种线性布局进而使目标函数最优化。在这一部分,我们将设计和实现两个插入算法。对于调度问题,主要讨论生产和运输整合调度问题。这个问题是作业车间调度问题的一个扩展,在作业车间调度问题基础上加上运输以及运输工具负载能力这两个扩展条件。这个问题的目的是找到一个运输和生产的任务安排以尽量减少整体任务花费时间,也就是所有操作和运输完成时间的最大值。在这部分首先对此问题进行数学模型,然后根据这个数学模型,设计并实现一种任务时间计算标准以及一种能产生最优生产运输安排的算法。
【关键词】：组合优化 序列问题 图形布局问题 调度问题 数学规划
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224
【目录】：

• 摘要4-5
• ABSTRACT5-6
• Résumé6-10
• 第1章 绪论10-16
• 1.1 课题来源与背景10-11
• 1.2 课题目的11-12
• 1.3 国内外相关研究现状12-14
• 1.3.1 图形布局问题的相关研究现状12-13
• 1.3.2 调度问题的相关研究现状13-14
• 1.4 论文的主要内容14-16
• 第2章 系统需求分析16-22
• 2.1 系统目标16
• 2.2 MINLA问题的功能需求分析16-18
• 2.2.1 符号16-17
• 2.2.2 无向树的定义17
• 2.2.3 Min LA问题定义17
• 2.2.4 输入输出17
• 2.2.5 复杂度17-18
• 2.3 MINLA问题的非功能需求分析18
• 2.4 PTSP问题的功能需求分析18-20
• 2.4.1 PTSP问题描述18
• 2.4.2 符号18-19
• 2.4.3 PTSP问题的输入19
• 2.4.4 析取图G=(V,C,D)19-20
• 2.4.5 复杂度20
• 2.5 PTSP问题的非功能需求分析20-21
• 2.6 小结21-22
• 第3章 MINLA系统设计22-40
• 3.1 算法符号定义22
• 3.2 最小线性布局问题实例22
• 3.3 数据构建22-27
• 3.4 计算中心点函数27-28
• 3.5 核心算法 128-31
• 3.6 核心算法 231-39
• 3.7 函数VAL39-40
• 第4章 PTSP系统设计40-56
• 4.1 PTSP中的实际问题40-41
• 4.2 本章概述41
• 4.3 数据构建41-44
• 4.4 约束条件简化44
• 4.5 条件标准44-47
• 4.6 调度序列生成47-52
• 4.7 输出表示52-53
• 4.8 修复调度序列53-56
• 第5章 系统实现及测试56-67
• 5.1 系统实现环境56
• 5.2 程序流程图56-59
• 5.2.1 Min LA问题的程序流程图56-57
• 5.2.2 PTSP问题的程序流程图57-59
• 5.3 MINLA问题的主要界面59-60
• 5.4 PTSP问题的主要页面60-62
• 5.5 MINLA系统测试62-65
• 5.6 PTSP系统测试65-66
• 5.7 小结66-67
• 结论67-68
• 参考文献68-73
• 致谢73-74
• 个人简历74-77
• 附件77

【相似文献】

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

1 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

2 席裕庚,王长军;控制、规划和调度问题中的博弈论应用[J];中国计量学院学报;2005年01期

3 胡扬;桂卫华;;人工代谢算法在多对象调度中的应用[J];系统工程学报;2011年01期

4 刘鹏;周晓晔;衣娜;;带有减少线性恶化效应的双代理调度问题[J];系统工程学报;2011年03期

5 董平;机器调度问题及求解方法[J];物流技术与应用;1997年01期

6 张仁忠;一类串行生产线的最优调度问题的注记[J];黄淮学刊(自然科学版);1998年S3期

7 刘红,张强,杜瑜;全国大学生数学建模竞赛中公交车调度问题的求解[J];成都航空职业技术学院学报;2002年02期

8 黎鹤;孙广中;许胤龙;;未知网络中可分负载的分布式调度[J];中国科学技术大学学报;2009年08期

9 王冰;动态单机调度的一种滚动时域策略及全局性能分析[J];系统工程理论与实践;2004年09期

10 左燕;薛安克;王建中;;单机调度问题对偶集结迭代算法[J];控制理论与应用;2010年12期

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

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

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

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

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

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 李雪松;模糊环境下若干单机批加工调度问题的模型及其算法研究[D];哈尔滨工业大学;2015年

4 汤雅连;关联物流运输调度问题研究[D];广东工业大学;2015年

5 周理;高效可重构阵列计算：体系结构，设计方法与程序映射技术研究[D];国防科学技术大学;2014年

6 冯大光;一类批处理机调度的理论和方法研究[D];东北大学;2011年

7 孟盈;钢铁企业并行批生产决策与调度问题研究[D];东北大学;2011年

8 杨磊;内容网络中内容调度技术研究[D];重庆大学;2015年

9 李亚志;流水制造单元调度智能优化方法[D];东南大学;2015年

10 丁宁;若干调度问题的算法研究[D];大连理工大学;2016年

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

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 吉佳红;基于细菌觅食算法的改进及应用研究[D];江苏科技大学;2015年

9 周超;柔性作业车间批量问题研究[D];宁波大学;2014年

10 赵兴野;工序顺序柔性作业车间描述与调度研究[D];大连理工大学;2015年

  本文关键词：针对序列问题的一类快速插入算法，，由笔耕文化传播整理发布。

本文编号：482562