（应用数学专业论文）求解车间作业调度的遗传算法.pdf

摘要 车间作业调度是制造系统的一个研究热点，也是理论研究中最为困难的问题之 一。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、 机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效率，有着极 大的作用。 由于调度问题具有约束性、非线性、不确定性、大规模性等复杂性，人们研究和 发展了诸如模拟退火、遗传算法、禁忌搜索、神经网络等优化算法。这些优化算法通 过模拟或揭示某些自然现缘、过程和规律而得到发展，其思想和内容涉及数学、物理 学、人工智能等多个学科，为解决复杂问题提供r 新的思路和手段。迄今，这些算法 独特的优点、机制及其非凡的优化能力，引起了国内外学者的“泛重视，并掀起了该 领域的研究热潮，而且在诸多领域得到了成功应用，较满意地解决了一大批传统优化 方法难以解决的复杂问题。 本文主要介绍了典型车间作业调度问题及其遗传算法的设计与实现。对基于车间 作业调度的遗传算法编码问题、算法操作做了详细阐述，并且对于其中的“基于先后 表的编码”做了重新诠释，进而比较了此编码与其他编码的执行效率，最后设计了一 个混合遗传算法p s a ，并给出t p s a ，o m s g a ( 保优标准遗传算法) ，s a 算法之间 的性能比较。 关键词：车间作业调度：遗传算法；全局收敛 g e n e t i c a l g o r i t h m o n s o l v i n g j o b s h o ps c h e d u l i n g p r o b l e m a b s t r a c t a sap o p u l a rr e s e a r c hr e a l mi nm a n u f a c t u r es y s t e m ，j o bs h o ps c h e d u l i n g ( j s p ) i so n eo f t h em o s td i f f i c u l tp r o b l e m si nt h e o r e f i c s t h em a i nt a s ki ns c h e d u l i n g ，i nt e r m so f p r o d u c e t a r g e ta n dc o n s t r a i n t s ，i s t od e t e r m i n et h ep r e c i s e p r o c e s sr o u t e ，t i m e ，m a c h m ea n d o p e r a t i o ne ta i f o re v e r yp r o c e s so b j e c t ，a ne m i n e n ts c h e d u l i n gs t r a t e g yc a ni m p r o v et h e o p t i m i z a t i o na n de c o n o m i ce f f i c i e n c yo fp r o d u c es y s t e m d u et ot h e c o m p l e x i t ys 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 ya n dl a r g es c a l eo f s c h e d u l i n gp r o b l e m ，m a n yo p t i m a la l g o r i t h m sl i k es i m u l a l l ta n n e a l ，g e n e t i ca l g o r i t h m ， t a b us e a r c h , a n dn e u r a ln e t w o r ka r e d e v e l o p e d a l lt h e s eo p t i m i z a t i o na l g o r i t h m s p r o p o s en e ww a y st o s o l v ec o m p l e xp r o b l e m ；t h e yw o r kb ys i m u l a t i n go r d i s c l o s i n g n a t u r a l p h e n o m e n a ，n a t u r a lp r o c e s s e s , a n dn a t u r a lr o l e s ，w h e r em a t h e m a t i c s ，p h y s i c s ， a r t i f i c i a li n t e l l i g e n c ee ta la r ei n v o l v e d s of ha l lt h e a l g o r i t h m s m e n t i o n e da b o v ea r o u s eb r o a di n t e r e s t s a m o n gs c h o l a r s t h r o u g h o u tt h ew o r l da n dl i f t e dr e s e a r c hu p s u r g ei nt h i sf i e l db e c a u s eo ft h e i rw o r k i n g m e c h a n i s m ，o p t i m i z a t i o nc a p a b i l i t y a n do t h e r p a r t i c u l a ra d v a n t a g e s ；t h e ya r ea p p l i e d s u c c e s s f u l l y i n m a n y f i e l d sa n ds o l v e m a n yl a r g eq u a n t i t i e s o fd i f f i c u l t p r o b l e m s s a t i s n c m r i l yt r a d i t i o n a lo p t i m i z a t i o nm e t h o d sc o u l d n tm a n a g e i nt h i s p a p e r , t y p i c a l j s pp r o b l e mi s m a i n l yi n t r o d u c e da n di t s g e n e t i ca l g o r i t h mi s d e s i g n e da n dr e a l i z e d t h ec o d i n gi s s u ea n do p e r a t i o no f a l g o r i t h mi ng e n e t i ca l g o r i t h m b a s e do nj s pa r eg i v e ni nd e t a i l ；t h e p r e f e r e n c el i s t b a s e dr e p r e s e n t a t i o n ”i sa n n o t a t e d o v e ra g a i n ，a n dt h e nt h ee x e c u t i o n e f f i c i e n c yo f t h i sc o d i n gm e t h o di sc o m p a r e dw i t ho t h e r c o d i n gm e t h o d s ；i nt h ee n d ，ah y b r i dg e n e t i ca l g o r i t h mp s ai s d e s i g n e d ，a n dt h e p e r f o r m a n c ec o m p a r i s o n so f p s a ，o m s g a ，a n ds a a r e p r e s e n t e d k e yw o r d 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 ；g l o b a l c o n v e r g e n c e i i 独创性说明 作者郑重声明：本学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谓f 的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名： 睦透接日期：2 q q 5 生2 旦 大连耻。r 人学硕【学位论文 1 绪论 生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制 造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效 的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关 键。改善生产调度方案，可大大提高生产效益和资源利用率，进而增强企业的竞争能 力。生产调度的研究主要可分为建模和调度算法设计两方面，它是一个交叉行研究领 域，涉及运筹学、数学、计算机工程、控制工程、工业设计等多个学科。其中，建模 主要研究调度模型、调度规划、目标函数等内容：算法主要研究算法设计、算法的复 药? 弘i ：、算法的收敛性和优化质鼹等内容。 这里主要关注的是制造系统的车间生产调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ， 简称j s p ) 。 1 1j o bs h o p 调度问题概述 j s p 研究月个工件在m 台机器上的加工过程，各个工件在各台机器上的加工时间 已知，事先给定每个工件在各个机器上的加工次序( 称为技术约束条件) ，每个机器 一次最多只能加工一道工序，调度就是把工序分配给机器上某个时间段，确定与技术 约束条件相容的各机器上所有工件的加工次序。问题的目标是找到最小时间长度的调 度。若各个工件的技术约束条件相同，则把这种j o bs h o p 调度问题称为f l o ws h o p 调度问题( 流水车间调度) 。在过去的3 0 年里，机器调度问题吸引了无数研究者的浓 厚兴趣，大量的研究成果相继问世，文献 1 给出了相关文章列表。 1 2 调度算法分类 作业车间调度问题是最困难的组合优化问题之- - ”，业已证明：超过两台机器和 两个工件的般调度问题是n p 难题。 求解调度问题的方法统称为调度优化算法。所谓优化算法，其实就是一种搜索过程 或规则，它是基于某种思想和机制，通过一定的途径和规则来得到满足用户要求的问 题的解。下面对调度算法进行简单介绍。 ( i ) 分支定界法( b o u n d a n db r a n c hm e t h o d ) 分支定界的基本思想是先求出对调度整数规划模型所对应的线性规划问题的最 优解，如果该解不满足调度问题的整数条件，则对应的线性规划问题的最优解必是调 度问题的目标函数值的上界，而调度问题的任意可行解的目标函数值则是其最优解的 下界，然后将对应的线性规划问题的可行域分成子域( 分枝) ，通过不断减少上界和增 求解车阃忭业调度的遗传算法 大f 界，最终寻找到最优解。分技定界法的实现方法是动态构造一个表示调度问题所 有可行解的树，通过对树的搜索寻找调度问题的最优解。目前分枝定界法的研究重点 在提高分枝和定界的策略【2 3 1 ，各种不同的分枝定界方法的不同点主要在于分枝规则、 定界机制和上界产生三方而的差异。分枝定界法只适合于小规模的调度问题，并且对 实际问题比较敏感，因此限制了它在调度问题上的应用。 ( 2 ) l a g r a n g e 松弛法( l a g r a n g e a nr e l a x a t i o n ) l a g r a n g e 松弛法的基本原理是：将造成问题难的约束吸收到目标函数中，并使得 目标函数仍保持线性性，由此使得问题容易求解。 h o i t o m p 与c h e n 分别用l a g r a n g e 松弛法解决过j s p 问题】。 ( 3 ) 禁忌搜索( t a b us e a r c h ，t s ) 禁忌搜索是局部邻域搜索算法的推广。g l o v e r 等人于1 9 8 6 年首次提出这个概念 1 6 j ，进而形成了一套完整的算法，详见文献 7 ，8 1 。禁忌搜索算法的特点是采用了禁忌 技术，所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主 要不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索 中，利用禁忌表中的信息不再或者选择地搜索这些点，以此来跳出局部最优点。 禁忌搜索算法具有如下的特点：没有自然性的中止条件，对求解的闯题、目标函 数和搜索空间没有任何特殊的要求，计算速度较快。因此，它在调度问题上有着广泛 的应用前景，并受到了许多学者的重视。然而，禁忌搜索算法毕竟是一个年轻的算法， 在理论和应用方面还存在许多问题需要进一步的研究。 r 4 ) 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 模拟退火算法是局部搜索算法的扩展，它不同于局部搜索算法之处是以一定的概 率选择邻域中费用值最大的状态。模拟退火算法的主要思想是m e t r o p o l i s 于1 9 5 3 年 提出的1 9 j ，它的基本过程是：从某一温度开始，对某随机系统状态进行扰动，每次 随机选择一个小的扰动，并计算其对系统的影响，通过多次扰动来模拟菜一温度下系 统的热平衡过程a 当时算法并没有用于解决优化问题。1 9 8 3 年k i r k p a t r i c k 等意识到 固体退火过程与组合优化问题之间存在的类似性，将m e t r o p o l i s 等固体在恒温下达到 热平衡过程的模拟成功地应用到组合优化问题中，形成了现在的模拟退火算法 1 0 1 。 i 基本模拟退火算法】 s t e p 1 ：在解空间s 中随机产生一个解s ，并令i = 0 ，最优解j + = j ，最优值为 加) ，确定初始温度t o 。 s t e p 2 ：若算法中止条件满足则结束搜索并输出最优解j ，否则继续以下步骤。 s t e p 3 ；在当前解j 的邻域j v 0 ) 中产生邻域解一。 s t e p 4 ：若，f ) 郧) ，则令j + = s ，郧) = 贝一) 。 大连理工大学颂士学位论文 s t e p 5 ：若f m i n l ，e x p ( 一丛堕王盟) ) ，则令s ：，郧) ：以s t ) 。 f s t e p6 ：若抽样稳定准则满足则转步骤7 ，否则转步骤2 。 s t e p 7 ：降温，即令t i + l = u p d a t e ( t ，) ，并令i = 什1 ，转步骤2 。 模拟退火法用于求解调度问题出现于众多的文献当中，文献【1 1 为f l o ws h o p 问 题构造了一类模拟退火法。文献 1 2 】提出一种改进的模拟退火法，用来解决具有最小 m a k e s p a n 指标的f l o ws h o p 排序问题，并与禁忌搜索法等进行了比较。文献 1 3 1 提 出将模拟退火法与贪婪算法相结合，先用贪婪算法搜索，得到的作业序列作为初始解， 再用模拟退火法求解单机调度问题。 由于模拟退火法能以一定的概率接受荠的能量值，因而有j 可能眺出局部极小，但 它的收敛速度较慢，很难用于实时动态调度环境。 ( 5 ) 遗传算 去( g e n e t i ca l g o r i t h m ，g a ) 遗传算法是在模拟自然界生物进化机制的基础上提出来的，它适合于求解现实世 界中的复杂问题，在2 0 世纪7 0 年代初由美国m i c h i g a n 大学的h o l l a n d 教授等人提出 的【1 4 1 。1 9 7 5 年h o l l a n d 发表了第一本比较系统论述遗传算法的专著( ( a d a p t a t i o n i n n a t u r a la n da r t i f i c i a ls y s t e m 。 用遗传算法解调度问题时通常基于这样的考虑：首先将所有工件的每一道工序定 义为一个操作，然后将所有操作的排列定义为一条染色体( 编码过程) ，染色体上的每 一个基因代表一个操作，基因的排列顺序就是操作的实现顺序，随机产生的染色体作 为初始种群，根据调度问题的优化目标函数构造染色体的适应函数，根据适应函数值 的大小确定染色体的是否生存，对生存f 来的染色体经过遗传、交叉和变异产生下一 代种群，重复上面的过程，最终求解调度问题。 由于遗传算法具有高效性、鲁棒性、通用性和灵活性，它在调度问题上已经得到 广发的应用，特别是在2 0 世纪9 0 年代以后，文献 1 5 ，1 6 等提出了改善遗传算法局部 搜索能力的方法。目前遗传算法研究主要集中在全局收敛性和搜索效率的基础数学研 究上面。 尽管遗传算法有着很多优点，但是它的有效性不是太好。 ( 6 ) 巢分区( n e s t e dp a r t i t i o n ，n p ) n p 方法是由s h i 等最近提出的一种全局优化算法，其基本思想是对可行域进行 系统性分区，然后集中搜索优良解可能位于的区域1 1 7 1 。在每一步迭代中，算法跟踪最 有希望的区域，并用随机抽样得到的信息来实现有希望区域间的转移。在第k 步迭代 中算法进行如下操作： 巢分区方法的第k 步迭代流程 ： 求解车间作业调度的遗传算缓 s t e p 1 ：分区。将最有希望的区域分成历，( 】个子区域q ( 七) ，。，( 七) ， 并将整个解空间中余下的空间0 盯( ) 合并为一个区域仃。+ i ( 膏) 。 s t e p 2 ：随机抽样。在每个区域盯，( t ) ，= 1 ，m 础) + 1 中随机选取月卜点 臼i ，一，础并计算其目标值，徊j ) ，i = l ，n ，。 s t e p3 ：计算希望指标。给定一个希望指标函数，：斗r ，计算每一区域盯，( k ) 的希望指标。譬如定义区域的最佳性能为p ，( 女) ) = 。m i 罂、f ( o ) ，其估计值为 ，l j ，( 仃，( ) ) = 印i nf ( o ) 。 t 。j ，月， s t e i 4 ：返回。确定最佳予区域j = a r g r a i n l ( a ，( i ) ) ，若j t 矾) + l 则将陔 区域作为下一步迭代的最有希望区域，否则用设计好的撤退规则返回到某个区域。 n p 算法保证每一步对所有可行空间均进行抽样，尤其对最有希望区域通过重复 分区而进行重点抽样，如此逐步缩小最佳区域。如何分区、如何得到抽样点、如何定 义指标函数、如何选择撤退规则、如何选择初始最佳区域，这些都是该方法的基本问 题。该方法非常容易实施，在理论上具有概率l 全局收敛特性，并且具有自然的并行 性，因此也可在并行计算机上实施。 ( 7 ) 变邻域搜索( v a r i a b l en e i g h b o r h o o ds e a r c h ，v n s ) v n s 方法是h a n s e n 等提出的又一种m e t a - h e u r i s t i c 算法【1 8 】最近又有若干改进方 法并成功应用于若干典型n p h a r d 问题。区别于传统方法的单一邻域结构，v n s 首 先定义系列邻域结构，并在搜索过程中系统性地不断改变( 扩大) 邻域搜索范围，直 到有新的更好的解产生。 f 基本变邻域搜索算法】： s t e p l ：定义一系列邻域结构m ，k = l ，。给定一个初始解。 s t e p2 ：重复下列过程直至算法终止： ( 2 1 ) 令k = l 。 ( 2 2 ) 重复下列过程直至捂。： ( 2 2 1 ) 由当前解x 在其第是种邻域他内随机产生新解一； ( 2 2 2 ) 以f 为初值应用邻域搜索方法得到局部极小解x ”； ( 2 2 3 ) 若x ”优于x 则z 唧”并令k = - i ，否则k = k + l 。 可见，确定邻域结构及其数量，确定各邻域结构在搜索中应用的次序及其改变的 策略，是v n s 要解决的基本问题。例如旅行商问题，可以定义邻域搜索结构为k - o p t 变换，k = - 2 ，3 ，行，即两条不同回路间仅存在k 条不同的边。由于k - o p t 的解必然 优于( k - - 1 ) 一o p t 的解，因此通过增大k 即可扩大邻域搜索范围，并能取得更好的解。 4 大近理工人学硕l 一学位论文 需要指出的是：v n s 除了多邻域的应用，也可采用多利，不同的子邻域搜索方法；另 外，研究问题目标函数中局部极小和相应波峰波谷的拓扑结构不仅有助于对问题有更 清晰的了解，而且有助于提供v n s 进行搜索的有用信息，但迄今这方面的研究成果 相当少，且限于极少数几个问题。 ( 8 ) 噪声方法( n o i s i n gm e t h o d ，n m ) n m 方法是c h a r o n 等最近提出的一种组合优化算法l 】，它可以理解为s a 的一 种变形和推广。区别于传统邻域搜索算法和s a ，n m 对新旧状态的目标值差附加 一定的扰动，即乜= + p ，其中p 一，r 为扰动，然后判断h 0 是否成立。成立 则接受新状念，否则保留旧状态。当上述搜索过程持续一定步数后，算法适当降低r 侬来减小噪声幅度，显然当，= 0 删n m 称为传统趋化性下降搜索，棚对于s a 的， = 0 x , 3 于s a 而言，若a m 结束 对于刚才的死锁调度，可以如下安排：扫描3 台机器的第一个待加工工件，有 d 2 l 在机器1 ：0 1 2 在机器2 ；仍2 在机器3 。考察工艺约束，仅0 2 l 在机器1 可操作， 如图( a ) 。其次可进行的操作为0 2 2 在机器3 ，如图( b ) 。至此，当前的优先操作为：0 3 2 在机器1 i0 1 2 在机器2 ，轨3 在机器3 ，但它们因不满足工艺顺序均不可进行，因此， 判定调度死锁，由于当前操作停留在机器3 上( 它当前待加工工件是工件1 ) ，找到 工件1 的待加工工序及其机器( 即d l l