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

摘要

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

目录

译文摘要

第1章 绪论

1.1 课题来源与背景

1.2 课题目的

1.3 国内外相关研究现状

1.4 论文的主要内容

第2章 系统需求分析

2.1 系统目标

2.2 MinLA 问题的功能需求分析

2.3 MinLA问题的非功能需求分析

2.4 PTSP问题的功能需求分析

2.5 PTSP问题的非功能需求分析

2.6 小结

第3章 MinLA 系统设计

3.1 算法符号定义

3.2 最小线性布局问题实例

3.3 数据构建

3.4 计算中心点函数

3.5 核心算法1

3.6核心算法2

3.7 函数VAL

第4章 PTSP系统设计

4.1 PTSP中的实际问题

4.2 本章概述

4.3 数据构建

4.4 约束条件简化

4.5 条件标准

4.6 调度序列生成

4.7 输出表示

4.8 修复调度序列τ

第5章 系统实现及测试

5.1 系统实现环境

5.2 程序流程图

5.3 MinLA问题的主要界面

5.4 PTSP问题的主要页面

5.5 MinLA系统测试

5.6 PTSP系统测试

5.7 小结

结论

参考文献

声明

致谢

个人简历