（技术经济及管理专业论文）蚂蚁算法的杂交改进.pdf

中文摘要 生产调度问题，即对生产过程进行作业计划，是指产品在制造过程中，在满 足各种生产约束的前提下，实现人力、材料、机器等共享资源的有效配置及使用 顺序，以达到生产费用最低的目的。有效的调度方法和优化技术的应用，可大夫 提高生产效率和资源利用率，进而增强企业的竞争能力。 蚂蚁算法是意大利学者m d o r i g o 受蚂蚁等社会性昆虫的行为方式启发而提 出的一种全新的并行式算法。蚂蚁算法模仿了自然界中蚂蚁间相互协作以优化群 体行为的方式，并具有应用简单、便于实现、鲁棒性强等特点，已成功应用于组 合优化、工程设计等不同领域。 然而蚂蚁算法在求解大规模组合优化问题中显示了其容易陷入局部极小值 的缺陷，为此本文选择了将蚂蚁算法和模拟遐火算法进行杂交以改进算法性能。 首先，文章介绍了生产调度问题，包括调度问题简介、特性和加工性能指标的描 述。其次介绍了蚂蚁算法的生物学机理、算法流程，并详细介绍了m a xm i na n t s y s t e m 。然后重点阐述蚂蚁算法的具体操作以及参数选择，将蚂蚁算法与模拟退 火进行杂交的操作、算法流程。最后针对2 1 个r e c 类f l o w s h o p 问题进行实证 分析，分析了该类问题的拓扑空间特性以及杂交算法性能的改进情况。 本文提出的杂交蚂蚁算法策略结合了蚂蚁算法和模拟退火算法各自的特点， 使两种算法的搜索能力得到相互补充，弥补了各自缺点，是一种优化能力、效率 和可靠性较高的优化方法。对解决现实流水线生产中的产品排序具有一定的实际 意义。 关键词：蚂蚁算法组合优化置换f l o w s h o p 问题杂交算法 a b s t r a c t s c h e d u l i n gp r o b l e m ，w h i c hm e a n sm a k i n go p e r a t i o np l a n sd u r i n gt h em a n u f a c t u r i n g p r o c e s s ，s e e k st om a k ef u l lu s eo ft h eh u m a nr e c o u r s e s ，m a t e r i a la n dm a c h i n e s t h e o b j e c t i v ei st om i n i m i z et h ep r o d u c t i o nc o s t s e f f e c t i v es c h e d u l i n gc a ni m p r o v ct h e m a n u f a c t u r i n ge f f i c i e n c ya n dm a k eb e r e ru s eo ft h ee q u i p m e n t s ，t h u sh e l pt h e c o r p o r a t i o nt ob em o r ec o m p e t i t i v e a n ta l g o r i t h mi san o v e lp a r a l l e la l g o r i t h mb r o u g h tf o r t hb ya ni t a l i a ns c i e n t i s t m d o r i g o ，w h o w a si n s p i r e d b y a n t sa n do t h e rs o c i a li n s e c t s b e h a v i o r s a n t a l g o r i t h mm i m i c st h ec o o p e r a t i o no ft h en a t u r a la n t s i tc a nb ee a s i l ya p p l i e da n do f h i g l i l yr o b u s t n e s s a n ta l g o r i t h mh a sb e e nw i d e l ya p p l i e di nv a r i o u sa r e a ss u c ha s o p t i m i z a t i o na n di n d u s t r i a ld e s i g n h o w e v e , a n ta l g o r i t h mh a so n ed e f e c tt h a tw h e na p p l i e di nl a r g e s c a l eo p t i m i z a t i o n p r o b l e m si ti sa p tt ob es u c k e di nl o c a lo p t i m a s ot h i st h e s i sc h o o s e sa n n e a l i n g a l g o r i t h ma n da n ta l g o r i t h mt oh y d r i d ei no r d e rt oi m p r o v ei t sp e r f o r m a n c e f i r s tt h et h e s i si n t r o d u c e st h es c h e d u l i n gp r o b l e m s ，i n c l u d i n gt h eb r i e fi n t r o d u c t i o n ， c h a r a c t e r sa n ds o m eo p e r a t i o ni n d e x e s t h e nt h et h e s i si n t r o d u c e st h eb i o l o g i c a l m e c h a n i s mo ft h ea n ta l g o r i t h m ，t h ep r o c e d u r eo ft h ea l g o r i t h m ，a n de x p a t i a t e st h e m a xm i na n ts y s t e mi nd e t a i l n e x tt h et h e s i se m p h a s i z e so nt h ed e t a i lo ft h e o p e r a t i o na n dh o wt oc h o o s ep a r a m e t e r so ft h eh y d r i d ea n ta l g o r i t h m a tl a s tt h e a l g o r i t h m sa f et e s t e da g a i n s tb y2 1r e cf l o w s h o pp r o b l e m s a l s o 。t h et o p o l o g y c h a r a c t e r i s t i c sa n dt h ep e r f o r m a n c ea r ea n a l y z e da sw e l l t h eh y b r i da n ta l g o r i t h mc o m b i n e st h et r a i t so ft h ea n ta l g o r i t h ma n dt h ea n n e a l i n g a l g o r i t h m ，t h u se n h a n c i n gi t ss e a r c h i n gc a p a b i l i t y t h eh y b r i da n ta l g o r i t h mi s s u p e r i o ri no p t i m i z a t i o na b i l i t y , e f f i c i e n c ya n dl i a b i l i t y i ta l s oc a l lb ea p p l i e di nt h e i n d u s t r y k e yw o r d s ：a n ta l g o r i t h m ，c o m b i n a t o r i a lo p t i m i z a t i o n ，p e r m u t a t i o n f l o w s h o p ，h y d r i da l g o r i t h m s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究：l 作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得墨壅盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文巾 作了明确的说明并表示了谢意。 学位做作者签名：派新华签字日期斓f 年f 眇烟 学位论文版权使用授权书 本学位论文作者完全了解墨凄太茔有关保留、使用学位论文的规定。 特授权盘韭盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索。并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或规构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：骂茛薪华 签字日期：埔年f 月枷日 导师签名 签字日期：弘衫_ 年月硝日 第一章绪论 1 1 本文背景 第一章绪论 敏捷制造作为2 1 世纪企业的先进制造模式，综合了j i t 、并行一程、精良制 造等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品， 即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、 如何重构车间和单元、如何安排生产计划、如何进行调度都是人们面临的问题。 其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，：备 效实用的调度方法和优化技术的研究与应用已成为先进制造技术实践的基础。调 度问题主要集中在车间的计划与调度方面许多学者作了大量研究，出了不少的 研究成果。制造系统的生产调度是针对一项可分解的工作( 如产品制造) ，探讨 在在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下 达生产指令、安捧其组成部分( 操作) 、使用哪些资源、其加工时间及加： 的先 后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问题常 被称为排序问题或资源分配问题。 实际的调度问题有以下特点： ( 1 ) 复杂性：由于装卸作业、装卸设备、库场、搬运系统之间相互影响、相 互作用，每个作业又要考虑它的到达时间、装卸时间、准各时间、操作顺序、交 货期等，因而相当复杂。由于调度问题是在等式或不等式约束下求性能指标的优 化，在计算曩上往往是n p 完全问题，即随着问题规模的增大，对于求解最优化 的计算量呈指数增长，使得一些常规的最优化方法往往无能为力，对于这一点 g a r e y 等【l j 给出了明确的证明。即便对单机调度问题，如果考虑n 个作业而每个 作业只考虑加工时间及与序列有关的准备时间时，就等价于n 个城市的t s p 问 题。对于一般的装卸系统，问题就变得更为复杂。 ( 2 ) 动态随机性：在实际的生产调度系统中存在很多随机的和不确定的因 素，比如作业到达时间的不确定性、作业豹加工时间也有一定的随机性，丽且生 产系统中常出现一些实发偶然事件，如设备的损坏修复、作业交货期的改变等。 ( 3 ) 多目标：实际的计划调度往往是多目标的，并且这些目标间可能发生冲 突。o r a v e s 曾将调度目标分为基于调度费用和调度性能的两大类指标；a l i a s 等 人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基于 第一章绪论 生产成本的目标。这种多目标1 ，# 导致调度的复杂性和计算量急剧增0 | l 1 2 研究现状 由于大多调度问题属于一1 类n p 困难组合问题，因此寻找具有多项式复杂性 的最优算法几乎是不可能的，但仍激发着学者们进行不断的探索。随着各种新的 相关学科与优化技术的建立与发展，在调度领域出现了许多优化方法，比如神经 网络、模拟退火法、遗传算法、禁忌搜索法等，使得调度问题的研究方法向多无 化方向发展。下面分别对这些方法进行总结： 1 运筹学方法：运筹学方法是将生产调度问题简化为数学规划模型，采用基 于枚举思想的分枝定界法或动态嫂划算法进行解决调度最优化或近优化问题，属 于精确方法。文献1 2 - - 6 h 等提出了不问的分技定界法，其不同点主要在于分析规 则、定界机制和上界的产生这三方面存在差异。这类方法虽然从理论上能求得最 优解，但由于其计算复杂性的原因、因而不能获得真正的实用。l e n s t r a 在文献 7 中指出，对一个标准的1 0 i o b - - - 1 0 m a c h i n e 问题求最优解，需要在p r i m e2 6 5 5 计算机上运行l 小时，并产生2 2 0 0 0 个结点。对于复杂的问题，这种纯数学方 法有模型抽取困难、运算量大、算法难以实现的弱点，对于生产环境中的动态调 度实现复杂，解决不了动态及快速响应市场的问题。 2 基于规则的方法：对生产加工任务进行调度的最传统的方法是使用调度规 则( d i s p a t c h i n gr u l e s ) ，已经有许多调度规则被应用，因其调度规则简单、易于实 现、计算复杂度低等原因，能够用于动态实时调度系统中，许多年来一直受到学 者们的广泛研究，并不断涌现出新的调度规则。许多学者在这方面已进彳亍了探索 及大量工作，如研究与制定较优的单元零件加工调度算法，在减少等待时间、提 高生产率等诸多约束条件下达到了一种较为科学有效的调度效果。 p a n w a l k a r 和l s k a d d e r 总结了1 1 3 条规则1 3 j 并将它们按形式分为三类：简 单规则、复合规则、启发式规则；m m o n t a z e l i 等例举了常见的2 0 条规则，并针 对一个实际的f m s ，分析了这些规则对系统性能( 如作业的平均等待时间、设 备的平均利用率、作业总加工时间等) 的影响；文献【9 】将多种规则组合起来实 现调度；文献f l o 】讨论了决策规贝l j 解决f m s 车间调度问题的方法与规则库豹具 体实现，分析了各种规则与性能指标的关系，对如何合理地选用规则提出了建议： 为了提高规则调度的质量，文献 1 1 通过分析拖后时间与两个作业调度决策问的 关系，提出了一种比较复杂的规则，并在以拖后时间最小的目标下，与l s t 、 l p t 、l d d 、l w r 、l s w r 、璐o r 等规则作了实验比较。随着计算机运算速度 的飞速提高，人们希望寻找新的近似调度方法，它以合理的额外计算时间为代价， 第一睾绪论 换得比单纯启发式规则所得到的调度更好的调度。在这方面比较有代表性的订移 动瓶颈方法( b o t t l en e c kp r o c e d u r e ) ， j 来解决以最小化m a k e s p a n 为 1 标的 j o b s h o p 调度问题，它通过不断地对移动的瓶颈设备进行单机调度，来获瞅更好 的次优解。 总的说来，启发式规则直观、简单、易于实现。但是近f 年的研究表明并不 存在一个全局最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及生 产条件。它是局部优化方法，难以得到全局优化结果，并且不能对得到的结果进 行次优性的定量评估。顾客需求的个性化及要求企业响应市场的敏捷性，往往在 生产加工过程中加入了更多的不确定性及复杂性约束，寻找调度最优算法本身是 一个n p 完全问题，这些使得基于规则的调度思想已不能适合敏捷化制造的要求， 3 系统仿真的方法：基于仿真的方法不单纯追求系统的数学模型，侧重对系 统中运行的逻辑关系的描述，能够对生产调度方案进行比较评价，分析系统的动 态性能，并选择系统的动态结构参数。由于制造系统的复杂性，很难用一个精确 的解析模型来进行描述和分析。而通过运行仿真模型来收集数据则能对实际系 统进行性能、状态等方面的分析，从而，能对系统采用合适的控制调度方法。仿 真方法最早被用来作为测试调度启发式规则及分派规则的工具。后来，人们发现， 通过将简单的优先权规则进行组合，或用一个简单的优先权规则将一些启发式规 则进行组合，这样的调度优于单独的优先权规则。于是仿真方法逐渐发展为一 种人机交互的柔性仿真工具，并用来进行车间调度。这样，就能通过仿真而动态 地震现j o b s h o p 车闻的状态，分析在不同的调度方法下的系统性能，并运用知识 和经验去选择合适的调度方法，从而改善调度性能。 k i r a n 等回顾和总结了在动态环境下基于纯仿真模裂的j o b s h o p 调度问题的 研究状况；b a k c r 等人研究表明：机器数目对生产的相对效率影响不大；n a n o t 说明了优先规则的相对效率并不因机器的构成而改变；文献【1 2 】中提出了基于纯 仿真模型的调度方法，即在一个较短的时间段内用仿真来评价一个分派规则集， 选取最小代价的规则进行调度，以适应系统状态的变化；文献【1 3 】运用纯仿真模 型，同时解决f m s 中作业调度和搬运小车及刀具的资源分配问题。 基于纯仿真法虽然可以包含解析模型无法描述的因素，并且可以提供给使用 者一个调度性能测试的机会，但其不可避免地存在以下闯题：1 ) 鉴于其实验性， 因此，很难对生产调度的理论作出贡献。2 ) 应用仿真进行生产调度的费用很高， 不仅在于产生调度的计算时间上，而且在于设计、建立、运行仿真模型上的高费 用。3 ) 仿真的准确性受编程人员的判断和技巧的限制，甚至很高精度的仿真模型 也无法保证通过实验总能找到最优或次优的调度。 4 基于d e d s 的解析模型方法：由于制造系统是一类典型的离散事件系统， 第一章绪论 因此，可以用研究离散事件系统的解析模型和方法去探讨车间调度问题，渚蚴排 队论、极大极小代数模型、p e t r i 网等。调度中的排队论方法是种随机优化0 + 法，它将每个设备看成个服务台，将每个作业作为个客户。作业的各种复杂 的可变特性及复杂的路径，可通过将其加 ：时问及到达时间假设为个随机分前， 来进行描述。 总的说来，排队网络模型由于从随机统计的角度来描述f m s ，难以表述系 统中存在的某些特性( 如有限的缓存空间等) ，同时，产生的输出是基于系统稳 态操作的平均量，因此，很难得到比较具体的细节。p e t r i 网作为一种图形建模 工具可以形象地表示和分析f m s 中加工过程的并发和分布特征以及多项作业共 享资源时的冲突现象，具有很强的建模能力，对于描述系统的不确定性和随机性 也具有一定的优越性。在制造自动化领域，利用p e t r i 网及其扩展形式的模型进 行死锁分析、调度决策和性能评价等已有大量理论研究文献。赋时p e t r i 网是在 以往p e t r i 网的基础上又引入了时间元素，使其能够用于f m s 中加工的组合优化、 生产进程的实时调度和性能估计等。t i e nh s i a n gs u n 等人用赋时p e t r i 网为f m s 建摸，它包括两个主要的子模型：静态的传送模型和变化的加工流模型。通过嵌 入一个基于a 搜索算法，最后得到一个满意的作业加工调度。在此基础上还进 行了一个实例研究。部分学者用赋时p e t r i 网为f m s 建模，通过优化变迁的发生 序列来产生的搜索可标识集，从而得到较优的调度结果。 目前，p e t r i 网模型用于f m s 的调度还存在以下的问题：1 ) 节点语义的单义 性，使得所携带的系统信息量不够丰富。2 ) 重用性差。拓i 网多是基于f m s 中 作业的加工流程建模，当作业需求或工艺稍有变动时，必须修改模型结构，这难 于适应f m s 中存在的不确定因素。3 ) 不能对高级的调度规则加以建模，通常只 能用禁止弧机制体现一些低级控制。 5 基于捧序的方法：该方法是先有可行性加工顺序，然后才确定每个操作的 开工时间，并对这个顾序进行优化，它虽然属于近似算法，但有可能达到最优的 调度方案。它主要包括邻近搜索法，它在生产调度领域得到了相当广泛的应用， 在探索解空间时，仅对选定的成本函数值的变化做出响应，因而通用性强。这类 方法包括局部探索c a ls e a r c h ) 、模拟退火法( s i m u l a t e da n n e a l i n g ) 、遗传算法 ( g e n e t i ca l g o r i t h m s ) 。邻近搜索虽然可能得到最优的调度方案，但也存在各自的 不足，很多学者采取混合算法来弥补单一方法的不足。 ( 1 ) 启发式圈搜索法 对于表述为整数规划的调度问题，最初采用分枝定界法来解决，而后其他的 启发式图搜索法也被应用于解决调度闯题。在文献【1 2 】中b a l a s 将调度排序问题 用一个d i s j u n c t i v e 图来表示，首先构造一个可行解，采用基于隐枚举的搜索方法 第一章绪论 不断提高解的次优性：在文献( 1 4 1 中采用束搜索法( b e a ms e a r c h ) 来识别瓶颈机 器，进行调度：为了解决搜索空间太大的m 题，在文献f 1 5 】中通过列分枝定界法 和柬搜索法进行系统的分析，提出了一种过滤束搜索法( f i l t e rb e a ms e a r c h ) ，剧 来解决单台机器提前延期问题和加权延期的f l o w s h o p 问题：文献f 9 】、f 1 5 】中研 究了基于a 的优先树搜索法的优化作业排序问题：文献【1 6 】中针对基j i 树搜索 的优先a + 算法需要大量内存的问题，提出了一个图搜索法，并对两种方法作丁 比较；文献【2 4 】中为解决j o b s h o p 调度问题对a 算法作了两点改进：1 ) 在搜索过 程中只展开有限节点；2 ) 采用加权的评价函数。对于图搜索算法，如何提高搜索 效率并减少内存使用以解决规模较大的问题，还需要迸一步探索。 ( 2 ) 模拟退火法 模拟退火算法( s a ) 将组合优化问题与统计力学中的热平衡问题类比，另辟 了求解组合优化问题的新途径。它通过模拟退火过程，可找到全局( 或近似) 最优 解。模拟退火法的几个重要部分为：生成函数( g e n e r a t i o nf u n c t i o n ) 、接受函数 ( a c c e p t a n c ef u n c t i o n ) 、降温过程和结束准则。模拟退火法的改进算法有加温退 火法、有记忆的模拟退火法等。文献【9 】中为f l o w s h o p 问题求解构造了一类模拟 退火法，并通过六种不同的随机抽样方式分析了算法渐近收敛于全局最优解，分 别解决了具有最小m a k e s p a l l 指标且具有无限中间存储( u i s ) 、有限中间存储( f i s ) 和无中间存储( n l s ) 的f l o w s h o p 排序问题；文献1 1 6 1 提出了一种改进的模拟退火 法，用来解决具有最小m a k e , s p a n 指标的f l o w s h o p 排序问题，并与禁忌搜索法 等进行了比较；文献【1 0 】用模拟退火法进行机器分组；文献【1 3 】用模拟退火法求 解有资源约柬的调度问题。另外，模拟退火法也可与其他方法相结合进行求解， 如文献【1 7 】中先用贪婪算法( g r e e d ys e a r c h ) 搜索。将得到的作业序列作为初始解， 再用模拟退火法求解单机调度问题，其结果表明这种方法比单纯用模拟退火法和 贪婪算法要好；文献1 1 8 中提出了将模拟退火法与启发式算法相结合的方法，求 解具有交货期约束的j o b s h o p 调度问题。由于模拟退火法能以一定的概率接受差 的能量值，因而有可能跳出局部极小，但它的收敛速度较幔，很难用于实时动态 调度环境。 ( 3 ) 禁忌搜索法 对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的 方法，g l o v e r 曾在文献 1 5 】【1 8 】中叙述了它的基本原理。禁忌搜索是一种迭代方 法，它开始于一个初始可行解s ，然后移动到领域n r s ) 中最好的解s ，即s 对于 目标函数f ( s ) 在领域n ( s ) 中是最优的。然后，从新的开始点重复此法。为了避 免死循环，禁忌搜索把最近进行的t 个移动( t 可固定也可变化) 放在一个称作 t a b u l i s t 的表中，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后 第章绪沦 它们又被释放出柬。这样的t a b ul i s t 是，个循环表，它被循环地修改，蕻长度t 称作t a b us i z e 。最后，还须定义个停j 上准则来终止整个算法山于t a b ul i s t 的限制，使其在搜索中有可能跳出局部极小。文献【1 9 l 2 0 1 分别提出r 解决 f l o w s h o p 调度问题的禁忌搜索算法。在文献 2 1 1 中为了更有效地搜索解空间，引 入了插入和移动相结合的机制提高了搜索效率。文献 1 0 1 中采用了并行禁忌搜索 法以加快搜索速度。文献【1 3 】中针对求解公芡交货期下带有等待时问惩罚的提前 拖后单机调度问题，提出了一种禁忌搜索法。 ( 4 ) 神经网络优化 h o 呻e l d 神经网络模型的提出为求解各种有约束优化问题开辟了条新途 径，用h o p f i e l d 网络解决t s p 问题就是其在组合优化问题中的最成功的应用之 。它的主要思路是：通过一个l y a p l m o v 能量函数构造网络的极值，当网络迭 代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。文献【1 8 】 介绍了一种随机h o p f i e l d 网络来懈决j o b s h o p 调度问题的方法：文献 1 5 1 中为了 解决大规模问题，又提出一种改进的h o p f i e l d 网络的整数线性规划神经网络方法 来解决j o b s h o p 调度阊题：文献1 2 2 1 中也提出了一种用于解决j o b s h o p 调度问题 的神经网络方法。 ( 5 ) 遗传算法 美国m i c h i g a n 大学的j h h o l l a n d 于本世纪末提出了一种新的并行优化搜索 方法：遗传算法( g e n e t i ca l g o r i t h m ) ，它是一种基于进化论优胜劣汰、自然选择、 适者生存和物种遗传恩想的随机优化搜索算法，通过群体的进化来进行全局性优 化搜索。它以其很强的并行性和很高的计算效率正日益受到人们的关注。它对组 合优化问题求解的主要过程是：给定一组初始解作为一个群体，通过选择、交换 和变异等遗传操作符来搜索问题的最优解。文献【2 1 1 中提出了一种基于遗传算法 的启发式方法，用于解决以最小化m a k e s p a n 为指标的f l o w s h o p 调度问题；文 献 2 3 1 用遗传算法解决j o b s h o p 调度闯题；有的学者将遗传算法与图搜索法相结 合，利用遗传算法进行知识的推理、启发，再用过滤束搜索法进行优化搜索，以 得到高质量的f m s 静态调度；文献f 5 】提出了一种并行遗传算法，试图解决常规 遗传算法在解决f m s 调度问题时产生的计算速度较慢及过早收敛等问题。 总的来说，遗传算法的最大优点是通过群体问的相互作用，保持已经搜索到 的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存 在着计算速度较慢的问题。 6 基于智能的调度方法 近年来受实际需要的推动，基于知识的智能调度系统和方法的研究取得了很 大的进展。人工智能在6 0 年代就将计划问题作为其应用领域之一，但直到8 0 年 第一章绪论 代，以c a r n e g i e m e l l o n 大学的m f o x 为代表的学者们丌展基于约束传播的 i s i s ( i n t e l l i g e n ts c h e d u l i n ga n di n f o r m a t i o ns y s t e m ) 的研究为标志人f 智能爿真 正：开始应用于调度问题。基于知识的调度方法是用专家系统自动产生调度或辅助 人去调度。它是将传统的调度方法与基于知识的调度评价相结合的方法。在八f 年代后期，几位学者先后开展了基于调度系统处于不同的状态，采用不同的调度 规则策略的动态调度方法的研究。它们研究的共同特点是：在支持某些活动发生 的资源条件具备时( 称为决策点) ，根据系统当时所处的属性状态，决定采取伺种 规则，确定或选择活动发生的顺序和时间，即状态指导的智能调度方法。 d o u b l g e r i 以一个柔性p c b 安装系统为实例，提出基于知识的调度方法 k b s 。它采用分级方法并利用仿真技术，根据全局知识划分作业，再根据局部知 识将作业分配到设备，通过满足一系列约束以及用户提出的总体和局部目标来产 生实际调度。文献【2 _ 4 】中探讨了一种基于知识摊理的专家系统模型、以实现作业 排序问题的求解，并给出了采用三种不同知识表示方式和分段推理的排序知识处 理方法。文献 1 5 1 用黑板模型来组织和维护动态数据库、在规划层用数学规划求 解、在调度控制层用基于知识的调度方法。文献f 2 5 】介绍了动态j o b s h o p 调度的 工具软件o c s ，提供了j o b s h o p 调度管理中的集成决策支持系统，它既能用专 家知识自动产生和评价调度，也能提供图形界面使用户能进行手工调度。另外还 有基于e r a i 网的启发式决策支持系统、基于p e 啊网的决策支持系统、用专家 系统实现的调度模型s o j 4 3 7 d 、以及利用启发式知识进行资源优化分配。 总的来说，主要包括智能调度专家系统、基于智能搜索的方法及基于多代理 技术( m u l t i - a g e n ts y s t e m ，简称m a s ) 的合作求解的方法等。其中，智能调度专 家系统是人工智能应用的体现，由于专家系统中知识获取和推理速度这两个瓶 颈，使得神经网络逐渐被采用，但还存在训练速度慢、探索能力弱等缺点。基于 多代理技术的合作求解方法是较新的智能调度方法，它提供了一种动态灵活、快 速响应市场的生产调度机制，它以分布式人工智能( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ，简称嗍忡的多代理机制作为新的生产组织与运行模式，通过代理 f a g e n t ) 之间的合作以及m a s 系统协调来完成生产任务的调度，并达到预先规定 的生产目标及生产状态。在这种研究方法中，在a g e n t 内部也可采用基于规则及 智能推理相结合的混合方法，来构造基于m a s 的生产调度系统。 调度领域中的大部分问题都是n p 问题，虽然对它的研究已有几寸。年的历史， 但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着很大 差距。尤其随着j 1 t ( j u s t i n t i m e ) 思想的广泛采用，e t ( e a r l i n e s s t a r d i n e s s ) 调度 问题，即使得工件尽量按交货期完成，变得越来越突出。实际应用中的调度方法 能够响应系统的动态变化，但不能保证得到好的调度：一黪理论上的最优化方法 第一章绪论 能提供最优调度，但出于其计算的复杂性，并且忽略了很多实际吲豢，离实m 、适 用还有较大距离。基于最优化的方法，诸如动态规划算法与分枝定奔锋法等等， 由于其大多数是建立在对可能调度的部分枚举匕，因此只能解决小赳模的调度问 题，距离实用还有较大距离。 1 3 本文结构和创新 本文共分六章。 第二章首先介绍生产调度问题，详细介绍了本文所要针对解决的f l o w s h o p 调度问题的数学模型、加工特性等。 第三章介绍蚂蚁算法的生物学机理，并以t s p 问题为例阐述了蚂蚁算法的 算法过程；此外介绍了蚂蚁算法中性能相对最好的m a xm i n 蚂蚁算法，该算法 所做出的三项改进。 第四章详细阐述了如何将m a xm i n a n ts y s t e m 应用于解决f l o w s h o p 问题， 包括算法基本操作、参数设置等，针对标准蚂蚁算法在解决大规模、复杂组合优 化问题中可能出现优化性能不尽如人意的情况，本文提出了一种新的蚂蚁算法一 将模拟退火算法与蚂蚁算法相结合的退火蚂蚁算法。并随后阐述了退火蚂蚁算法 的算法流程、参数设置等问题。 第五章中将标准蚂蚁算法、模拟退火算法以及退火蚂蚁算法分别用来求解 f l o w s h o p 问蘧，比较算法之间的性能差异，尤其是退火蚂蚁算法与标准蚂蚁算 法性能之间的差异。通过对f i o w s h o p 问题的空间分析，得出结论：新的算法局 部搜索能力的提高是导致算法能力大幅度提升的主要原因。 第六章是结论和展望。 本文创新点在于 ( 1 ) 将蚂蚁算法和模拟退火进行杂交，得到退火蚂蚁算法这一商质量、高甚棒 性的改进算法； ( 2 ) 在将蚂蚁算法应用到解决f l o w s h o p 问题的模型建立过程中，提出动态确 定信息素轨迹方法，解决了建模过程中难以将f l o w s h o p 问题抽象为一个完全图 的问题。 第二章生产调度同蘑 2 1 生产调度问题描述 第二章生产调度问题 2 1 1 生产调度问题简介 生产调度问题，即对生产过程进行作业计划，是指产品在制造过程中，在满 足各种生产约束( 如作业优先级、设备能力、交付日期等) 的前提下，实现人力、 材料、机器等共享资源的有效配置及使用顺序，以达到生产费用最低的目的1 “j 。 调度问题的解决是一个资源限制的寻优过程口”。 对于m 台机器( 皿m h i n e ) ， m ”，m 。 对n 个工件0 0 b ) ， 的加工过程， 所谓调度就是分配各工件在各机器上的加工时间。第一次世界大战中g # 图的 应用标志着形式化的调度模型的出现【冽。 生产调度作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹 技术、优化技术、自动化与计算机技术发展的核心。在自动化及计算机领域中， 调度问题都得到了深入的研究，在计算机集成制造系统化m s ) 及柔性制造系统 f f m s l 中，如何安排各工序的处理次序及占用资源，使之满足一定优化目标( 如 完成时间最短等) ，就是调度所要研究的问题1 2 q 。 有效的调度方法和优化技术的研究与应用，可大大提高生产效率和资源利用 率，进而增强企业的竞争能力。车间调度闯蘧一直是人们广泛注意的问题 3 0 p 1 i 。 生产调度的研究主要可分为建模和调度算法设计两个方面，它是一个交叉性 研究领域，涉及运筹学、数学、计算机工程、控制工程、工业工程等多个学科。 其中，建摸主要研究调度模型、调度规则、目标函数等内容；算法主要研究算法 设计、算法复杂性、算法收敛性和优化质量等内容。本论文主要研究生产调度问 题的算法。 2 1 2 工件加工数据和特性韵描述 调度问题中，通常一个工件 包含n z 个操作和p c r 鲥o n ) 。：”q 。 ，每个操 作d j ，的加工时间为p p 若强- 1 ，则工件j 。仅包含一个操作瓯，筒记其加工时 间为凤。称工件的第一个操作可执行的时刻为释放时间或准备时问( r e l e a s e d a t e ) ，记为r j ，记加工操作q 的机器集为一 m ，m 。 ，岛可以在心中任 何一台机器e 加工。通常，盹仅对应一台机器或者对应所有机器。前者称为专 何一台机器上加工。通常心仅对应一台机器或者对应所有机器。前者称为专 第二章生产调度问厦 2 1 生产调度问题描述 第二章生产调度问题 2 1 1 生产调度问题简介 生产调度闯题，即对生产过程进行作业计划，是指产品在翻造过程中，在满 足各种生产约束( 如作业优先级、设备能力、交付日期等) 的前提下，实现人力、 材料、机器等共享资源的有效配置及使用颓序，以达到生产费用最低的目的【2 酊。 调度问题的解决是一个资源限制的寻优过程口月。 对于r a 台机器( m a 血i n 吐和，m 对n 个工件a o b ) ，l 的加工过程， 所谓调度就是分配各工彳牛在备机器上的加工时间。第一次世晃大战中g 如t t 图的 应用标志着形式化的调度模型的出现l 捌。 生产调度作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹 技术、优化技术、自动化与计算机技术发展的核心。在自动化及计算机领域中， 调度问题都得到了深入的研究，在计算机集成制造系统( c l m s ) 及柔性制造系统 ( f m s ) 中，如何安捧各工序的处理次序及占用资源，使之满足定优化目标( 如 完成时间最短等) ，就是调度所要研究的问题】。 有效的调度方法和优化技术的研究与应用，可大大提高生产效率和资源利用 率，进而增强企业的竞争能力。车间调度闯惩一直是人们广泛注意的问题【3 0 】f 3 1 l 。 生产调度的研究主要可分为建模和调度算法设计两个方面，它是一个交叉性 研究领域，涉及运筹学、数学、计算机工程、控制工程、工业工程等多个学科。 其中，建模主要研究调度模型、调度规则、目标醋数等内容；算法主要研究算法 设计、算法复杂性、算法收敛性和优化质量等内容。本论文主要研究生产调度问 题的算法。 2 1 2 工件加工数据和特性的描述 调度问题中，通常一个工件包含一个操作( o j 碍鲥o n ) d l 一q 。) ，每个操 作q 的加工时间为岛。若吩- 1 ，则工件 ，。仅包含一个操作q 。，简记其加工时 间为n 。称工件的第一个操作可执行的时刻为释放时间或准备时间( r e l e a s e d a t e ) ，记为，记加工搡作q 的机器集为心 m ，m 。) ，q 可以在心中任 何一台机器上加工通常，心仅对应一台机器或者对应所有机器。前者称为专 幕一章生产调度问题 用机( d e d i c a t e dm a c h i n e ) ，后者称为并行 ) l ( p a r a l l e dm a c h i n e ) 。许多实际牛产系统 中，各机器可装备相同或不同的工具操作可在任何一台装备合遁j f 具的机器 ： 加工，这就是生产系统所谓的柔性，该调度通常称为多目的机器( m u l t i p u r p o s e m a c h i n e sm p m ) 。若q ，的加， 过程同时占有- t i ，中所有机器，则该调度问题称为 多处理机任务调度( m u l t i p r o c e s s o rt a s ks c h e d u l i n g ) 。对于每一工件j ，记f 时刻完 成j 的加工费用函数为f ( t ) ，记计划完成时间或交货期( d u ed a t e ) 为d ，j 之相 关的权重( w e i g h t ) 为。 若同一机器上既没有任意两个时间区间重叠，也没有分配给同一个 。件的任 意两个时问区间重叠，并且满足调度问题的一些特殊工艺约束，则称一个调度为 可行( f e a s i b l e ) 调度。进而，称使得调度准则或指标最优的可行调度为最优( o p t i m a l ) 调度。 通常，工件加工特性可用六元组声一 韪，疋，晟，卢，风，以 来表示，其中 1 且用来表示加工方式，包括抢占式( p r e e m p t i o n ) 或非抢占式 ( n o n p r e e m p t i o n ) 。其中，抢占式加工中操作在加工过程中可以被打新，再在原机 器上或其它机器上重新开始；非抢占式加工则一旦操作开始，直到加： 完毕，不 能再被其它加工打断。通常，记抢占式加工为反一p m t n ，而非抢占式加工则不 在3 中出现卢1 。 2 岛用来表示工件闯的加工优先关系( p r e c e d e n c er e l a t i o n ) 。该优先关系可以 用非循环有向图g ( v ，a ) 来表示，其中v 一扛，n ，表示工件，( i ，七) 爿，当 且仅当，必须在 开始加工之前完成。若g 为任意非循环有向图，则记 卢2 - p r e c 。若g 对应树( t r e e ) ，则记卢2 - t r e e 。若g 对应链，则记卢2t c h a i n ，若 g 对应的图具有系列一并行( s e r i e s p a r a l l e d ) 特性，则记卢2 - s p g r a p h 。若调度 问题不考虑工件加工的优先权，则卢中不出现卢，。 3 1 3 ，用来表示工件的准备加工时间。若- 1 0 ，则记岛一；若所有- 0 ， 贝0 卢中不出现卢，。 4 芦。表示加工时间或操作数量的限制。若以记做p i i ，( 或n ，一1 ) ，则每 个工件( 或操作) 有一次操作需求( 如加工时间为1 ) 。有时，成也可为一些具 有明显意义的别的值，如肛 1 ，2 ，d ，- d 。 5 段用来表示交货期信息。反一d ，表示工件有交货期要求，否则卢中不出 现玩。 6 凤用来表示批量信息，即工件是否成批联合进行加工。批量调度中，闷批 的各工件的完成时间等于该批量的完成时间，假定各批量的加工设置时问相同且 与加工顺序无关。i b 。一p b a t c h 或反一s b a t c h 分别表示批量长度等于该批量中 所有工件的加工时间的最大值或加工时间之和。若不考虑批量调度，则1 3 中不出 第二章生产调度问题 现成。 2 1 3 加工性能指标的描述 以n 个工件、m 台机器的f l o w s h o p 为例( 约定调度问题为非抢占式，每个 工件或操作不能在同一台机器上多次加工，不考虑工件加工优先权和批量) ，给 出调度性能指标。首先引入一些相关变量和符号； 1 ：工件以进行第j 道操作的等待时间： 2 嵋：工件的总加工等待时间，即m 一； 3 g ：工件