置换流水车间调度问题上的蚁群算法分析

《置换流水车间调度问题上的蚁群算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文插图索引2．1阿根廷蚂蚁及双桥实验示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．83．1蚁群算法的核心流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．143．2PFSP的图表示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．153．3PFSP的类ATSP图表示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．153．4计算makespan的格状图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一173．5一步选择选择两个任务的周游方案图⋯⋯⋯⋯⋯⋯⋯⋯⋯，⋯⋯⋯⋯

2、．．183．6改进周游方案与原方案比较图(应用于基本蚁群算法)⋯⋯⋯⋯⋯⋯193．7改进周游方案与原方案比较图(应用于Max．Min蚁群系统)⋯⋯⋯⋯⋯193．8改进周游方案与原方案比较图比较图(应用于ACS蚁群系统)⋯⋯⋯203．9协调度概念示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．224．1任务之间的相互关系示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一264．2关键路径与关键块示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．：⋯⋯⋯⋯⋯．．274．3按照数据依赖顺序并行计算示意图⋯⋯⋯⋯⋯

3、⋯⋯⋯⋯⋯⋯⋯⋯⋯．．294．4机群系统示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯354．5MPI编程及运行流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36VI图图图图图图图图图图图图图图图置换流水车问调度问题上的蚁群算法研究附表索引表2．1蚁群算法的应用说明表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯．12表3．1PFSP相关符号说明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．13表3．2Y_MMAS应用于Taillard标准问题实验结果⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯23表3．3改进算法与传统算法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯24表4．1代价函数的并行计算结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．34表4．2并行蚁群算法的实验结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37VlI硕士学位论文1．1问题背景和意义第1章绪论现实生活中，我们时常会面对如何配置资源的问题，从最宽泛的角度讲，调度理论即是研究该领域的理论。调度类型繁多，本文研究车间调度中的置换流水车间调度问题。早在1OO年前，生产调度就引起了工程师和管理决策者的注意，当时只是一

5、些简单的想法，并没有上升到理论的高度。上世纪50年代起，调度问题的研究受到应用数学、运筹学和工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划和动态规划等方法，研究并解决了一系列有代表意义的调度和优化问题。60年代Conway、Maxwell和Miller三人有关调度的研究工作成为调度理论的奠基石。此后30多年里，调度理论和应用的研究蓬勃发展，一些调度技术和模型在今天仍然被应用着。70年代，随着科学技术的发展，生产规模增大，对企业的管理和对生产过程的监控都提出了更高的要求。原

6、来简单的控制和仅凭经验的管理己经不能满足现代生产的要求。在这种情况下，1973年美国约瑟夫·哈林顿博士提出了计算机集成制造的概念一CIMS，它借助计算机软件、硬件，综合运用现代管理技术、制造技术、信息技术、自动化技术、系统工程技术，将企业生产过程中有关人、技术、经营管理三要素及其信息流与物质流有机地集成并优化运行，以实现产品的高质、低耗，从而使企业赢得市场竞争。生产调度是实施CIMS的关键，无论是理论研究，还是应用系统的开发都受到学术界和企业界的关注。置换流水车间调度问题，是车间调度领域的一个子问题，是

7、通过对制造过程进行作业计划，以实现流水车间环境下生产过程的优化调度。它广泛应用于实际生产，尤其适用于单件大批量生产背景的制造企业。除了工程背景外，置换流水车间调度问题还是一个经典的理论问题，拥有简洁的形式，广泛的关联性和高度的计算复杂度。该问题的简洁性体现在，任务集合上的一个排列就代表了一个调度序列。而关联性和复杂性表现在，该问题代表了一大类具有排列性质的问题，许多组合优化问题都可以归约到它。在计算理论中，它是NP．难的。1．2问题描述车间调度所涉及到的元素虽然只有任务和机器，但由这两个元素却可以衍生置

8、换流水车问调度问题I二的蚁群算法研究出非常复杂的问题来，如任务各不相同、机器异构、求解目标各异等情况，随着问题规模的增加，该问题的计算量呈阶乘级增长。一般来说，车间调度由元素、限制和目标构成。元素是指给定的一些任务、任务上的一些操作以及一些执行这些操作的机器组成。限制包括操作的执行时间的限制、一个机器只能处理一个操作的限制。目标是企图最优化的一个量，如任务序列的时间跨度、任务的执行时间总和等。根据限制的不同，车间调度有几个分类。开放车间调度