（机械设计及理论专业论文）基于蚁群算法与竞选算法的作业车间调度求解及比较研究.pdf

摘要 摘要 制造过程的调度技术，将在很大程度上影响产品生产的周期、成本和效率。优 化制造过程调度，可以有效地提高企业的生产管理水平和制造自动化水平，从而提 高企业的竞争力。作业车间调度问题是生产调度中许多实际问题的简化模型，是制 造类企业无法回避的一个关键且核心的问题。现行的各种调度方法在求解作业车间 调度问题时，都存在各种各样的缺陷。因此，改进现有的调度方法或者寻找新的调 度方法，始终具有重要的理论价值和实际意义。 蚁群算法的搜索机制模拟蚂蚁觅食过程中的群体行为，适合于求解旅行商问题 等组合优化问题，但应用于作业车间调度问题的研究不多，且优化效果不明显，也 没有一般性规律可循。竞选算法搜索机制模拟竞选活动中对更高支持率的追求动机， 目前主要应用于连续域内的各种函数优化问题。 本文针对作业车间调度问题，对蚁群算法进行改进，设计了一种新的信息素更 新方式；对竞选算法进行离散化设计，探索新的求解作业车间调度问题的调度方法， 并对这两种算法进行比较。本文的主要研究结果如下： ( 1 ) 本文综合分析了蚁群算法的特点及作业车间调度问题的特点，讨论了两种 经典的改进蚁群算法一蚁群系统与最大最小蚂蚁系统一的算法思想及求解机制。在 此基础上，提出了一种新的改进蚁群算法。为了验证该改进蚁群算法的有效性，将 其应用于作业车间调度问题与柔性作业车间调度问题的求解。采用文献中的测试函 数进行计算，并将计算结果与文献中的结果进行比较分析。结果表明，该改进蚁群 算法大大提高了问题的求解效率及求解结果。 ( 2 ) 介绍了竞选算法的基本思想、基本原理以及在连续优化领域内的应用研究。 将竞选算法应用于求解作业车间生产调度问题，采用基于工序的表达法表示问题的 解，采用基于关键路径的邻域搜索方法生成局部选民，这两者是竞选算法的离散化 设计的核心技术。将离散化的竞选算法求解f t 0 6 算例以及l a 系列标准调度函数， 无论是计算时间，还是计算结果，离散的竞选算法都取得了较好的效果，表明了该 改进算法的有效性及可行性。 ( 3 ) 利用m a t l a b7 编程实现了上述两种算法的操作，构建了一个求解作业车 间调度问题的工具包。 广东工业大学硕士学位论文 ( 4 ) 分析了改进蚁群算法与改进竞选算法两种启发式优化算法在算法特性方面 的异同点，并对这两种算法进行求解质量、算法时间复杂度和空间复杂度等方面的 比较分析。 关键字：蚁群算法；竞选算法；作业车间生产调度；柔性作业车间生产调度 a b s t r a c t a b s t r a c t s c h e d u l i n gt e c h n o l o g i e si np r o d u c i n gp r o c e s sw o u l da f f e c tp r o d u c tp r o d u c ep e r i o d ， p r o d u c tc o s ta n de f f i c i e n c y o p t i m i z i n gs c h e d u l i n gp r o b l e m si np r o d u c ep r o c e s sc o u l d i m p r o v et h el e v e lo fm a n a g e m e n ta n dm a n u f a c t u r i n ga u t o m a t i z a t i o n ，w h i c hw o u l dh e l p m a n u f a c t u r i n gc o r p o r a t i o n s i n c r e a s et h e c o m p e t i t i o np o w e r j o b s h o ps c h e d u l i n g p r o b l e m ( j s p ) w a s as i m p l i f i e dm o d e lo fm a n yp r a c t i c a lp r o b l e m s i tw a sa l s oac o r e p r o b l e mc o r p o r a t i o n s c o u l db ei n e v i t a b l et of a c e b u tt h e e x i s t i n gs c h e d u l i n g t e c h n o l o g i e sh a d d i f f e r e n tk i n d so fl i m i t a t i o n sw h e nt h e yw e r ea p p l i e dt os o l v ej s p s s o ， t oi m p r o v ee x i s t i n gs c h e d u l i n gm e t h o d so rf i n dn e ws c h e d u l i n gt e c h n o l o g i e st os o l v e j s p sa c c u r a t e l ya n dq u i c k l yw o u l db ep r o v i d e dw i t ha ni m p o r t a n ta c a d e m i cv a l u ea n d p r a c t i c a ls i g n i f i c a n c e a n tc o l o n yo p t i m i z a t i o n ( a c o ) a n a l o g i z e dt h es o c i a lb e h a v i o ro fs e e k i n gf o o do f a n tc o l o n i e s ，w h i c hw a sg o o df o rs o l v i n gc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s ，s u c ha s t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，b u ti t ss t u d yi nj s pf i e l dw a sf e w , t h eo p t i m i z a t i o n r e s u l tw a sn o tv e r yg o o d ，a n dt h e r ew a sn o tr e g u l a rr u l et ob eu s e d e l e c t i o nc a m p a i g n a l g o r i t h m ( e c a ) s i m u l a t e dt h ep u r s u i to fh i g h e s ts u p p o r tr a t ei ne l e c t i o na c t i v i t i e s a t p r e s e n t ，e c aw a sa l m o s tu s e di ne n g i n e e r i n gf i e l d s i no r d e rt os o l v ej s p s ，t h i sp a p e rd e s i g n e dan e wp h e r o m o n eu p d a t er u l e ；a n i m p r o v e de c aw a sd e s i g n e dt oe x p l o r en e ws c h e d u l i n gt e c h n o l o g i e st os o l v ej s p s a n d t h e nt h e s et w oa l g o r i t h m sw e r ec o m p a r e di nm a n ya s p e c t s t h ec o n c l u s i o n st h i sp a p e r h a dg o r e nf o l l o w e da s ： f i r s t l y ，t h i sp a p e rp r e s e n t e dt h ec h a r a c t e r so fa c o a n dj s ps e p a r a t e l y t h e nt h i s p a p e ri n t r o d u c e dt h ei d e a sa n dp r i n c i p l e so f t w oc l a s s i ci m p r o v e da c o ，a n tc o l o n y s y s t e m ( a c s ) a n dm a x m i nc o l o n ys y s t e m ( m m a s ) t h i sp a p e rp r o p o s e da ni m p r o v e d a c ob a s e do nt h ec h a r a c t e r so fa c sa n dm m a s a n dt h e nt h ei m p r o v e da c ow a s a p p l i e dt o s o l v ej s p sa n dm o r ec o m p l i c a t e dp r o d u c t i o ns c h e d u l i n gp r o b l e m s ，f l e x i b l e j o b s h o ps c h e d u l i n gp r o b l e m s ( f j s p s ) m e n t i o n e d i nr e f e r e n c e s t h er e s u l t s d e m o n s t r a t e dt h a tt h ei m p r o v e da c oc o u l di m p r o v et h e q u a l i t y a n de f f i c i e n c yo f s o l u t i o n sa f t e rc o m p a r e dt h er e s u l t sw i t ht h es o l u t i o n st h a tt h eo t h e rh e u r i s t i ca l g o r i t h m i i i 广东工业大学硕士学位论文 s e c o n d l y ，t h i sp a p e ri n t r o d u c e dt h eb a s i ci d e a , p r i n c i p l ea n dc o m p u t ep r o c e s sa b o u t e c a e c ah a sb e e na p p l i e dt os o l v ep r a c t i c a le n g i n e e r i n gp r o b l e m si nm a n yf i e l d s b u t i tw o u l db ei m p r o v e dt os o l v ed i s c r e t ep r o b l e m s t h i sp a p e re x p r e s s e dt h ej s ps o l u t i o n 。 b a s e do no p e r a t i o ne x p r e s s i o nm e t h o d ，a n dg e n e r a t e dl o c a lv o t e rb a s e do nc r i t i c a lp a t h m e t h o dn e i g h b o rs e a r c ht e c h n o l o g y , w h i c hw a st h ek e yt e c h n o l o g yf o rt h ed e s i g no f i m p r o v e de c a t h i sp a p e ra p p l i e dt h ei m p r o v ee c a t os o l v ei n s t a n c e so ff t 0 6 ，l a o1 ， l a 0 3 ，l a 0 4a n dl a 0 5a n dl a l5 t h er e s u l t ss h o w e dt h ei m p r o v e de c ac o u l dg e tg o o d o p t i m i z m i o ns o l u t i o n si nl e s sc o m p u t i n gt i m e t h i r d l y , t h i sp a p e rp r o g r a m m e dt oc o m p l e t et h es c h e d u l i n go p e r a t i o n sf o rb o t h a l g o r i t h m su s i n gm a t l a b7 ，a n dt h e nt h i sp a p e rd e v e l o p e dat o o l b o xt os o l v ej s p s f o u r t h l y , t h i sp a p e rh a da na n a l y s i sb yc o m p a r i n gt h e s et w oi m p r o v e da l g o r i t h m si n s o m ec h a r a c t e r s ，s u c ha ss e a r c he f f i c i e n c y , c o m p u t a t i o n a lc o m p l e x i t y k e y w o r d s ： a mc o l o n yo p t i m i z a t i o n ；e l e c t i o nc a m p a i g na l g o r i t h m ；j o b - s h o p s c h e d u l i n gp r o b l e m ；f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m 广东工业大学硕士学住论文 c o n t e n t a b s t r a c t ( c h i n e s e ) i a b s t r a c t c o n t e n t ( c h i n e s e ) v c o n t e n t c h a p t e r 1 i n t r o d u c t i o n 1 1 1 s i g n i f i c a n c eo f t h es t u d y 1 1 2r e s e a r c hi n t r o d u c t i o na th o m ea n da b r o a d 2 1 2 1 o p e r a t i o n a lr e s e a r c hm e t h o d 2 1 2 2m e t h o db a s e do nh e u r i s t i cr u l e 2 1 2 3s i m u l a t i o ns c h e d u l i n gm e t h o d 3 1 2 4 a r t i f i c i a li n t e l l i g e n c em e t h o d 3 1 3 j o b s h o ps c h e d u l i n gp r o b l e m 7 1 ：；1 d e s c r i p t i o n 7 1 3 2f e a t u r e so f j o b - s h o ps c h e d u l i n gp r o b l e m 7 1 ：；3f u n c t i o ni n d e x e s 8 1 4 s u p p o r t i n gt h e o r y 9 1 5 s t u d yw o r ko ft h i sp a p e r 9 c h a p t e r2a p p l i e di m p r o v e da n tc o l o n yo p t i m i z a t i o nt os o l v ej o b s h o p s c h e d u l i n gp r o b l e m 11 2 1i n t r o d u c t i o n 。1l 2 2b a s i ca n tc o l o n yo p t i m i z a t i o n 1 l 2 2 1i n u o d u c t i o no fb a s i ca n tc o l o n yo p t i m i z a t i o n 1 1 2 2 2m o d e lo fb a s i ca n tc o l o n yo p t i m i z a t i o n 13 2 3c l a s s i ca n tc o l o n yo p t i m i z a t i o n 15 2 3 1a n tc o l o n ys y s t e m 15 2 ：；2m a x m i na n ts y s t e m 17 2 4 i m p r o v e da n tc o l o n yo p t i m i z a t i o no f t h i sp a p e r 17 2 4 1 d e s c r i p t i o n 17 v i i i c o n t e n t 2 4 2 i m p r o v e dp h e r o m o n eu p d a t er u l e 1 8 2 4 3 i m p r o v e ds t a t et r a n s i tr u l e 1 9 2 5 s o l v i n gj o b s h o ps c h e d u l i n gp r o b l e mb yi m p r o v e d a n tc o l o n y o p t i m i z a t i o n 1 9 2 5 1 c o m p u t i n gp r o c e s s j 1 9 2 5 2 t e s t i n ga n da n a l y z i n g 2 0 2 6 a p p l i e di m p r o v e da n tc o l o n yo p t i m i z a t i o n t os o l v ef l e x i b l ej o b 。s h o p s c h e d u l i n gp r o b l e m 2 6 2 6 1 d e s c r i p t i o no f f l e x i b l ej o b - s h o ps c h e d u l i n gp r o b l e m 2 7 2 6 2 s c h e d u l i n gm o d e l 2 8 2 6 3 s t a t et r a n s i tr u l e 2 9 2 6 4 c o m p u t i n gp r o c e s s 3 0 2 6 4 1 o p e r a t i o np r o d u c er u l e 3 0 2 6 4 2 s o l u t i o nu p d a t er u l e 3 0 2 6 4 3 s o l v i n gp r o c e s s 31 2 6 5 t e s t i n ga n da n a l y z i n g 31 2 7c o n c l u s i o n s 3 7 c h a p t e r3s o l v i n gj o b s h o ps c h e d u l i n g p r o b l e mb yi m p r o v e de l e c t i o n c a m p a i g na l g o r i t h m 3 9 3 1i n t r o d u c t i o n 。3 9 3 2b a s i ci d e a sa n dp r i n c i p l e so f e l e c t i o nc a m p a i g na l g o r i t h m 3 9 3 3 i m p r o v e de l e c t i o nc a m p a i g na l g o r i t h m 4 0 3 3 1 c o d i n ga n de n c o d i n g 。4 1 3 3 2 c o m p u t i n gp r o c e s s 4 3 3 4 a p p l i e di m p r o v e de l e c t i o nc a m p a i g na l g o r i t h m t os o l v ej o b 。s h o p s c h e d u l i n gp r o b l e m 4 5 3 4 1 g e n e r a t i n gl o c a lv o t e r 4 5 3 4 2r e s u l t sa n a l y z i n g 4 6 3 5c o n c l u s i o n s 5 0 i x 广东工业大学硕士学位论文 c h a p t e r 4 a n a l y s i sa n dc o m p a r i s o no fa n tc o l o n yo p t i m i z a t i o na n d e l e c t i o nc a m p a i g na l g o r i t h m 51 4 1 i n t r o d u c t i o n 51 4 2c h a r a t e r so ft h e s et w oa l g o r i t h e m s 51 4 2 1t h es a m ep o i n t so ft h e s et w oa l g o r i t h e m s 51 4 2 2t h ed i f f e r e n tp o i n t so ft h e s et w oa l g o r i t h e m s 5 2 4 3 c o m p l e x i t ya n a l y s i s 5 3 4 3 1t i m ec o m p l e x i t y 5 4 4 3 2 s p a c ec o m p l e x i t y 5 7 4 4 a n a l y z i n go p t i m i z a t i o nq u a l i t y 5 8 4 5c o n c l u s i o n s 5 9 c o n c l u s i o n sa n d p r o s p e c t s 6 0 r e f e r e n c e s 6 ：； p u b l i c a t i o n sd u r i n gp e r i o d so fp o s t g r a d u a t i o n 6 9 d e c l a r a t i o n 7 0 c o p y r i g h ts t a t e m e n t 7 1 a c k n o w l e d g e m e n t s 7 2 a p p e n d i xab e n c h m a r k f u n c t i o n so fj o b s h o ps c h e d u l i n gp r o b l e m 7 3 a p p e n d i xb b e n c h m a r kf u n c t i o n so ff l e x i b l ej o b - s h o ps c h e d u l i n gp r o b l e m o fk a c e m 7 9 x 第一章绪论 1 1研究意义 第一章绪论 近几十年来，随着制造技术与当代信息技术、自动化技术、现代管理技术及系 统工程等技术方法的相互融合，涌现出了许多的先进制造技术和现代管理技术等先 进制造模式。企业资源规划n 一1 、仿生制造系统1 、计算机集成制造系统、精细生产、 柔性制造系统、智能制造系统、敏捷制造系统h 】、虚拟制造技术等制造模式被广泛 地应用于生产制造中隋1 。这些先进的制造模式使得各类生产过程发生了显著的变化， 也使得制造企业的竞争力由原来的以质量、成本为主，逐渐扩展为质量、成本、时 间、环境、服务等环节并重1 。 尽管这些先进制造模式采用了不同的原理和实现技术，但它们都是通过合理配 置和优化内外资源、缩短制造周期、降低生产成本来解决企业普遍面临着的生产过 程中物料流程混乱、设备负荷不均衡、排队、等待时间过长等共性问题。在激烈的 市场竞争中，必须保证生产高效稳定运行，以获取最大的经济效益。而生产调度 ( p r o d u c t i o ns c h e d u l i n g ) 能够在满足系统约束条件下有效地配置资源并优化相关性 能指标。因此，生产调度很自然地成为以上各种先进制造模式共同关注的核心内容 和重要组成部分。 生产调度技术在很大程度上影响产品的周期、成本和效率。而车间生产调度是 制造系统的基础，因此，对其进行优化便成为各种先进制造技术和现代管理技术的 核心技术口1 。 在过去几十年中，人们将许多算法应用于调度领域，并且研究和开发了许多新 的调度算法，但这些调度算法在应用于实际生产调度时都需要特定的应用环境，简 单地将这些调度算法应用于实际生产其效果并不理想。这使得一些调度算法无法完 全发挥它们本身的特点。这也间接地阻碍了调度理论和应用的发展哺1 。很多研究表 明，找出一个调度问题的最优解往往是非常困难的，最有工程意义的求解算法是放 弃寻找最优解的目标，转而在有限的时间内找到一个合理的、有用的解。因此，研 究有效的调度方法与优化技术，设计先进而实用的调度与控制算法，在有限的时间 内找到一个合理的、有效的调度解，对于企业提高生产率，增强企业竞争力，实现 广东工业大学硕士学住论文 企业的现代化管理具有重要的理论价值和实际意义一引。 1 2国内外研究现状及分析 调度算法是调度技术的核心，其研究自2 0 世纪5 0 年代起在先进制造和自动化 领域学术界及工业界一直受到广泛的重视。6 0 7 0 年代建立了调度理论的主体( 经 典调度理论) 并重视调度复杂性的研究n 。国内对车间调度的研究起步比较晚，始于 9 0 年代。很多企业由于技术上的制约，基本上是靠调度人员的经验进行车间作业分 配和调度。但随着各种优化算法在各个领域的应用热潮，调度领域也成为一个研究 热点。 随着技术的不断向前发展，调度的重要性日益突出，调度方法的研究也逐渐走 向复杂化和多元化，基本上可以归结为4 种类型畸1 ：基于运筹学的方法n2 1 、基于启 发式规则的调度方法、基于仿真的方法n 3 1 和基于人工智能口4 幅1 的方法。 1 2 1 基于运筹学的调度方法 基于运筹学n 刚的调度方法通常以寻求问题的最优解为目标，可以概括为在等式 约束或不等式约束条件下，对一个或者多个目标函数的优化，可以表示为混合整数 规划n l1 8 1 ( m i x e di n t e g e rl i n e a rp r o g r a m m i n g ，m i l p ) 或者混合整数非线性规划 ( m i x e di n t e g e rn o n l i n e a rp r o g r a m m i n g ，m i n l p ) 优化模型，采用各种数学规划方 法求解。求解步骤为：首先将调度问题描述为整数或混合整数规划等模型，然后采 用相应的数学工具n 钔( 如分支定界方法、动态规划方法和拉格朗日松弛方法等) 对 其进行求解。它们的共同特点是寻求调度特例的多项式时间最优或近优算法。但由 于该类方法的计算量一般随着调度问题规模的增大呈指数增加，搜索效率低。因此， 单纯采用该方法难以有效求解较大规模的制造过程调度问题。 1 2 2 基于启发式规则的调度方法 基于启发式规则的调度方法是根据一定的规则和策略来决定下一步操作的调 度方法。因其易于实现、计算复杂度低等特性，能够用于动态实时调度系统中，许 多年来一直受到学者们的广泛关注，并不断涌现出许多新的调度规则。常见的调度 规则包括加工时间最短规则、加工时间最长规则、交货期最早规则等。启发式规则 第一章绪论 利用不同的规则可产生不同的调度方案，而且规则在不同的场合所起的作用也不同， 调度系统的性能取决于规则的选择。因此，规则的选择成为基于规则调度方法的主 要障碍。启发式方法可分为基于调度规则( 也可以称为分派规则或优先规则等) 的 简单启发式方法和复杂启发式方法两种。启发式方法的优点是计算量小，适用于求 解实时调度问题；其缺点是当调度问题规模较大、约束较为复杂时，往往找不到全 局最优解。 1 2 3 仿真调度方法 在离散制造业中，由于其生产系统柔性较大，而且生产过程可完全由离散事件 仿真来模拟，因而，基于仿真的启发式调度方法较为常用。仿真调度方法是通过对 仿真模型的运行来模拟实际生产过程，并从中收集数据。然后运用这些数据对实际 系统进行性能和状态方面的分析，从而对系统采用合适的控制调度方法。应用仿真 方法调度能够在较短的实验时间内测试和分析不同调度决策的性能，进而选择较优 的调度决策。仿真调度方法可以解析模型无法描述的因素，但其也存在以下一些问 题：( 1 ) 仿真调度方法是通过仿真来模拟的调度方法，缺乏理论意义；( 2 ) 应用仿 真进行调度的费用很高；( 3 ) 仿真调度的准确性受编程人员的能力与主观因素影响。 1 2 4 人工智能方法 人工智能方法求解制造过程调度问题的研究兴起于2 0 世纪8 0 年代。是解决调 度问题的一种有效途径，已经成为了一个热门的研究课题。人工智能调度方法是基 于人工智能技术和人类调度专家经验对调度问题进行建模并求解的方法总称，主要 包括以下一些方法： 1 专家系统专家系统住基于系统当前的状态和给定的优化目标，通过对知识 库进行有效的搜索和模糊推理，从中选择最优的调度策略，为生产调度提供智能支 持。i s i s 是第一个旨在解决作业车间调度问题的调度专家系统。其优点是可以产生 复杂的启发式规则，利用定性和定量知识，具有智能性。但由于开发周期长、费用 昂贵、适应性差、所需的经验和知识难以获取且难以量化，因此调度专家系统常用 于相对稳定的系统，且往往与其他调度方法混合使用。 2 基于智能体的调度方法多智能体系统他2 1 是一种分布式的自主系统，它采用 广东工业大学硕士学位论文 基于协商的策略，能够在相同环境中采用不同的解决问题的方法，具有并行性、智 能性和柔性。智能体调度系统可以分为两大类智能体：任务智能体和资源智能体。 任务智能体负责处理调度中的各种任务类型，如物料运送、加工和监测等。资源智 能体负责单一或某一类资源。任务智能体将资源请求与资源应该进行的一系列操作 同时发送给相应的资源智能体，资源智能体接受到请求后，必须依据自己的性能指 标产生一个新的调度，然后根据结果决定是否接受这个请求。由于存在任务智能体 发送过来的请求没有资源智能体接受的可能性，因此，必须建立协作机制。然而到 目前为止还没有统一的规范来设计和实施协作。随着分布式调度越来月广泛，基于 智能体的调度技术也越来越受到重视。 3 约束规划约束规划是一种通过限制变量选取顺序和变量赋值顺序来减少搜 索空间的方法。约束规划可以把各种不同的算法包装成传播器，因而可以有效地用 于实施调度。基于约束规划的调度系统典型的有o p i s 产品族。约束规划方法由于考 虑多种约束，所以求解代价和难度比较大。 4 基于神经网络的方法神经网络模仿了人类学习和对事物的预测能力，是一 种并行处理模型。这种模型根据网络拓扑结构、节点特征和训练或学习规则的不同 而变化。神经网络由大量的处理单元以适当的方式互连构成，是一个大规模的非线 性自适应系统。它的主要思路是：通过一个l y a p l m o v 能量函数构造网络的极值， 当网络迭代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。 神经网络具有一定的自学习能力，且容错性好，但神经网络存在学习效率比较差、 计算速度速度比较慢、计算精度不高、难以表达符号知识以及其它知识等缺点哺1 。 5 遗传算法遗传算法是基于自然选择和群体自然遗传进化模型的并行优化 搜索方法，其优化过程模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变 现象。遗传算法对求解的问题本身一无所知，它仅是对算法所产生的每个染色体进 行评价，并根据适应性进行选择，使适应性好的染色体有更多的繁殖机会，以能够 更快速的达到问题的较优解。使用遗传算法求解生产调度问题的主要工作有：生产 问题到遗传编码的转换、字符串操作符的选择和限制搜索空间的约束描述等。它的 最大优点是利用群体间的相互作用，保持已经搜索到的信息。但是遗传算法也存在 计算速度较慢和早熟的问题。 6 模拟退火算法模拟退火算法陵钔是源于对热力学中退火过程的模拟，从8 0 年代起开始应用于优化领域，可以求解大规模组合优化问题，是当前较为成功、应 第一章绪论 用较广的全局优化算法。在某一给定初温下，通过缓慢下降温度参数，使算法能够 在多项式时间内给出一个近似最优解。模拟退火算法是一种通用的随机搜索算法， 是对局部搜索算法的扩展。但由于模拟退火算法要求具备足够高的初温和足够慢的 降温速度，才可能收敛到全局最优解，是一种计算效率比较低的串行优化算法，所 以一般都要对它加以改进。 7 禁忌搜索算法禁忌搜索从一个可行解开始逐步移向一个最优解或次优解， 在每次移动前，需要依据某种与问题有关的规则搜索现行解周围的相邻解集，然后 评估每一个相邻解。有些移动由于会导致问题的解陷入局部最优或导致循环，因此 这些移动是被禁止的，将这些被禁止的移动加入禁忌表。一般而言，禁忌表的长度 影响搜索的质量，禁忌表的长度越长，则搜索陷入局部最优的可能性越小。但是， 禁忌表的长度越长，计算扫描的时间也越长，因而会加大算法的求解时间，并且在 每次迭代中限制了搜索空间。最合适的长度与问题有关，但到目前为止还没有确定 长度的规则可循。禁忌搜索算法的搜索性能完全依赖于邻域结构和初始解。 综上所述，调度研究至今尚未形成一套系统的理论和方法，理论研究与实际应 用之间也还存在着很大的差距。实际应用中的一些调度方法能够响应系统的动态变 化，但不能保证得到好的调度，因此，探索有效求解作业车间生产调度问题的优化 算法，便成为本课题的研究目标。 表1 - 1 生产调度问题的各种求解算法及特点 t a b l e1 - 1a l g o r i t h m sa n dt h e i rf e a t u r e sf o rj s p 第一章绪论 1 3作业车间调度问题 作业车间调度问题( 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 ) 是一个典型的n ph a r d 问题，是许多实际问题的简化模型，例如加工制造、v l s i 设计、电气布线、网络通 信、交通规划等问题n 引。车间生产调度是制造系统的基础，主要是针对确定数量的 工序及固定的机器，探讨在满足约束条件的情况下，使得某些性能如加工时间、制 造成本的最优化。 1 3 1 问题描述 作业车间调度问题是一类满足任务配置和顺序约束要求的资源分配问题，是组 合优化领域内的难点。资源和任务分别是一些机器和作业。作业可由若干称为操作 的子任务组成。作业车间调度可以简单概括为：有聆个相互独立的工件要在m 台机 器上进行加工，每个工件需要经过m 道工序，每道工序的加工机器不同，每道工序 所需的加工时间给定，分别为兀( f = l ，2 ，聊) ；各工件在机器上的加工次序约束也是 给定的；问题的目标是确定甩个工件在每台机器上的最优加工顺序，使某些加工性 能指标达到最优。以工件完工时间最小作为目标，对该问题的假设为：( 1 ) 操作的 执行次序遵循严格的串行顺序；( 2 ) 在特定时间，每个操作需要一台特定机器完成； ( 3 ) 工序一旦进行不能中断；( 4 ) 每台机器在同一时候不能同时完成不同的工作； ( 5 ) 同一时候，同一工作的各个操作不能并发执行。( 6 ) 问题是求从第一个操作开 始到最后一个操作结束的最小时间间隔( m a k e s p a n ) 啪1 。 1 3 2 问题特性 作业车间调度是车间调度问题的一种更为具体的形式，因此它具有车间调度的 一般特性： 1 复杂性生产环境的复杂性与优化计算的复杂性是作业车间调度问题复杂性 的主要表现。生产环境的复杂性在于车间中工件、机器和搬运系统之间相互影响、 相互作用。每个工件的加工时问、安装时间和操作顺序等因素会不断地改变。优化 计算的复杂性在于：调度问题的优化性能指标，往往包含着等式或不等式等复杂约 束，在计算量上往往是n p ( 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 ) 完全问题。并且随着问 题规模的增大，其计算量急剧增加，常规的方法根本无法求解这种问题，对于这