（计算机软件与理论专业论文）一种混合蚁群算法在jsp问题中的应用研究.pdf

一种混合蚁群算法在j s p 问题中的应用研究 捅婴 随着市场竞争的日趋激烈，每个企业都在寻求更好的生产与运作管理方案， 以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。生产与 运作管理的核心是车间调度问题能否高效地获得优化解，研究车间调度问题具 有很大的理论意义和现实价值。 车间调度问题是解决如何按时问的先后分配资源来完成不同的生产任务， 使预定目标最优化的问题。作业车间调度一( j s p ) 问题是许多实际车间调度问 题的简化模型，是一个典型的n p - 难问题。该问题具有约束性、非线性、不确 定性、大规模性等复杂性，已被证明在多项式时间内得不到最优值。近年来， 对于j o b - s h o p 调度问题求解方式主要有启发式算法和元启发式算法，但各有其 不足之处：元启发式方法的运行时间长，可获得较好的解，但其解不稳定；启 发式方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优的解。 为了更好地解决作业车间调度问题，将一些解决此类问题较好的算法组合 起来。蚁群算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并 行全局搜索能力，但初期信息素匾乏，求解速度慢。禁忌搜索法( t a b u s e a r c h ) 是一种通过邻域搜索以获取最优解的方法，能有效地加快解的收敛速度。本文 根据蚁群算法的特点，对蚁群算法进行改进，并将禁忌搜索算法熔入到蚁群算 法中，以改善蚁群算法的收敛速度。算法动态融合的思想是首先应用改进的蚁 群算法找到j s r 问题的可行解，然后应用禁忌搜索在可行解的邻域找到更优的 解。最后，本文对j s p 问题应用实验仿真计算。结果表明，改进的蚁群算法与 禁忌搜索结合后的混合蚁群算法的收敛速度更高，具有更好的全局收敛性能， 能在更少的迭代次数达到全局最优解，具有更高的收敛速度。 关键词：蚁群算法；禁忌搜索；作业车间调度 ah y b rida n tc oio n yo p timiz a tio nf o rt h ejo bs h o p s c h e d ui in gp r o bie m a b s t r a c t w i t ht h ei n c r e a s i n gk e e nm a r k e tc o m p e t i t i o n ，e a c he n t e r p r i s el o o k s f o rb e t t e rs o l u t i o n st op r o d u c t i o na n do p e r a t i o nm a n a g e m e n ta i m i n ga t i m p r o v et h ec o r ec o m p e t i t i v ea d v a n t a g e t h ek e yt ot h em a n a g e m e n to f p r o d u c t i o na n do p e r a t i o nm a n a g e m e n ti st oa c h i e v et h eo p t i m a ls o l u t i o n s t h e r e f o r e ，t h es t u d yo fj o bs h o ps c h e d u l ep r o b l e mi st h eg r e a t s i g n i f i c a n c e j o bs h o pp r o b l e mi st os o l v et h ep r o b l e mt h a tm a k i n gp r e a r r a n g ei s o p t i m i z a t i o nb ya s s i g n i n gr e s o u r c e st of i n i s hd i f f e r e n tm a n u f a c t u r e t a s k sa c c o r d i n gt ot i m ee a r l yo rl a t e j o bs h o pp r o b l e mi st h ec o n c e n t r a t e m o d e lo fm a n ya c t u a lj o bs h o ps c h e d u l ep r o b l e m s ，a n di t i sat y p i c a l n o n d e t e r m i n i s t i cp o l y n o m i a l t i m eh a r dp r o b l e m t h ep r o b l e mh a sm a n y c o m p l e xc h a r a c t e r i s t i c s ，s u c ha sc o n s t r a i n t s ，n o n l i n e a r i t y ，u n c e r t a i n t y a n dl a r g es c a l e ，s oi ti sr e p o r t e dt h a ti tc a n tg e tt h eb e s to u t c o m e t h r o u g hp o l y n o m i a l i nr e c e n ty e a r s ，m e t a - h e u r i s t i c sa l g o r i t h mc a ng e t s t r o n gl i f t f o r c ea n s w e ri nm u c hs h o r t e rt i m e ，b u tt h e r ei sr a r eb e t t e r a n s w e r i nt h i sp a p e r ，w ep r e s e n tah y b r i da l g o r i t h mc o m b i n i n ga n tc o l o n y o p t i m i z a t i o na l g o r i t h mw i t ht h et a b o os e a r c ha l g o r i t h mf o rt h ec l a s s i c a l j o bs h o ps c h e d u l i n gp r o b l e m i n s t e a do fu s i n gt h ec o n v e n t i o n a l c o n s t r u c t i o na p p r o a c ht oc o n s t r u c tf e a s i b l es c h e d u l e s ，t h ep r o p o s e da n t c o l o n yo p t i m i z a t i o na l g o r i t h me m p l o y san o v e ld e c o m p o s i t i o nm e t h o d i n s p i r e db yt h es h i f t i n gb o t t l e n e c kp r o c e d u r e ，a n dam e c h a n i s mo f o c c a s i o n a lr e o p t i m i z a i t o n so fp a r t i a ls c h e d u l e s b e s i d e s ，at a b us e a r c h a l g o r i t h mi se m b e d d e dt oi m p r o v et h es o l u t i o nq u a l i t y w er u nt h e p r o p o s e da l g o r i t h mo ns o m eb e n c h m a r ki n s t a n c e sa n dt h eo u t c o m ei n d i c a t e t h eh y b r i da l g o r i t h mh a sb e t t e rc o n s t r i n g e n c ya n db e t t e rw h o l e c o n s t r i n g e n c y k e yw o r d s ：a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ；t a b us e a r c h ；j o bs h o p h e d u l ep r o b l e m 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含未获得 ( 洼；翅遗查墓丝置墨挂型直蛆笪：奎拦亘窒2 或其他教育机构的学位或证书 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：j 研伙签字日期：沙眵年广月力e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： 才讲伙 一字：彳讥 签字日期：缔月y 日 一种混合蚁群算法在j s p 问题中的应用研究 u 刖吾 车间调度问题一直是组合优化问题中的一个公认的难点问题，对此问题的 解决方案无外乎确定性算法和非确定性算法( 启发式算法) ，对于确定性算法， 也即精确算法是利用数学规划等方法求得问题精确解的算法。此方法固然可以 得到最优解但是对待规模较小的优化问题起计算是比较现实的，但是对于规模 稍大一点的问题确定性算法在现有的条件下近乎是不可能的算法。 近年来启发式算法发展迅速，其中智能算法发展尤为突出。大量新颖的智 能算法已经被应用到车间调度问题当中，并且取得了良好的效果。然而每一种 算法都有其自身的优缺点，单独使用一种算法解决复杂的车间调度问题都会有 各种各样的问题凸现。现在的趋势是不同算法相结合去解决j s p 问题。 蚁群优化( a c o ) 这个在9 0 年代初产生的群体智能算法，在解决t s p 问 题中取得了巨大的成功，很快就被尝试用来解决j s p 问题，然而结果却不是令 人满意的。对于某些问题，例如单机器总权重延迟问题、开放车间问题和资源 约束项目调度问题，a c o 是性能最好的算法之一。而对于其他经典的调度问题 如排列流水车间问题和作业车间问题计算结果还远逊于当前最先进的算法。【1 】 本文针对单独使用蚁群优化来解决车间调度问题的不足，受转换瓶颈算法 启发，尝试把蚁群优化与禁忌搜索算法相结合来解决车间调度问题。 一种混合蚁群算法在j s p 超题中黪应用研究 1 引言 1 1 课题研究背景及意义 1 1 1 课题研究背景 车间调度问题是交通运输、科研、服务行业以及各种企业生产中普遍遇到 的闻题，也是调度领域和f m s 中人们广泛注意的闻题。它最旱是在机器制造业 中提出来的，但事实上它在编制作业计划、企业管理、交通运输、航空航天、 医疗卫生等各个领域都有广泛的应用。因此，车间调度问题中的任务、机器、 资源都应理解为抽象的概念，可以代表及其广泛的具体对象。与生产计划相比， 车间调度一般是在线实时的，对快速高效运行要求更高。 车间调度问题应用如此广泛，以至于在应用数学、计算机科学、运筹学、 人工智能以及工程科学等领域，大量新的文献不断涌现。由此可见调度研究的 重要性。随着现代制造业中车阆调度问题的复杂性和重要性的提高，迫切需要 研究有效的车间调度方法。随着现代制造业的发展，小批量、多类型的、有不 同完_ i 时间和产品要求的产品需求逐渐取代大批量单类型的产品制造计划。在 这种情况下，如何利用现有的资源( 加工能力) ，满足被加工任务所需的各种约 束( ! j n t 次序、所需机器) ，使所有的任务能尽量按时完成c 眭能指标最小) ，就成 为一个十分现实和迫切的问题。由于理论上已经证明车间调度问题属于典型的 n p 难闻题& 3 ，不可能在多项式复杂度的时闻算法内找到最优解。有越来越多 的入开展了对该问题的研究，产生了许多方法，并随着对各类调度闻题研究深 入及各种交叉学科的发展，出现了许多新魄车阆调度理论和方法，并取得了许 多研究成果。 1 1 2 选题意义 车间调度问题是在一定的时间内，进行可用共享资源的分配和生产任务的 排序，以满足某些指定的性能指标。简单地说，生产调度问题就是按时间分配 资源来完成任务的闯题( 2 3 。 蚁群算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 是毒意大捌学者 m d o r i g o 【3 】等人在2 0 世纪9 0 年代初通过模拟良然界中蚂蚁集体觅食的行为丽 提出的一种基予种群的启发式仿生类算法。它是继模拟退火算法、遗传算法、 禁忌搜索算法、神经网络算法等启发式搜索算法以后的又一种应用子组合优化 一种混合蚁群算法在j s p 问题中的应用研究 问题的启发式搜索算法。虽然与已经发展完备的一些启发式算法比较起来，蚁 群算法的计算量比较大、搜索时间长、有时候效果并不理想，但是它的成功运 用还是激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算 法的研究。众多的研究结果已经证明，蚁群算法具有很强的发现较好解的能力， 该算法不仅利用了正反馈原理加快进化过程，而且是一种本质并行的算法，不 同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好 解。由于鲁棒性强，使得蚁群算法易于解决各种不同的优化问题。 本课题研究的目的是针对求解n p 难的车间调度存在的问题，通过深入研 究问题的性质，提出混合蚁群算法的求解方法，利用禁忌搜索提高解的质量和 稳定性。 1 2 蚁群算法研究现状 最先提出的蚁群算法被称为a s 4 7 1 ( a n ts y s t e m ) ，它是m d o r i g o 、a c o l o m i 、 v m a n i e z z o 在意大利的米兰理工学院合作研究组合优化问题的计算机智能解 ? 决方法时的研究成果。a s 算法首先应用于解决旅行商问题( t s p ) ，随 ，v m a n i e z z o 、a c o l o m i 把a s 算法用于解决二次分配问题( q a p ) 。最初的赴 算法的效果并不理想，但是后续的研究将蚁群算法和局部搜索以及其它的一些 优化方法相结合获得的许多令人振奋的成果。 1 9 9 5 年l m g a m b a r d e l l a 和m d o r i g o 提出y a n t 。o 算法【8 捌。该算法建立 了a s 与q 学习机制( q 1 e a r n i n g ) 0 0 的联系。它在a s 算法的随机比例规则基 础上，在解构造过程中提出了伪随机比例状态迁移规则( p s e u d o r a n d o mp r o p o r o t i o n a ls t a t et r a n s i t i o nr u l e ) 从而能够实现解构造过程中知识探索( e x p l o r a t i o n ) 和知识利用( e x p l o i t a t i o n ) 的平衡，并引入信息素局部更新过程，信息素局部 更新规则使用了q 学习机制。此外，在信息素的全局更新中采用了精英策略。 a n t q 是一个非常有效的算法。 此后，m d o r i g o 和l m g a m b a r d e l l a 在a n t q 算法基础上提出t a c s t l l 1 2 】 ( a n t c o l o n ys y s t e m ) ；t s t u t z l e 和h h o o s 提出 m m a s 1 3 1 ( m a x m i n a n t s y s t e m ) 。这两种扩展的蚂蚁算法都被用于解决对称旅行商问题( t s p ) 以及非 对称旅行商问题( a t s p ) ，并取得了比较满意的结果。m m a s 算法采用了用 当前找到的最好解来更新信息素指引蚂蚁向更高质量的解空间搜索的贪婪策 一种混合蚁群算法在j s p 问题中的应用研究 略，并对信息素设立上下限来避免算法的早熟。 1 9 9 9 年，m d o r i g o 、g d i c a r o 和l m g a m b a r d e l l a 把此前各种基于a s 演 化而得的算法归结到一个统一的框架中，并提供了抽象而规范的算法描述，称 为a c o 元启发式算法【1 4 】( a n tc o l o n yo p t i m i z a t i o nm e t a h e u r i s t i c ) ，简称为a c o 算法。a c o 算法的优点在于：利用了正反馈原理加快进化过程；是一种本质并 行的算法；不同个体之间不断进行信息的交流和传递，从而能够相互协作，有 利于发现较好的解；由于鲁棒性强，故易于解决各种不同的优化问题。但是， 蚁群算法的计算量比较大、搜索时间长、有时候效果并不理想，国内外的研究 人员针对蚁群算法的这些问题，做了许多研究工作，有的将蚁群算法与其它算 法相结合，有的给蚁群系统加入变异特征，取得了许多研究和应用成果。 b b u l l n h e i m e r 等【冽提出了一种基于蚂蚁等级的a s r e n k 算，w j g u t j a h r 2 9 珈】提出了基于图的蚂蚁算法g b a s ( g r a p h b a s e da n ts y s t e m ) ， 并证明了算法将以概率1 一收敛于最优解。其中，可以通过选择足够大的 蚂蚁数量或足够小的信息素挥发系数p 来获得任意小的值。c b l u m 3 1 】针对可 转换为0 1 整数规划问题的组合优化问题，提出了一种h c - a c o 算法。该算法 利用一些策略来避免算法陷入局部最优解。 吴庆洪【1 5 】等人提出了具有变异特征的蚁群算法，有机地结合了2 - o p t 方法， 提高了算法的搜索速度。吴斌、史忠植【1 6 】在蚁群算法的基础上提出了相遇算法， 其基本思想是在求解t s p 问题中，用两只蚂蚁共同完成对一条路径的搜索，并将 相遇算法与采用并行策略的分段算法相结合提出一种基于蚁群算法的t s p 问题 分段求解算法，提高搜索速度。陈峻、沈洁、秦玲【1 7 】等针对蚁群算法加速收敛 和早熟停滞现象的矛盾，提出了一种基于分布均匀度的自适应蚁群算法。该算 法根据优化过程中解的分布均匀度，自适应地调整路径选择概率策略和信息素 更新策略，以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。朱庆 保、杨志军【1 8 】针对蚁群算法在进行大规模优化时收敛时间过长，提出了基于变 异和动态信息素更新的蚁群优化算法。该算法以最近的邻居节点选择和动态信 息素更新策略来加速全局收敛，以一种独特的变异策略来加快局部寻优，使收 敛速度大幅度地提高。 i w a t a n a b e 和s m a t s u i t 3 2 1 通过白适应的控制候选集合，改善a c o 算法性 一种混合蚁群算法在j s p 问题中的应用研究 能；p k o r o 吾e s 和j 誊i 一3 3 】用多级的a c o 算法解决了网络划分问题( m e s h p a r t i t i o n i n gp r o b l e m ) ；c s o l n o n 卅研究了蚁群算法搜索的多样性和快速收敛性 之间的矛盾，通过对算法参数的研究提出了在算法初期增加预处理步骤，希望 在不影响搜索多样性的前提下，提高收敛速度，通过对约束满足问题( c o n s t r a i n s a t i s f a c t i o np r o b l e m ) 的仿真试验表明了算法确实能提高速度。 目前大量的研究工作注重于a c o 的实际应用 3 6 - 3 8 1 ，然而，近几年的研究发 现：a c o 用于解决组合优化问题时，也会遇到类似进化算法中的d e c e p t i o n 和 b i a s 3 9 】现象。例如：c b l u m 和m s a m p e l s 研究a c o 用于作业调度问题( s h o p s c h e d u l i n g p r o b l e m s ) 时发现：段时间之后a c o 的性能会由于信息素模式和 处理的问题实例而下降，这种现象称为：s e c o n d o r d e rd e c e p t i o n 4 1 l 或者s e a r c h b i a s ，它意味着随着时间的推移找到更好解的可能性越来越小。j m o n t g o m e r y 4 2 等试图找出导致算法s e a r c hb i a s 的原因；c b l u m 和m d o r i g o 3 5 】针对蚁群算法求 解组合优化是遇到的s e c o n do r d e rd e c e p t i o n 问题，做了大量的研究工作。然而 算法性能的下降原因仍然是未知的，这些情况表明我们需要对a c o 算法行为做 更多更深入的了解。 i应当指出，现阶段对蚁群算法的研究大多还只是停留在仿真阶段，尚未能 提出一个完善的理论分析，对它的有效性也没有给出严格的数学解释。但是， 理论上的不完善并不妨碍应用，有时应用还会超前于理论，并推动理论研究， 蚁群算法的研究正是如此。 目前，蚁群算法已成为国际智能计算领域关注的热点和前沿课题。1 9 9 8 年 在布鲁塞尔专门召开了第一届蚂蚁优化国际研讨会，以后每两年召开一次。尽 管蚁群算法的严格理论基础尚未奠定，但这种新兴的智能进化仿生算法已展现 出勃勃生机。 1 3 主要研究内容及论文结构 主要研究内容： 蚁群算法求解j s p 问题。包括j s p 问题的模型，蚁 群算法参数初始值的确定和蚁群算法与禁忌搜索的结合等。 论文结构 一转混会蚁璞算法在j s pi n - j 题串熬应粥裂究 第1 章绪论。奔绍了论文研究的背景及选题赡意义；蚁群算法及牵闻调度闻 题的研究现状：最瑟说明了论文主要研究内容及结构。 第2 章j s p 闯题介绍。介绍了车闽调度闯题的描述、分类、特点等；以及j s p 问题的描述、模型及解决方法等。 第3 章蚁群算法。概述了蚁群算法的发展现状、基本原理及步骤，分析了 蚁群算法的特点，并对蚁群算法的一些理论进行了讨论。 第4 章基本蚊群算法求解j s p 闯题的。描在分析了基本蚁群算法的基础上， 提离了瑟纛j s p 酌蚁群算法。 第5 章混合粪望群算法求解j s p 弱题。将蚁群算法进行改进并与禁忌搜索进行 结合解决j s p 阏题 结论。对本文的工作进行总结，并对进一步研究方向作了展望。 一种混合蚁群算法在j s p 问题中的应用研究 2 作业车间调度问题 作业车间调度与控制是管理与生产自动化的核心技术，车间生产作业计划 调度是其中重要的一环，它在工厂经营管理、产品制造这两个层次上都占有极 其重要的地位和作用，它主要解决工件在机器上的调度和资源分配问题。合理 的作业车间调度是实现作业车间调度自动化和集成化的重要环节。 作业车间调度的研究主要可分为建模和调度算法设计两方面，它是一个交 叉的研究领域，涉及运筹学、数学、计算机工程、控制工程、工业设计等多个 学科。其中，建模主要研究调度模型、调度规划、目标函数等内容，算法主要 研究算法的设计、算法的复杂性、算法的收敛性和优化质量等内容。本章研究 作业车间调度的模型建立，并分析求解作业车间调度的优化算法，提出采用蚁 群算法来求解作业车间调度问题。 2 1 作业车间调度问题 2 1 1 作业车间调度问题描述 作业车间调度问题是对生产过程的作业计划，一般可以描述为：针对某项可 以分解的工作，在一定的约束条件下，安排其组成部分操作所占用的资源、加 工时间及先后顺序，实现产品制造时间或成本等最优，描述如图2 1 所示【4 3 】。 图2 - 1 作业车间调度描述图 一种混合蚁群算法在j s p 问题中的应用研究 作业车间调度问题是安排工件加工任务到加工设备上，它是在工件加工工 艺等约束条件下，通过决策与优化，达到加工时间最短、成本最低等目标。影 响调度问题的因素很多，正常情况下有产品的投产期、交货期完成期、生产能 力、加工顺序、加工设备占用和原料的可用性、批量大小、加工路径、成本限 制等，这些都是约束条件。有些约束条件是必须满足的，如交货期、生产能力 等，而有些达到一定的满意度作业车间调度问题的描述，如生产成本等，这些 约束在进行调度时可以作为确定性因素。而对于设备故障，原料供应变化、生 产任务变化等非正常情况，都是事先不能预见的，在进行调度时大都作为非确 定性因素考虑。生产调度中涉及的工厂资源包括原料、设备加工、存储、运输、 人力、资金、能源等。资源的详细分配受到产品的生产工艺限制。 作业车间调度问题的性能指标可以是成本最低、库存费最少、生产周期最 短、生产切换最少、设备利用率最高、三废最少等。 2 1 2 作业车间调度的特点及分类 作业车间调度将生产任务分解，将任务安排到加工设备，实现最优加工的 过程，其主要特点有： ( 1 ) 建模与计算复杂性，车间中机器、工件、缓存搬运系统之间关系复杂， 它们之间又相互影响相互作用。每个工件之间又要考虑它的加工时间、完成时 间以及安装时间和操作顺序等，因而作业车间调度问题显得相当复杂。调度问 题往往是通过等式或不等式约束条件来计算的，属于典型的问题。随着问题规 模的加大，计算量也急剧加大，所以调度问题往往没有精确的解，通常是在解 答过程中寻求其最优解或满意解。 ( 2 ) 动态随机性，调度中存在很多随机性和不确定性，如工件的交货期变 更，工件的加工完成时间，工件的到达时间。另外一些突发事件也增加的调度 的难度和随机性。如机器故障、作业交货期的变更等。 ( 3 ) 多约束性调度中受到很多约束条件的限制，如缓存容量、资源数量、 工件到期时间与操作顺序等。此外，还有人为的附加因素，如机器负荷平衡等 等约束条件。 ( 4 ) 多目标性调度的目标很多，目标之间往往又相互冲突。主要有基于作 一种混合蚁群算法在j s p 问题中的应用研究 业交货期的目标、基于作业完成时间的目标、基于生产成本的目标三类目标。 按照不同的分类标准，作业车间调度可分为6 种类型：( 1 ) 开环车间和闭 环车间；( 2 ) 单台处理机、多台并行机、j o bs h o p 和f l o ws h o p ；( 3 ) 基于调度 费用和调度性能的指标；( 4 ) 确定性调度、随机性调度；( 5 ) 静态调度、动态调度；( 6 ) 有序加工，无序加工。现代车间调度类型往往是j o bs h o p 和f l o ws h o p 型，且 是动态的。 j s p 问题是企业生产活动中最一般最复杂的作业调度问题，是许多实际生 产调度问题的简化模型，也是最困难的组合优化问题之一m ，本文将分析作业 车间调度的描述及优化技术。 2 2 作业车间调度模型描述 作业车间调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 可描述为：给定 一个工件的集合和一个机器的集合，每个工件包括多道工序，每道工序需要在 一台给定的机器上非间断的加工一段时间；每台机器一次最多只能加工一道工 序；调度就是把工序分配给机器上的一个时间段。问题的目标是找到最小时间 长度的调度。 已知： ( 1 ) - i _ 件集p = p l ，p 2 p ) ，p i 为第i 个工件，i = 1 ，2 ，n ； ( 2 ) 机器集m = m l ，m 2 ，m m ，m j 为j 号机器，j = 1 ，2 ，o o e9 m ； ( 3 ) t 序序列集o p = o p l ，o p 2 ，o p n ，o p i = o p i l ，o p a ，o 陆】为工件 p i 的工序序列。o p i k 为第i 个工件在第k 道工序使用的机器号，o p i k = o 表示工件 p i 的第k 道工序不加工，k = l ，2 ，m ，此为技术约束条件； ( 4 ) 每个工件使用每台机器的时间矩阵t ，t i j t 与第i 个工件p i 使用第j 个机器的时间。当t i j = o ，表示工件p i 不使用机器j o 在典型的j s p 调度问题中，除了技术约束外，通常还假定以下条件： ( 1 ) 整个加工过程中，一个工件不能在同一台机器上加工多次； ( 2 ) 任何一个工件的前一道工序加工完成后，方能进行后一道工序的加工， 在同一台机器上一个加工任务完成之后，方能开始另一个加工任务： ( 3 ) 各工件必须按工艺路线以指定的次序在机器上加工； 一种混合蚁群算法在j s p 问题中的应用研究 ( 4 ) 不考虑工件加工的优先权； ( 5 ) 每个工件的工序一旦进行就不能中断； ( 6 ) 一个工件同一时间只能在一台机器上加工，一台机器同一时间只能加 工一个工件，加工的开始时间为0 。 确定调度结果，安排机器的加工工序，必须满足工件的工艺约束条件和资 源占用约束，其各类约束条件描述如下 ( 1 ) 顺序约束 令q k 表示工件j 在机器k 上的完工时间，t j k 表示工件j 在机器k 上的加工 时间。 对于工件i ，如果在机器h 上的加工先于机器k ，则有约束q k - t j 。c i h ；另 一方面，如果在机器k 上的加工先于机器h ，则有约束c i h t i l 【c 。 定义如下的指示函数： 1 1 ，对于给定的工件i ，如果在机器h 上的加工先于机器k a 撤2 10 ，其它 以上约束也可以写成讯一t i l 【+ m ( 1 一a m k ) c i h i = 1 - - n ，h = l m ( 其中 m 是一个很大的数) 。 ( 2 ) 资源约束 对于两工件i 和j 都需要在机器k 上加工，如果工件i 先于j 来到，有约束 c ；i k c l l 【t j k ；另一方面，如果工件j 先于工件i 到达机器k 上n t ，则有c i l 【一 q k t j k 。 定义指示变量x i j l 【为 f 1 ，如果工件i 先于j 来到机器k 一1o ，其它 以上约束也可以写成q k c i l 【+ m ( 1 - - x i h l 【) t j 。；i ，j = 1 n ，k = l m ( 其 中m 是一个很大的数。 综上所述，以最大流程时间最小为目标调度问题可以用数学公式描述为【删 一种混合蚁群算法在j s p 问题中的应用研究 i n i i l 廷a 如a 蛾卅 s 丘 一+ 肘( | 1 9 f j l 七) 芝；f = 1 n ；h , k - - - 1 m c 雕一+ m ( 1 一丐弧) f 胪；f ，j = 1 n ，k - 1 m o ，i - 1 巧歹= 1 。m = 吡f = 1 。n ；h ，k = 1 一m 王肚；o ，1 ；f ，j = 1 。n ；k = 1 m 其中，式( 2 1 ) 表示调度的目标函数，即要求机器加工最大完成时间最 小化 也叫m a k e s p a n ；式( 2 2 ) 表示工艺约束条件，它决定了各种工件各自操作的先 后加工顺序，保证每个工件的加工顺序满足预先的要求；式( 2 3 ) 表示加工各 个工件的各机器的先后顺序，保证每台机器一次只能加工一个工件。 此外，r o y e t a l 淄3 有向图也是描述j s p 的常用工具。对于n 个工件、m 台 机器( 共n 个操作) 的j s p ，所对应的有向图g = ( v ，a ，e ) 如图2 2 所示。 其中，v 为所有操作构成的顶点集，包括0 和n + 1 两个虚拟操作( 表示加工 的开始和结束) ，a 为n 条子边构成的边集，子边( 实线) 表示某工件按约束条 件在所有机器上从开始到结束的加工路径；e 为m 条子边构成的弧集，子弧( 虚 线) 表示同台机器上的加工各操作的连接。 集合v = ( 0 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，l o 中的节点表示工序序列， 其中0 节点和1 0 是虚拟工序，它表示作业的开始和结束；集合a = ( ( 1 ，2 ) ， ( 2 ，3 ) ，( 4 ，5 ) ，( 5 ，6 ) ，( 7 ，8 ) ，( 8 ，9 ) ) 中单连弧表示工件的工序加工顺 序约束，集合e = ( 1 ，5 ) ，( 5 ，9 ) ，( 9 ，1 ) ，( 2 ，4 ) ，( 4 ，8 ) ，( 2 ，8 ) ，( 7 ，6 ) ， ( 7 ，3 ) ，( 6 ，3 ) ) 中无向弧表示同一台机床的工序加工约束，他们之间并没有 加工顺序约束。集合可按每台机器分解成e - - e 。ue 2 ue m ，子集e 1 = ( 1 ，5 ) ， ( 5 ，9 ) ，( 9 ，1 ) 中双向析取弧表示在机器上进行加工的工序，其它类似。 一种混合蚁瓣算法在j s p 阏题中的应用研究 圈2 2 一个3 x 3j s p 调度有蠢匿 用有向图描述的j s p 问题的目标是确定集合e 中每个无向弧的一个方向使 得最终得到的图为非循环图，使连接开始节点和终点节点弧的权重之和的最大 值达到最小，即加工时间最少。图2 4 就是一个以有向图表示的可行调度，在 图中三台机器上加工顺序为 ( 1 ，5 ，9 ) ，( 8 ，4 ，2 ) ，( 7 ，6 ，3 ) ) 。 图2 3 3x3 j s p 调度的一个可行调度 研究j s p 调度时还经常涉及三种调度，郎活动调度、半活动调度和j 延迟 调度，定义如下： 定义2 。l ：如果在不推迟其他操作或破坏优先顺序的条件下，其中没有一个 操作可以提前加工，这种调度称为活动调度。 定义2 2 如果在不改变机器上加工顺序的条件下，其中没有操作可以提前， 一种混合蚁群算法在j s p 问题中的应用研究 称这种调度为半活动调度。 定义2 3 如果至少存在一个工件等待加工时，对应的不存在相应的处于空 闲的机器，这种调度称为非延迟调度。 三种调度的包含关系如图2 4 所示。 图2 4 三种类型调度的关系 上述定义表明，若处于非活动调度下，则一定可以找到某些操作，使其可 以更早加工。当然，有时只能通过改变机器上工件的加工次序来做到。譬如当 一个操作在前道工序完成后，可将其插入到同一机器中操作时间比它长，而出 现时刻比它早的另一个操作之前，也即在那个操作还未开始加工前插入到机器 的空闲时间内。显然，通过将非活动调度转化为活动调度，加工时间必然有所 改善。对于正规调度指标，已经证明最优调度必为活动调度晰3 。 在作业车间调度中，主要有加工完成时间最小、总加工成本最小和工件提 前与延迟时间的加权平方和最小等目标函数。 2 3 车间调度问题算法分析 自从车间调度问题在2 0 世纪5 0 年代被开始广泛研究以来，经过几十年的 发展，产生了许多车间调度问题的类型m 和求解方法【删，对于车间调度问题， 根据需求的产生来源，可分为开环车间和闭环车间；根据加工系统的复杂性， 可分为单机、多台并行机、f l o ws h o p 和j o bs h o p ；根据性能指标，可分为基于 调度费用和调度性能的指标两大类。根据生产环境的特点，也可以将调度问题 分为确定性调度和随机性调度问题。根据作业的加工特点，也可以将调度问题 一种混合蚁群算法在j s p 问题中的应用研究 调度指标 分为静态调度和动态调度。实际中，车间调度的类型往往是j s p 型，且是动态的。 目前研究比较多的是j s p i h - j 题 4 9 1 5 0 】和流水车间调度问题【5 1 1 ，并随着对各类调度 问题研究的深入及各种交叉学科的发展，出现了许多新的车间调度理论【5 2 1 5 3 1 1 5 4 1 和方法【5 5 1 。早期关于流水车间调度问题，只局限于调整时间顺序依赖于两台机 器中的一台，一种动态规划方法，可用于求解大约1 5 个工件下这一问题的最小 化最大流程时间( m a k e s p a n ) 。当调整时间分离且顺序依赖所有m 台机器时，且有 无限大存储空间存储已处理过的文件时，数学规划方法和建立在图搜索规则之 上【5 6 】的隐枚举方法可被修改用来解决问题。这些均是流水车间调度问题的一些 最优算法。这些算法的计算时间即使在中等规模时已经非常大。因此人们转向 对高效、有效的启发式方法的研究。姜思杰，马玉林阳针对具有路径柔性的j s p 问题，以调度长度极小化为优化目标，提出新的动态优化调度算法将优化分配 算法、可行优化调度算法和故障调度算法有机的集成起来，能够在系统设备出 现异常时迅速产生最优或次优调度。但是启发式方法虽然能在较短时间内找到 解但解的质量往往不高，随着计算机运算速度的快速提高，元启发式算法越来 越受到人们的关注。车间调度问题的研究方法向着多元化的方向发展。目前关 于车间调度问题的研究主要分为两大类：启发式方法和元启发式方法。 1 启发式方法嗍陋1 ( 1 ) 数学规划法、( 2 ) 组合优化法、( 3 ) 规则调 度、( 4 ) 人工智能技术等。 ( 1 ) 数学规划法有线性规划( l i n e a rp r o g r a m m i n g ) 方法、非线性规划( n o n 躺龊搠撇酣 鳓媸舡勰勰黼栅彻蕤 一种混合蚁群算法在j s p 闯题中的应用研究 l i n e a rp r o g r a m m i n g ) 法、动态规划( d y n a m i c a lp r o g r a m m i n g ) 法、拉格朗日乘子 法等等，在这些算法中，线性规划法作为一种精确调度方法，是较成熟的方法 之一，但很多问题都不能以简单的线性关系精确表达，且变量多为整数，因此 他的使用受到很大限制。 ( 2 ) 组合优化方法包括分支定界法( b r a n c ha n db o u n d ) 1 6 3 】、割平面法等。其 中较常用的是分支定界法，它的效率与定界的方法以及搜索空间的结构密切相 关，如果能合理地这些因素，可将其用于中小规模问题的求解。由于调度问题 地复杂性，对于n p 难题，上述算法的计算时间随规模的增大而呈指数增长。s a t i n s c e ta l 删和p o t t sc n e ta l 删提出了改进的分支定界法，其不同点主要在于 分析规则、定界机制和上界的产生三方面的差异。这类方法虽然从理论上能求 得最优解，但由于其计算复杂性和搜索效率低下，难以解决大规模的调度问题。 ( 3 ) 规则调度旧1 是指在一般的调度算法基础上引入有效的调度规则，以寻 找近忧解。p a n w a l ks e ta l 【明总结t1 1 3 条规则，并将它们分为了三类：简单规 则、复合规则、启发式规则。这一方法可以大大缩短寻优过程，具有很强的使 用价值。在选用调度规则时，人们必须对实际情况做具体分析和必要的仿真实 验后，才可以适当选用。 ( 4 ) 人工智能方法油1 利用知识表达技术把人的知识包括进去，同时使用各 种搜索技术以求给调度问题一个令人满意的解。它把调度过程描述成一个在满 足约束的解空间中搜索的过程。人工智能方法如专家系统的研制，为调度问题 指明了一条通向应用的途径。但是具有只是难于表达和难于获取等缺点。 2 元启发式方法嘲嗍( 1 ) 模拟退火法、( 2 ) 禁忌搜索法、( 3 ) 遗传算法、( 4 ) 神 经网络算法、( 5 ) 蚁群算法。 ( 1 ) 模拟退火法( s i m u l a t e da 咂e a l i n g ) 模拟退火法( s a ) 【删将组合优化问题 与传统力学问题的热平衡问题类比，它模仿了晶体结晶的冷却过程，在较高温 度n 下，系统状态为s ，能量( 即目标函数) 为e ，选择s 的一个邻域s ，如果eu 、 ) e ( s ) ，则接受s 为下一个状态，否则以概率p ( - ( ( s ) 硒p ) ) 7 露接收。经过一 定次数的搜索，认为系统在此温度下达到平衡，则降低n 再进行搜索，直到满 足约束条件。 ( 2 ) 禁忌搜索法( t a b us e a r c h ) 禁忌搜索法( t s ) 【7 1 】【7 2 】【7 3 】也是一种通过邻域搜 一种混合蚁群算法在j s p 问题中的应用研究 索以获取最优解的方法，它从一个可行解s 出发，产生s 的s 邻域，如果f 为目标 、 函数，选取所有邻域中使厂t , s 夕为最优的状态最为下一个状态，并把这一移动 的反向移动存入一个称为禁忌移动( t a b um o v e ) 的表中。列在表中的移动在以后 若干步内不允许再产生，这样可避免搜索退回去。每搜索一次，更新一次禁忌 移动表。由于禁忌移动表的限制，有可能跳出局部极小。t a i l a r d e 【7 4 】提出了解 决f l o ws h o p 调度问题的禁忌搜索算法，l a g u n ae ta l 7 5 】 7 6 】最早将禁忌搜索策略应 用于j o bs h o p 调度中；为了更有效地搜索解空间，m a n u e l le ta l t 7 7 】引入了插入 移动和移动相结合的机制提高了搜索效率。 ( 3 ) 遗传算法( g e n e t i ca 1 9 0 r i t h m ) 遗传算法( g a ) 【7 8 】【7 9 】是一种模仿生物群体 进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和 变异等遗传操作来搜索最优解 7 3 1 1 7 s l s o l 。张长水【8 1 1 等用遗传算法对j o bs h o p 零件 排序问题进行优化搜索，并在