（计算机应用技术专业论文）调整时间与工序顺序相关的车间作业调度算法.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 研究生签名：益查丕 日 期：丛! 竺：丝! ； 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：渣生丕导师签名： 摘要 摘要 调整时间与工序顺序相关的车间作业调度问题( s d s t - j s p ) 广泛存在于制造工业中，如纺织、 半导体生产等。由于其比经典车间作业调度问题( j s p ) 能更好地建模实际生产调度，故具有非常重 要的实际应用价值。 本文在分别改进遗传算法和禁忌搜索算法的基础上，提出将两者相结合的混合算法g a + t s 。设 计启发式算法与随机算法相结合的初始解生成策略，以保持种群的优良性和多样性；构造新的交叉 算子( r o x ) ，以有效保存父代的优良基因；提出具有扰动因子的解码算法( r g & t ) ，在生成活跃 调度的基础上，扩大算法搜索空间；构造新的启发式算法( b i d i r s 和l i s t s ) ，为禁忌搜索算法提供 较好的初始解：提出五种新的邻域结构，有效地增强算法的局部搜索能力；采用禁忌表动态变长策 略，提高对解空间有效搜索：采用短期记忆和长期记忆相结合的策略，以充分利用搜索历史信息， 避免循环搜索，从而扩大算法对解空间的覆盖率；提出遗传算法与禁忌搜索算法相结合的混合启发 式算法，通过加强遗传算法局部搜索能力，提高禁忌搜索算法初始解的多样性，从而提高算法总体 性能。 通过基于b t 标准的测试实例，将g a + t s 与目前最好的两个算法s b + g l s 和g a + l s 进行比较。 实验结果表明所提算法在相对误差方面要优于其它两个算法，故能有效地解决s d s t - j s p 问题。 关键字：调整时间；车间作业调度；遗传算法；禁忌搜索 a b s t r a c t a b s t r a c t t h ej o bs h o ps c h e d u l i n gp r o b l e mw i t hs e q u e n c ed e p e n d e n ts e t u pt i m e s ( s d s t - j s p ) w i d e l ye x i s t si n m a n u f a c t u r i n ge n t e r p r i s e s ，s u c ha st e x t i l e s ，s e m i c o n d u c t o rp r o d u c t i o na n ds oo n s d s t - j s ph a sv e r y i m p o r t a n tp r a c t i c a la p p l i c a t i o nv a l u ea si tm o d e l sa c t u a lp r o d u c t i o ns c h e d u l i n gb e t t e rt h a nj s p a f t e rag e n e t i ca l g o r i t h m ( g a ) a n dat a b us e a r c h ( t s ) b e i n gi m p r o v e d ，an e wh y b r i da l g o r i t h m g a + t si sp r o p o s e d f o rg a an e wi n i t i a lp o p u l a t i o ng e n e r a t i o ns t r a t e g yi si n t r o d u c e dw h i c hc o m b i n e sa h e u r i s t i ca l g o r i t h mw i t har a n d o m i z a t i o nm e t h o dt oi m p r o v et h eq u a l i t ya n dd i v e r s i f i c a t i o no ft h ei n i t a l p o p u l a t i o n an e wc r o s s o v e ro p e r a t o r ( r o x ) i sc o n s t r u c t e dt op a s se l i t eg e n e so fp a r e n t st oo f f s p r i n g e f f e c t i v e l y ad e c o d ea l g o r i t h m ( r g & t ) w i t had i s t u r b a n c ef a c t o ri sp r e s e n t e dt ob u i l da c t i v es c h e d u l e sa n d e x t e n dt h es e a r c hf i e l d s f o rt s ，t h en e wh e u r i s t i ca l g o r i t h m s ( b i d i r sa n dl i s t s ) a r ed e v e l o p e df o r g e n e r a t i n gs o m eg o o di n i t i a ls o l u t i o n s f i v en e wn e i r g h b o r h o o ds t r u c t u r e sa r ei n v e s t i g a t e dt oi m p r o v et h e c a p a b i l i t yo fl o c a ls e a r c h d y n a m i ct a b ul i s ti sa d o p t e dt os e a r c h9 0 0 ds o l u t i o n s as t r a t e g yt h a tc o m b i n e s s h o r tt e r mi n f o r m a t i o nw i t hl o n gt e r mi n f o r m a t i o ni sd e s i g n e dt om a k ef u l lu s eo ft h es e a r c h i n gh i s t o r yi n o r d e rt oa v o i dr e p e a t i n gs e a r c h e sa n de x p a n dt h es e a r c hs p a c e ah y b r i da l g o r i t h mt h a tc o m b i n e sg e n e t i c a l g o r i t h mw i t ht a b us e a r c ha l g o r i t h mi sp u tf o r w a r dt oi m p r o v et h el o c a ls e a r c ha b i l i t yo fg aa n dt o d i v e r s i f yt h ei n i t i a ls o l u t i o no f t ss oa st oe n h a n c et h eo v e m l lp e r f o r m a n c eo f t h ea l g o r i t h m b a s e do nt h el5b e n c h m a r ki n s t a n c e so fb t g a + t si sc o m p a r e dw i t ht h e b e s tt w oe x i s t i n g a l g o r i t h m s ，w h i c ha let h es h i f t i n gb o t t l e n e c ka l g o r i t h mw i t hg u i d e dl o c a ls e a r c h ( s b + g l s ) a n dt h eg e n e t i c a l g o r i t h mh y b r i d i z e dw i t hl o c a ls e a r c h ( g a + l s ) e x p e r i m e n t a lr e s u l t ss h o wt h a tg a + t so u t p e r f o r m st h e o t h e rt w oo nr e l a t i v ee r r o r ( r e ) ，w h i c hi m p l i e st h a tt h ei tc a ns o l v es d s t j s pm o r ee f f e c t i v e l y k e y w o r d s ：s e t u pt i m e s ；j o bs h o ps c h e d u l i n g ；g e n e t i ca l g o r i t h m ；t a b us e a r c h i i 目录 目录 摘要i a b s t r a c t i i 目录1 i i 第l 章绪论1 1 1 车间作业调度问题l 1 1 1 课题背景1 1 1 2 车间作业调度问题的特点2 1 1 3s d s t - j s p 问题的求解方法2 1 2s d s t - j s p 问题的研究现状4 1 3 论文主要内容6 1 4 论文结构6 第2 章适用于s d s t - j s p 问题的遗传算法7 2 1s d s t - j s p 问题描述7 2 1 1 相关定义7 2 1 2s d s t - j s p 问题的数学模型7 2 1 3s d s t - j s p 问题的有向图表示8 2 2 适用于求解s d s t - j s p 问题的遗传算法l o 2 2 1 初始解的生成10 2 2 2 编码与解码1 l 2 2 - 3 适应度1 2 2 2 4 交叉算子1 3 2 2 5 选择算子1 4 2 2 6 变异算子15 2 3 算法比较与分析。1 5 2 3 1 常用的测试实例1 5 2 3 2 比较与分析1 6 2 4 本章小结1 7 第3 章改进的禁忌搜索算法1 8 3 1 改进的禁忌搜索算法。1 8 3 1 1 初始解的生成1 8 3 1 2 邻域结构18 3 1 3 总完工时间的估算一2 2 3 1 4 禁忌表的设计2 3 3 1 5 特赦准则2 4 3 1 6 循环检测2 4 3 1 7 终止准则2 4 3 2 带长期记忆的搜索策略2 5 3 3 算法比较与分析2 6 3 4 本章小结3 0 i l i 第4 章求解s d s t - j s p 问题的混合算法3 1 4 1 求解s d s t - j s p 问题的混合算法3l 4 2 算法比较与分析3 3 4 3 本章小结3 5 结论3 6 致谢3 7 参考文献3 8 攻读硕士学位期间发表的学术论文4 0 i v 第1 章绪论 第1 章绪论 1 1 车间作业调度问题 1 1 1 课题背景 车间作业调度问题源于加工制造业。加工制造业中常遇到的情况是用一组机器对若 干个工件进行加工。一个工件在某台机器上的加工称为一道工序。通常一个工件包括若 干道工序，这些工序的先后顺序事先确定，称为工件的工艺加工过程。所谓调度，是指 合理安排机器对工件的加工时间和加工顺序，使得预期目标达到最优。有关资料表明， 制造过程中9 5 的时间消耗在非切削过程中，故有效的调度方法与优化计划的研究应 用，已成为先进制造技术( a m t ) 的关键。 调度问题按照不同的分类标准，有不同的分类方式l l 硼，常用的分类方法包括按照 机器、任务和目标函数的特征分类。 按机器的种类和数量不同，可以分为单机调度问题和多机调度问题。对于多机调度 问题，按照加工路线的不同特征，可分为流水调度( f l o ws h o p ) 问题和车间作业调度 ( j o bs h o p ) 问题。流水调度问题的基本特征是所有工件的加工路线完全相同；而车间 作业调度问题的基本特征是每个工件的加工路线不一定相同。 按任务到达车间的情况不同，可以分为静态调度问题和动态调度问题。静态调度问 题是指所有工件都已到达车间，可以一次安排它们的加工顺序；动态调度问题是指工件 陆续到达车间，要随时安排它们的加工顺序。 按目标函数的不同，也可以分为多种不同的调度问题。譬如，同为单机调度问题， 最小化总完工时间( t o t a lf l o w t i m e ) 和最小化最大完工时间( m a k e s p a n ) 就是两类不 同的问题。总完工时间最小可以促使资源稳定有效地利用、任务快速周转及在制品库存 最小；最大完工时间最小则能减少总的生产周转时间。 按照参数的性质不同，可以分为加工时间和其他相关参数为确定常量的确定型调度 问题和加工时间和其他相关参数为随机变量的非确定型调度问题( 随机型调度问题) ， 这两种调度问题在解决方法上有着实质性的差别。 按生产需求不同【2 】，可以分为没有库存储备、需求仅由下货单产生的开放车间( o p e n s h o p ) 调度和需求受到库存储备限制的封闭车间( c l o s e ds h o p ) 调度问题。 车间作业调度问题可表述为：多个工件( 两个或两个以上) 在若干机器( 一台或多 台) 上加工时，确定各台机器上工件加工顺序，以达到最优的预定目标。预定目标可为 调度性能，如生产周期、平均流动时间等；也可为调度成本，如在线库存费用、加工费 用等；或用户指定指标，如最大拖期时间、平均拖期时间、拖期零件的数量等。 车间作业调度问题是著名的n p 难问题，一个典型的例子是由f i s h 和t h o m p s o n 5 l 于1 9 6 3 年提出的1 0 x 1 0 的实例直到1 9 8 9 年才得到解答。由于这类问题的复杂性，对于 调整时间与工序顺序相关的车间作业调度问题( s e q u e n c ed e p e n d e n ts e t u pt i m e sj o b s h o pp r o b l e m ，s d s t - j s p ) ，大量的研究都作了简化：如假设调整时间相对于加工时间 东南大学硕士学位论文 非常小，可以忽略不计；或者认为调整时间与加工顺序无关，可以包含在加工时间中。 然而，当工序调整时间占有相当比例，或者调整时间的长短取决于相关工序的顺序时， 调整时间就不能忽略。在某些情况下，工序的调整时间与该机器的上道工序有关。如纺 织企业中的染色工序，当从浅色产品到深色产品连续染色时，通常只要求一个相对较小 的调整时间，而当深色产品到浅色产品连续染色时，由于机器需要清洗，需要一个较长 的调整时间【6 】。由于调整时间与工序顺序相关的车间作业调度问题能更好的建模实际生 产情况，故具有非常重要的实际应用价值。 1 1 2 车间作业调度问题的特点 ( 1 ) 复杂性 由于车间中工件、机器、缓存和搬运系统之间的相互影响和相互作用，每个工件同 时要考虑其加工时间、调整时间和操作顺序等因素，因而相当复杂。调度问题是在等式 或不等式约束下求解性能指标的优化，在计算上往往属于n p 难问题，随着问题规模的 增大，其计算量呈指数增长，因此往往很难求得最优解，通常是寻求其近似最优解。 ( 2 ) 复杂性动态随机性 在实际的车间作业调度中存在很多随机性和不确定因素，如工件到达时间的不确定 性、工件加工时间也存在一定的随机性，加上实际车间环境中出现的一些突发偶然事件， 如机器故障、产品交货期的改变、人员误操作等不可预见因素，车间作业调度需要根据 生产情况做出动态调整。 ( 3 ) 多目标 实际的车间作业调度往往是多目标的，并且这些目标可能相互冲突。生产调度的性 能指标可以是库存最小、成本最低、生产周期最短、生产切换最少、设备利用率最高、 延迟最短、拖期惩罚最小等。 ( 4 ) 多约束性 生产车间中资源的数量、缓存的容量、工件的加工时间和加工顺序等都是约束条件。 此外还有一些其他的约束，如要求各机器上的负载要平衡等。 1 1 3s d s t - j s p 问题的求解方法 本文研究的s d s t - j s p 问题是经典j s p 问题的延伸，可参考经典j s p 问题的求解方 法，并在其基础上针对有调整时间的约束条件进行改进，以设计出适合该问题的求解方 法。 车间作业调度问题一般都是对于生产环境中动态的、多目标的、复杂的调度问题的 简化和抽象，属于n p 完全问题，问题规模较大时难以求得其最优解。一个好的近似解 在一定程度上也能满足实际需求，故目前大多考虑在有限时间内获取问题的近似最优 解。一般而言，求解车间作业调度问题的方法可分为精确算法和近似算法，近似算法又 包括启发式方法和元启发式方法两大类。 ( 1 ) 精确算法 精确算法建立在数学规划基础上，将生产调度问题简化为数学规划问题，主要包括 2 第1 章绪论 数学规划法、分枝定界法、动态规划法等。它适用于问题规模较小的情况，当问题规模 较大时，由于时间复杂性太高，精确算法往往在有限的时间内不能得出运算结果。对于 大规模问题，可以采用启发式算法或元启发式算法，求解其近似最优解。 ( 2 ) 启发式算法 启发式算法( h e u r i s t i c ) 是指针对某个特定问题的性质和目标函数，设计或选用有 效的调度规则以获取近似最优解。调度规则大体分为三类：简单规则、复合规则和启发 式规则。简单规则有三十多条，如先进先出( f i r s ti nf i r s to u t ，f i f o ) 、最短处理时间 ( s h o r t e s tp r o c e s s i n gt i m e ， s p t ) 等，另两种规则是简单规则的多样性组合。 启发式算法的优点是采用了贪心策略以减少搜索空间，从而可以快速给出质量较高 的近似最优解；缺点是只适用于问题规模较小的情况。对于较大规模问题的求解或者对 近似解的质量要求更高时，可使用元启发式算法。 ( 3 ) 元启发式算法 元启发式算法( m e t a - h e u r i s t i c s ) 是指以迭代求精法为核心思想的新启发式搜索算法， 能克服传统启发式算法易陷入局部最优解的不足，在性能方面相比启发式算法有了很大 的提高，但是以增加搜索空间提高时间开销为代价的。目前常用的元启发式算法主要包 括：遗传算法【7 1 、禁忌搜索算法【8 1 、模拟退火算法【9 1 、人工神经网络算法 1 0 1 等。不同的 算法有各自的优势和适用领域。本节将对遗传算法和禁忌搜索算法的基本思想进行简要 的介绍。 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是由h o l l a i l d 【7 1 根据生物进化论中“优胜劣汰、 适者生存 的基本思想于1 9 7 5 年提出的一种算法。遗传算法的运算对象是由m 个个体 所组成的集合，称为种群。与生物一代一代的自然进化过程相类似，遗传算法的运算过 程也是一个反复迭代的过程，第，代种群记做p ( t ) ，经过一代遗传和进化后，得到第t + l 代种群，它们也是由m 个个体组成的集合，记做p 0 + 1 ) 。生物的进化过程主要是通过 染色体之间的交叉和染色体的变异完成的。与此相对应，遗传算法中最优解的搜索过程 也模仿生物的进化过程，使用遗传算子作用于种群p ( f ) 中，进行下述遗传操作，从而得 到新一代种群p ( t + 1 1 。 选择：根据各个个体的适应度，按照一定的规则或方法，从第，代种群p ( f ) 中选 择出一些优良的个体遗传到下一代种群尸( ，+ 1 ) 中。 交叉：将种群p ( ，) 内的各个个体随机搭配成对，对每一个个体，以某概率( 称 为交叉概率) 交换它们之间的部分染色体。 变异：对种群p ( t ) 中的每一个个体，以某一概率( 称为变异概率) 改变某一个 或某一些基因座上的基因值为其他的等位基因。 标准遗传算法基本步骤如下： 1 进化迭代数f 卜o ，最大进化代数卜丁，随机生成m 个个体作为初始种群尸( 0 ) ； 2 计算种群尸( f ) 中各个个体的适应度； 东南大学硕士学位论文 3 种群p ( f ) 经过选择，交叉，变异运算之后得到下一代种群p ( t + 1 ) ； 4 若t t ，f 卜f + 1 ，转2 ； 5 若t 丁，则算法停止，输出最优解。 禁忌搜索算法 禁忌搜索( t a b us e a r c h ，t s ) 算法是由g l o v e r t 8 】于1 9 8 6 年首次提出，其是局部邻 域搜索算法的推广，是人工智能在组合优化算法中的一个成功的应用。禁忌搜索算法最 主要的特点是采用了禁忌技术，所谓禁忌技术就是禁止重复前面的工作。为了改进局部 邻域搜索算法容易陷入局部最优解的不足，禁忌搜索算法采用一个禁忌表记录已到达过 的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或者有选择地搜索这些点， 以此跳出局部最优点，从而保证对不同有效搜索路径的搜索。禁忌搜索算法主要涉及邻 域结构、禁忌表、候选解、特赦准则和终止准则等概念。组合优化问题是禁忌搜索算法 应用最多的领域，如旅行商问题、调度问题等。 标准禁忌搜索算法的基本步骤是： 1 给定一个初始可行解x 一以及禁忌表t = 由； 2 若满足停止准则，则算法结束； 3 根据邻域结构，找出当前解x 一的邻居解n ( x ) ； 4 将n ( x ) 中任一满足特赦准则的解x 删作为当前解，即x ”卜x “，更新禁忌表， 转2 ； 5 将( 工一) 中未被禁忌且评价值最佳的解x 删作为当前解，即x 一卜x “，更新禁 忌表，转2 。 可见邻域结构、禁忌表、特赦准则和终止准则等构成了禁忌搜索算法的关键。其中， 邻域结构沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表体现了避免迂回搜索的 特点；特赦准则可避免禁忌优良解；终止准则指明算法停止的条件。 综上所述，精确算法适用于求解小规模问题的最优值，由于时间复杂度较高，不适 用于稍大规模问题的求解；启发式算法根据启发式规则，运用贪心策略，能有效地减少 搜索空间，在很大程度上提高算法效率，在相对较短的时间内得到近似最优解；元启发 式算法则基于迭代操作思想，其性能较启发式算法有较大的提高，但是以更大时间开销 为代价。所以如何协调启发式算法和元启发式算法，使之在尽可能短的时间内求得尽可 能好的解，是目前车间作业调度理论领域研究的热点问题。 1 2s d s t - j s p 问题的研究现状 s d s t - j s p 问题作为车间作业调度问题的延伸，早在4 0 多年前已经提出，但是直到 上世纪9 0 年代才得到广泛关注。根据s d s t - j s p 问题研究方法的不同，本节从精确算法、 启发式算法和元启发式算法三个方面分别介绍s d s t - j s p 问题的研究现状。 ( 1 ) 精确算法 目前求解s d s t - j s p 问题的精确算法都是基于分枝定界法，代表算法有f l n 1 1 】算法、 b t 1 2 1 算法、a b f 1 3 1 算法和a f t l 4 1 算法。 4 第l 章绪论 f o c a c c i 【1 1 】等针对具有可选资源的s d s t - j s p 问题，提出一种分枝定界法，用于求解 该问题的各种变换。b r u c k e r 和t h i e l e l l 2 1 扩展他们之前提出的针对经典j s p 问题的算法 【l 引，提出适用于一般j s p 问题的分枝定界法，s d s t - j s p 问题是其中的一个特例。并且 他们提出后来被广泛使用的1 5 个基准测试实例t 2 p s o l - t 2 p s l 5 ，这些测试实例是在 l a 、m n c e 【l6 j 针对经典j s p 问题提出的l a 0 1 1 5 实例的基础上，加入调整时间扩展而来的。 目前求解s d s t - j s p 问题效果最好的精确算法是由a r t i g u e s 和f e i l l e t l 4 】提出的精确算 法，该算法采用求解带有时间窗口的旅行商问题的优先权规则得到可行解，其能求出 b t 测试集中的8 个最优解，而f a c a c c i ，b r u c k e r 和t h i e l t e 等提出的算法只能找到其中 最小5 个实例的最优解，并且该算法改进了8 个实例的最优下界和其他3 个实例的最优 上界。 ( 2 ) 启发式算法 w i l b r e c h 和p r e s c o t t 1 7 j 是最早研究s d s t - j s p 问题的，他们提出一种优先权规则：当机 器空闲时，选择需要最小调整时间的工件。k i m 和b o b r o w s h 【1 8 j 研究依赖工序顺序的调整 时间对不同性能指标的影响，并提出复合词优先规则。n o i v o 和r a m a l h i n h o l o u r e n c 0 19 1 在考虑调整时间的基础上提出一种新的优先权规则并和经典的优先权规则进行了比较。 m 6 n c h l 2 0 j 等对复杂的车间作业调度问题提出一种改进的移动瓶颈启发式算法，其考虑的 车间环境包括s d s t - j s p 问题，结果证明该算法可以极大地提高求解结果。b r u c k e r 1 5 】等 在g & t t 2 1 i 算法的基础上加入了调整时间的约束，提出一种新的优先权规则，并将其用于 他们的精确算法中。a r t i g u e s l 2 2 】等提出一些新的优先权规则，并将它们用于不同的调度 产生算法( s g s ) 。这些s g s 算法是非确定性的算法，即在有多个可选工序的情况下，其 优先权规则会做出非确定性选择。 ( 3 ) 元启发式算法 s c h m i d t l 2 3 1 改进了d e l l a m i c o t 2 4 】等提出的求解经典j s p 问题的禁忌搜索算法，并用 其求解s d s t - j s p 问题，取得了较好的结果。b a l s a 2 5 】等针对s d s t - j s p 问题，提出移动 瓶颈算法结合带引导的局部搜索算法的混合算法，并将单机调度问题转为化带有时间窗 口的旅行商问题。v e l a t 2 6 1 等提出用遗传算法结合局部搜索算法的混合算法，并提出针对 s d s t - j s p 问题的6 条推论及3 个邻域结构。c h o i l 2 7 】等用遗传算法结合启发式搜索，解 决可选机器的s d s t - j s p 问题。c h e u n g 和z h o u 【2 8 】将遗传算法结合处理时间最小和剩余 任务最大的两种启发式规则求解s d s t - j s p 问题，并将其用于评价函数。实验证明他们 的算法优于c h o i 和k o r k m a z t 2 9 】的算法。g o n z , 乱e z l 3 0 】等改进用于求解经典j s p 问题的遗 传算法和简单的局部搜索算法，并将两者结合成新的混合算法，实验证明他们的算法优 于c h u e n g 和z h o u t 蹦j 的算法。 针对目前研究情况，有如下问题亟待改进： ( 1 ) 目前求解s d s t - j s p 问题主要采用启发式算法和元启发式算法。启发式算法计 算时间较少，但算法性能通常较差；元启发式算法的性能较好，但所需计算时间相对启 发式算法较长。故需将启发式算法与元启发式算法相结合，充分发挥两者的优势。常用 策略是先用启发式算法生成一个近似最优解作为元启发式算法的初始解，然后对这个初 东南大学硕士学位论文 始解进一步迭代计算以获得更好的解。 ( 2 ) 由于不同的元启发式算法都有其各自的优势和不足，如何将不同的元启发式算 法结合，以提高其总体性能是当前调度理论研究的一个趋势。 1 3 论文主要内容 论文的主要内容如下： ( 1 ) 提出改进的遗传算法求解s d s t - j s p 问题：在初始种群的生成过程中，采用改 进的双向表调度算法生成一定比例的优良初始个体，并在选择操作时择优保存，保证遗 传算法在一个较好解的基础上进行不断地改进；提出新的交叉算子，在保证继承双亲优 良基因的基础上，更大程度地提高种群的多样性。 ( 2 ) 提出改进的禁忌搜索算法求解s d s t - j s p 问题：提出新的初始解生成算法，为 禁忌搜索算法提供较优的初始解；提出五种适用于s d s t - j s p 问题的邻域结构，以提高 对问题空间搜索范围；提出短期记忆与长期记忆相结合的搜索策略，以充分利用搜索的 历史信息，从而有效避免重复搜索提高全局解的质量。 ( 3 ) 采用遗传算法与禁忌搜索算法相结合的思想，先用遗传算法进行全局搜索，使 种群个体分布在解空间的大部分区域，再用禁忌搜索算法对种群中每一个个体进行局部 搜索，从而有效地结合遗传算法并行的大规模搜索能力和禁忌搜索算法的局部搜索能 力，提高算法的整体性能。 1 4 论文结构 第l 章主要介绍车间作业调度问题的相关理论，车间作业调度问题的特点和研究方 法，结合目前研究现状给出本文主要研究内容。 第2 章给出s d s t o j s p 的问题描述，设计适合该问题的遗传算法，遗传算法的设计 包括初始种群的生成、解码算法、选择算子、交叉算子等。 第3 章设计适合s d s t - j s p 问题的禁忌搜索算法，禁忌搜索算法的设计包括初始解 生成、邻域结构、禁忌表、循环检测等，并提出短期记忆和长期记忆相结合的搜索策略。 第4 章设计结合遗传算法和禁忌搜索算法机制的混合算法，并与目前最好的两个算 法进行性能比较。 6 第2 章适用于s d s t - j s p 问题的遗传算法 第2 章适用于s d s t j s p 问题的遗传算法 2 1s d s t - j s p 问题描述 2 1 1 相关定义 调整时间与工序顺序相关的车间作业调度问题的定义如下：给定m 台机器 m ，鸩，心和n 个工件q ，巴，见；每个工件q 有m 道给定先后加工次序的工序 e2 q 。，b ：，) ，工序乞表示工件q 的第歹道工序，i = l ，棚，j = 1 ，m ；工序b ，在 机器。上加工，。 m ，心) ，加工时间为岛对于同一台机器上连续加工的两 道工序吼和有一个调整时间岛。，钆，如果吃在之前加工，那么在吃加工结束到加 工之前就必须有一个时间间隔& 以( & 。表示机器蚝的第一道工序加工前的准备 时间，s j 表示在机器鸩的最后一道工序加工后的清理时间) ，在此期间不能加工其 他任何工序；工序嘭有一个开始时间s 乃。和一个完工时间q ，其中q = 踢，+ 岛，；c 槭 为全部工件的完工时间，o = m a x g 。) ( f = 1 ，刀，j = 1 ，m ) 表示调度的最大完工时间 ( m a k e s p a n ) 。 s d s t - j s p 问题有如下假设： ( 1 ) 在f = 0 时刻可使用全部机器，且工件毛坯全部到达； ( 2 ) 已知工件每道工序的加工时间； ( 3 ) 一台机器在同一时间只胄匕力n i - - 个工件； ( 4 ) 一个工件同一时间只能在一台机器上加工； ( 5 ) 某道工序的加工一旦开始，就不能中途停止； ( 6 ) 工序在机器上加工前有一个调整时间，并且该调整时间和该机器加工的上一道 工序有关； ( 7 ) 每台机器在加工第一道工序前有一个准备时间，在加工完最后一道工序后有一 个清理时间。 s d s t - j s p 问题可表示为在满足如上定义和假设的情况下，求解调度的最小化最大 完工时间。对于s d s t - j s p 问题的描述，本文主要采用了数学模型及有向图两种表示方 式。 2 1 2s d s t - j s p 问题的数学模型 ( p ) m i nc 懈 满足条件： ( 1 ) s v o m 。，- c o “，i = 1 ，刀，= 1 ，m - 1 ； ( 2 ) c 麟g 。，i = l ，玎； ( 3 ) s 乃h + ( 1 一x e 。，) m g ，+ 品，鸠，= m o 。，m 为一个很大的正数。 7 东南大学硕士学位论文 其中： s 乃。= m a x c 日k u - 1 ) ，g ，+ & ，岛) ，= 村，。，2 l ； w 亿署翩旺聃邻 ” 踢。o ，f = 1 ，甩，j = 1 ，m 。 问题( p ) 的一个可行解称为一个调度。约束条件( 1 ) 表示，每个工件必须遵循特 定的工艺路线；约束条件( 2 ) 进一步定义了最大完工时间c 腿；约束条件( 3 ) 给出在 某台机器上连续加工的两道工序的时间约束，即强调每台机器在同一时间只能加工一道 工序。 2 1 3s d s t - j s p 问题的有向图表示 为了更加直观的表示j s p 问题，一种有效的方法是用有向图来表示，其最经典的是 由b a l a s 3 1 1 提出的析取图( d i s j u n c t i v eg r a p h ) 。本文用类似于z o n g h b y t 3 2 1 等提出的方法， 在经典析取图上加入调整时间，从而更加直观的表示s d s t - j s p 问题。析取图中结点对 应工序；边有两种类型，一种是有向边( c o n j u n c t i v ee d g e ) ，种是分离边( d i s j u n c t i v e e d g e ) 。有向边连接的结点对应的是同一个工件的两个相邻工序，表示工序在工件中的 优先关系，是已知的；分离边是一对反向边，分离边连接的结点对应在同一台机器上处 理两道工序，它们之间的先后关系是未知的，需要用调度算法求出。 s d s t - j s p 问题可表示为g = ( y ，a u e u ，) ，其中y 表示所有工序的集合，并且包括 两个虚结点s t a r t 和e n d ，分别表示开始工序和结束工序，其处理时间都为0 ；彳为有向 边集合，有向边( v ，w ) 权重为工序v 的处理时间；e 为分离边集合，可分解成子集e ( e = u 脚。巨) ，表示机器m 上所有分离边的集合，分离边( ，w ) 权重为仇+ 瓯，；j 包含了所有边( s t a r t ，v ) 和( v ，e n d ) ，其权重分别为瓯，和风+ 鼠o ，1 ，v 。 一个可行解可表示为g 的一个无环子图g ，g = ( y ，a u h u j ) 。其中h = u 乩胛e ， 鼠为互的一个汉密尔顿选择，表示相同机器上所有工件的处理顺序；j 包含了所有的 边( s t a r t ，v ) 和( w ，e n d ) ，i = l ，历， i 和嵋分别表示e 中第一个和最后一道工序。故求 解s d s t - j s p 问题的一个可行调度，可简化为求解g 的一个无环子图g 。问题也可描述 为寻找一个可行的处理序列，使得p 最长路径( 即关键路径) 最小。关键路径为从s t a r t 到e n d 的最长路径，处于关键路径上的点和边都是关键的，可把关键路径分解为若干关 键块8 9 oo ，耳，用于指示位于关键路径上被同一台机器加工的最大相邻工序集。 在一个可行解对应的有向图q 中，头凡表示从s t a r t 到v 的最长距离，尾吼表示从1 ， 到e n d 的最长距离，因此从s t a r t 到e n d 经过v 的最长距离可以表示为匕+ a + 吼。当v 在 关键路径上时，其值为最大完工时间。任何工序v 都有两个直接前驱和两个直接后继， 即工件前驱矾和工件后续豇，以及机器前驱p m ，和机器后续s m , 。 8 第2 章适用于s d s t - j s p 问题的遗传算法 表2 1 给出3 个工件在3 台机器上加工的一个s d s t - j s p 问题实例，每个工件都有 3 道工序，总共9 道工序。 表2 - 13 个工件、3 台机器的实例 工序之间的调整时间用如下矩阵s 表示，矩阵大小为1 0 x 1 0 ，矩阵元素| s ：f 表示工序f 到工序，所需的调整时间，s o ，表示工序为某台机器上的第一道工序时的准备时间，s 。 表示工序i 为某台机器上的最后一道工序时，机器所需要的清理时间。 ，”一_ 、 j 多磐廿挚哆研3 玉k 毪一 乜彝峦再囚：m 9 东南大学硕士学位论文 2 2 适用于求解s d s t - j s p 问题的遗传算法 本节从初始解的生成，染色体的编、解码和遗传算子( 包括选择、交叉和变异) 等 环节介绍求解s d s t - j s p 问题的遗传算法，并提出改进的遗传算法i g a 。以下详细说明。 2 2 1 初始解的生成 遗传算法是从多个解组成的初始种群开始并行搜索，初始种群的设计对遗传算法的 性能至关重要。初始种群保持多样性，可使遗传算法在进行并行搜索时覆盖更多的解空 间，从而有效避免过早收敛。但如果种群过度随机化，遗传算法则更趋向于随机搜索， 难以保证解的质量。 i g a 初始解生成策略如下：用启发式算法生成前1 0 的初始解，随机生成后9 0 的 初始解。这种做的好处是：一方面用启发式算法生成较好的初始解，让遗传算法基于较 好的初始解进行迭代进化，以求得更好的解；另一方面也可以在保证初始解质量的前提 下，尽可能的提高初始种群的多样性。 对于求解s d s t - j s p 问题的启发式方法，首先参考j s p 问题的启发式方法。单向表 调度( 优先权调度) 算法是求解经典j s p 问题的一种有效的启发式方法，其基于以下结 论：一道工序只有当其前序所有工序或者其后序所有工序被调度后才是可调度的。 j a c k s o n 【3 3 】调度算法是比较典型的单向表调度算法，其基本思想是将工序从前往后调度， 每次从可调度的工序集中选择剩余工作量最多的工序。然而标准单向表调度算法有个严 重缺陷，即当算法即将结束时，大多数工序的调度结果都很差，