（应用数学专业论文）基于混合遗传算法的job+shop调度研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 作业车间调度( j o b s h o ps c h e d u l i n gp r o b l e m ) ，是车间加工的一个关键模 块，功能是对企业工场内的作业进行组织、调度和管理。工场在有效和合理安排 组织生产过程、利用设备、生产出产品或配件的条件下，以完成大量的作业为其 基本特征。并且要考虑满足任务配置和顺序约束的资源分配，所以是n p 难题之一。 有效的生产调度方法和优化技术的研究和应用，对实现先进制造和提高生产效益 显得非常关键。j o b s h o p 调度问题的研究早在1 9 5 4 年就展开了，求解的方法以启 发式算法为主，基于优先权规则，即从未排序的工序特定子集中选用工序的规则。 能否在给定资源和设备的条件下，有效的解决和优化作业车间调度问题是企 业在竞争中生存的关键因素。它表现在有效利用企业现有的资源、合理制定企业 和车间生产计划、保证按时交货等因素。国外对车间调度问题的研究已经有了五 十多年的历史，中国也有二十多年的研究经验，专家们从最开始的枚举方法到构 造性方法到现在领域搜索方法，一直不断的完善和改进车间调度问题，但要彻底 解决这一难题还需要大量的工作。本文对这一领域的若干问题进行了较为深入的 研究，取得了一些有益的成果。 具体工作如下： 1 提出生产调度问题研究的背景与意义。 2 给出了车间作业调度问题的定义，车间作业调度问题的数学描述，探讨车间 作业调度问题的可计算性和计算复杂度，回顾研究求解车间作业调度问题的主要 历程及其方法。 3 分析遗传算法的基本原理，以及基于遗传算法在求解车间作业调度问题中 关于算法算子的设计，如编码的选取，变异与交叉算子的设计，并通过实例给出 了采用这种方法所得到的结果。 4 在深入研究了遗传算法的基本原理、方法与实现技术的基础上，结合车间 作业调度问题，提出了一种用于求解j o b s h o p 调度问题的混合型遗传算法。在该 第1 i 页河南大学研究生硕士学位论文 算法中，结合遗传算法与模拟退火算法的优缺点，设计出一种混合两种优点的一 种新的算法，并设计了一种新的交叉算了以及高性能的编码方法，并通过实例给 出了采用这种方法所得到结果的优越性。 5 最后，对本文所作的工作进行了总结，对j o b - s h o p 调度问题的未来研究方 向进行了有益的探讨和展望。 关键词：车间调度；j o b s h o p ；遗传算法；模拟退火算法 河南大学研究生硕士学位论文第1 i i 页 a b s t r a c t j o b s h o pp r o d u c t i o ns c h e d u l i n gi sak e yp r o c e s s i n gw o r k s h o pm o d u l e ，w i t ht h e f u n c t i o no ft h eo r g a n i z a t i o n ，t h ed i s p a t c ha n dt h em a n a g e m e n to ft h ew o r k s h o pw o r k b a s e do nt h eo r g a n i z a t i o n a lp r o d u c t i o np r o c e s s ，t h ee q u i p m e n tt op r o d u c ep r o d u c t so r f i t t i n g si ne f f e c t i v ea n dt h ee n t i r ep r i n c i p l e ，t h ew o r k s h o pt a k e st h em a s s i v ew o r ka si t s e s s e n t i a lf e a t u r e j o b - s h o pp r o d u c t i o ns c h e d u l i n gm u s tc o n s i d e rw h a ts a t i s f i e st h ed u t y d i s p o s i t i o na n dt h es m o o t hr e s t r a i n tr e q u e s tr e s o u r c ed i s t r i b u t i o n ；t h e r e f o r e ，i ti so n eo f n pd i f f i c u l tp r o b l e m s e f f e c t i v em e t h o d so fp r o d u c t i o ns c h e d u l i n ga n do p t i m i z a t i o no f t e c h n o l o g yr e s e a r c ha n da p p l i c a t i o nf o ra d v a n c e dm a n u f a c t u r i n gh a v et ob et a k e n ， i m p r o v e m e n to ft h ee f f i c i e n c yo fp r o d u c t i o nh a sb e c o m ec r i t i c a l t h es t u d yo fj o b s h o p s c h e d u l i n gp r o b l e mh a sb e g u na se a r l ya si n 19 5 4 t h ea p p r o a c ht os o l v i n gt h i s p r o b l e mm a i n l yr e s t so nh e u r i s t i ca l g o r i t h m ，b a s e do np r i o r i t yr u l e sw h i c hf o c u so n s e l e c t e ds u b - p r o c e s s e sf r o ma p a r t i c u l a ru n s o r t e dp r o c e s s t h ee f f e c t i v es o l u t i o na n do p t i m i z a t i o no fj o b - s h o ps c h e d u l i n gp r o b l e mi sak e y f a c t o rt os u r v i v ed u r i n gt h ec o m p e t i t i o ni nt h eg i v e nr e s o u r c e sa n de q u i p m e n tc o n d t i o n s t h ef a c t o r sm a n i f e s t e di nu s i n gt h ec o r p o r a t ee x i s t i n gr e s o u r c e se f f e c t i v e l y , f o r m u l a t i n g e n t e r p r i s ea n dt h ew o r k s h o pp r o d u c t i v ep l a nr e a s o n a b l y , d e l i v e r i n go nt i m e l ya n ds oo n t h er e s e a r c ht ot h ew o r k s h o ps c h e d u l i n gp r o b l e mh a da k e a d ym o r et h a n5 0y e a r sl o n g h i s t o r yo v e r s e a s ，a n dc h i n ah a da l s om o r et h a n2 0y e a rr e s e a r c he x p e r i e n c e s e x p e r t s i m p r o v et h ew o r k s h o ps c h e d u l i n gp r o b l e me a r l i e s tf r o mt h ee n u m e r a t i o nm e t h o dt ot h e c o n s t r u c t i v i t ym e t h o dt ot h ep r e s e n td o m a i nr e c o n n a i s s a n c em e t h o d b u tt h er e s e a r c h e r s w h ow a n tt os o l v et h i sd i f f i c u l tp r o b l e mt h o r o u g h l ya l s oh a v em a s s i v ew o r kt od o t h i s a r t i c l eh a sc o n d u c t e dm o r ed e e pr e s e a r c hi n t ot h i sd o m a i n ，h a so b t a i n e ds o m eb e n e f i c i a l r e s u l t s t h ec o n c r e t ew o r ki sa sf o l l o w s ： 1 t op r o p o s et h eb a c k g r o u n da n dt h es i g n i f i c a n c eo ft h ep r o d u c t i o ns c h e d u l i n g q u e s t i o n 2 t h i sa r t i c l eh a sg i v e nt h ed e f i n i t i o no fw o r k s h o pj o bs c h e d u l i n gq u e s t i o na n dt h e m a t h e m a t i c sd e s c r i p t i o no fw o r k s h o pjo bs c h e d u l i n gq u s t i o n ，a n dd i s c u s s e st h e c i r c u l a r i t ya n dt h ec o m p u t a t i o nc o m p l e x i t yo ft h ew o r k s h o pj o bs c h e d u l i n gq u e s t i o n ， a n dr e v i e wt h em a i np r o c e s sa n dt h em e t h o do ft h er e s e a r c ht os o l v et h ew o r k s h o pj o b s c h e d u l i n gq u e s t i o n 3 t h i sa r t i c l eh a sg i v e nt h eg e n e t i ca l g o r i t h mb a s i cp r i n c i p l e ，a sw e l la sa b o u tt h e a l g o r i t h mo p e r a t o rd e s i g nb a s e do nt h eg e n e t i ca l g o r i t h mi ns o l v i n gt h ew o r k s h o pj o b s c h e d u l i n gq u e s t i o n s ，f o re x a m p l e ，t h es e l e c t i o no f t h ec o d e s ，a n dt h ev a r i a t i o na n dt h e o v e r l a p p i n go p e r a t o r 。sd e s i g n ，a n dg i v et h er e s u l tw h i c hu s e st h i sm e t h o dt h r o u g ht h e e x a m p l e 第1 v 页河南大学研究生硕士学位论文 4 t h i sa r t i c l ep r o p o s e dt h em i x e dt y p eg e n e t i ca l g o r i t h mu s e di ns o l v i n gt h e j o b - s h o ps c h e d u l i n gp r o b l e mu n i f i e dt h ew o r k s h o pj o bs c h e d u l i n gq u e s t i o na f t e ra d e e pr e s e a r c hi n t ot h eg e n e t i ca l g o r i t h m 。sb a s i cp r i n c i p l ea n dt h em e t h o da n d r e a l i z a t i o n i nt h et e c h n i c a lf o u n d a t i o n i nt h i sa l g o r i t h m ，ic o m b i n eg e n e t i ca l g o r i t h ma n dt h e s i m u l a t i o na n n e a l i n ga l g o r i t h m sg o o da n db a dp o i n t s ，a n dd e s i g no n en e wa l g o r i t h m w h i c hm i xt w ok i n do fm e r i t s ，a n dg i v et h er e s u l tw h i c hu s e st h i sm e t h o dt h r o u g ht h e e x a m p l e 5 f i n a l l y , t h ew o r kw h i c hd i dt ot h i sa r t i c l eh a sc a r r i e do nt h es u m m a r y , a n dt h e b e n e f i c i a ld i s c u s s i o na n dt h ef o r e c a s tt ot h ej o b s h o ps c h e d u l i n gp r o b l e m sf u t u r e d i r e c t i o n k e yw o r d s ：w o r k s h o ps c h e d u l i n g ；j o b s h o p ；g e n e t i ca l g o r i t h m ；s i m u l a t i o n a n n e a l i n g a l g o r i t h m 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加阻说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所儆的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位中请人( 学位论文作者) 签名：童叠 2 0 1 ) 罗卑z 月 臼 关于学位论文著作权使用授权书 本人经河南大学审核批准授子硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 甄质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：工耋经 2 0 09 年6 月 目 学位论文指导教师签名：墓拿吐 2 0 扫罗年6 月 目 河南大学研究生硕士学位论文第1 页 1 1 研究的背景与意义 第一章引言弟一早jl 苗 8 0 年代，企业以大批量生产为特点，这比较符合生产产品品种比较单一，生 产流水线固定的企业，而现在企业的生产调度已经转变为单品种，大批量的生 产特点，这也是市场经常条件下发展的需要。由于企业生产的产品品种多、批量 小、生产组织工作复杂，安排工作难度大，如果计划的及时性和应变性都不强， 则会导致公共交货期增长，任务完成的提前期和拖后期等因素影响了生产的经济 效益。自从j o n h s o n 在1 9 5 4 年解决两台机床的流水线调度问题以来眩1 ，研究者们 利用应用数学、工程技术、运筹学等方法来解决生产调度问题，在一系列经典的 调度问题和优化问题上取得了一定有成绩。c o n w a y ，m a x w e l l 和m i l l e r 对企业生产 调度的研究奠定了调度理论研究的基础b 1 。 企业生产调度问题是典型的多目标优化问题，在安排生产调度的同时，要同 时考虑满足生产调度的约束性。生产调度问题的约束性表现在确定所有待加工工 序的前后顺序、起始时间及占用的资源、机器闲置与劳动力的费用、调度过程中 库存的费用、交费日期等。只有考虑同时满足这些约束条件，才能有效的通过调 度算法解决车间调度问题，满足企业生产加工的需求。 国外对企业生产调度的研究已有近6 0 年的历史，在不同的阶段都有一些具有 代表性的技术和算法诞生。我国对此问题的研究仅2 0 多年的时间，也取得了很好 成就和效果。我国的制造业在制造装备和生产组织管理技术方面相对于国外工业 发达的国家来说，还是比较落后的，如我国大多数企业仍以普通机床为主，生产 管理和调度仍以手工和经验为主。在这种现状下企业花大量的资金更新工艺装备、 提高制造工艺水平和自动化程度是不现实的，实际上也没有必要。完善和清晰的 调度管理体系、有效的调度方法和优化技术应用，是我国企业的面临的首要任务。 第2 页河南大学研究生硕士学位论文 j o bs h o p 调度不仅是n p 难题，而且是最难的组合优化问题之一。它的研究不 仅可以推动相关算法的研究，如：模拟退火算法、遗传算法、神经网络、免疫算 法、禁忌搜索算法等，为其它领域类似问题的解决提供条件和手段，同时也会对 n p 问题的研究起到有意义的影响。 1 2 车间调度的分类 车间调度问题，按照不同的分类标准h 1 ，可分为以下四种类型： ( 1 ) 按照企业生产调度加工系统的复杂程度( 最基本的分类) ：分为单机调 度、多台并行机调度、f l o ws h o p 调度和j o bs h o p 生产调度。 按调度的复杂程度，一般把生产调度分为单机调度、流水线车间调度( f l o w s h o p ) 、多机器并行加工调度( km a c h i n ei np a r a l l e l ) 、作业车间调度( j o bs h o p ) 。 单机调度是生产调度中最基本和最简单的调度，这种调度是指所有要加工的工件 都在一台机器上按照某种优化加工工序排列加工；流水车间调度是生产调度中相 对比较简单的调度类型，与单机调度不同的是，加工的机器可能有多个，但这些 机器加工的工件都是按事先安排好的加工工序进行的，多机器之间的顺序是串行 的；多机器并行加工调度是指机器间的关系是并行的，所有的工件在并行的机器 上以相同的工序和操作进行加工。作业车间调度是最普通的调度，也是最难的调 度，因为这种调度的约束比较多，是典型的多目标优化调度和n p 难题，它指m 台 不同的机器加工n 个具有特定加工工序的工件，已知加工工序与对应机器上的加 工顺序和加工时间，并且要考虑加工约束( 这点会在这1 4 节节中做具体分析) 。 ( 2 ) 按照企业车间生调度性能指标来划分：分为基于调度费用和调度性能指 标两大类。 车间调度问题是多目标优化问题，其中一个目标就是怎样使生产调度费用最小 化，在这种情况下可能要牺牲调度时间或性能等因素；另一个目标是调度性能的 最优化，在这种情况下可能要牺牲调度时间、费用等因素。 ( 3 ) 按企业生产调度环境的特点来划分：分为确定性生产调度和随机性生产 河南大学研究生硕士学位论文第3 页 工调度。 车间生产调度由于生产环境的不同，有的调度问题的加工工序、加工时间、加 工工件所需的机器已经被安排好了，而有的调度序号没有被事先确定，工件的加 工序、加工时间以及加工所需机器都没有被安排好，而是随机安排的。 ( 4 ) 按企业生产调度的分类来划分：分为静态调度和动态调度。 静态调度，从它的字面可以看出应该是在调度过程中各作业的加工时间、加 工顺序、加工机器被确定后不再被改变；动态调度有点像操作系统进程管理，所 有待加工的工件进行排队处于待加工状态，作业按照加工顺序不断由等待状态变 成加工状态，加工完成的作业离开后，后继的加工工件工序由等待状态变成加工 状态进行加工，然后再离开。在实际的车间加工调度中，我们要考虑的更 复杂一些，比如加工过程中出现的人为因素、加工材料不足、设备的损坏等。这 也是研究车间调度问题的难点所在。 1 3 车间调度问题的特点 主要有以下特点畸1 ： ( 1 ) 复杂：复杂性是车间调度问题的突出特点。车间调度问题建模比较复杂， 此问题模型较多，条件稍加变化，原来的算法就可能变成另外一种调度问题或不 适用。另外，计算比较复杂，此问题的解决在要满足一定加工对约束下完成优化 操作，在计算量上往往是具有n p - h a r d 特性，随着问题规模的增大，其计算量急 剧增加，使得一些常规的方法无能为力。 ( 2 ) 随机：车间调度问题因为要考虑很多随机的和不确定即约束因素，因为 生产环境是不固定的，而且在调度过程中会遇到多种随机干扰，这都是我们要考 虑的，如果某一机器上加工的下一道工件由于某些原因不能及时到达，那么后继 的加工工件都要受到影响。或者由于机器的原因作业的加工时间比原来指定的加 工时间长等。设备的损坏、加工工件的损坏等因素可以看出，车间调度过程是一 个动态的随机过程，另外，在实际的车间调度系统中问题显得更复杂一些。 第4 页河南大学研究生硕士学位论文 ( 3 ) 约束：在上面两个调度特点中已经提到，调度问题的约束性是导致车间 调度问题复杂的重要原因。此问题中要考虑资源的数量、缓存的容量、工件加工 时间以及工件的操作顺序等都是约束。此外还有一些人为的因素、与加工车间相 关的车间外的因素，如要求各机器上的负荷要平衡等，这些都是我们要考虑的因 素。 ( 4 ) 多目标：车间调度问题是多目标优化问题，而且这些目标之间往往是发 生冲突的( 这是多目标优化的一个特点) 。第一个目标是作业的交货日期，生产企 业都希望及时的把生产出来的产品交给订货商。第二个目标是作业的完成日期， 作业完成日期不要提前也不要拖后，而是按照预先的交货日期加工完成，如果提 前加工完成会造成库存，拖后加工完成会延误交货日期给生产企业造成经济损失。 第三个目标是基于生产成本的目标，怎样在按时交货和加工的情况下使生产成本 降到最低。 1 4j o bs h o p 调度问题描述及数学模型 l o bs h o p 是研究企业生产车间1 个工件按照每个工件的加工次序，在皿台机 器上加工的问题。已知每个工件在各个机器上的加工次序和每个工件的各个工序 的加工时间，要求确定与工艺约束条件相容的各机器上所有工件的加工开始时刻、 完成时刻、加工次序，使加工性能指标达到最优。 生产调度过程要满足以下约束： ( 1 )在整个加工过程中，每个工件只能被所有的机器都加工并且只加工一 次； ( 2 )各个工件必须按工艺路线以指定的次序在机器上加工； ( 3 )加工过程不能间断： ( 4 )每一时刻每一台机器只能加工一个工件。 为了便于理解，先作如下假定： 河南大学研究生硕士学位论文第5 页 ( 1 ) 设j 为工件的集合，j = d ，江1 ，n 。这里n 表示第n 个工件，同时也表 示工件总数为n 个。 ( 2 ) 设m 为机器的集合，m = 磅，k = 1 ，2 ，m 。这里m 表示第m 台机器，同 时还表示机器总数为m 台。 ( 3 ) 设j o , 为工件i 包含的工序集合，j o , = ) ，j = 1 ，2 ，绝。这里强表示工 件f 有吩道工序，且吩还表示是工件i 的最后一道工序。 ( 4 ) 设矿为所有工件的工序集合，为任意工件的任意工序，记v = ( f ，j ) 。 ( 5 ) 设j 0 为工件i 的第道工序加工开始时间。 ( 6 ) 设p 乇为工件f 的第j n i 序加工结束时间。 ( 7 ) 设p 乇为工件f 的第道工序加工持续时间。 ( 8 ) 设& 为所有在机器七上加工的加工工序的一种排序，记k ( ，) 为在s 中第 ，位置上的加工工序， 则s k = ( v k ( 1 ) ，k ( 耽，n ( 厶) ) ， 其中： k ( 1 ) v ；i = 1 ，；七= 1 ，m 。 ( 9 ) 设j o bs h o p 调度问题的解为j ，则s = ( s l ，& ，s 。) ，k = 1 ，m 。 j o bs h o p 调度问题通常以最小化最大完成时间( m a k e s p a n ) 为目标函数。以 最小化最大完成时间为目标函数是在可行解的解空间中，找出一个解，该解的所 有工件的最大结束时间与其它所有可行解相比为最小，用数学式表示为： c = m i n ( s ) = m i n ( m a x ( e t o m = m i n ( m a x ( s t o , + p t o 伪，i e j ( 卜1 ) j o bs h o p 调度问题的求解就是要找到一个合理的安排使每个工件都能在满足 工艺约束的条件下在各台机器上加工，使得总的加工时间最短。在上- d , 节已经 定义过，f 发e t u 为工件i 的第j 道工序加工结束时间，p t u 为工件i 的第j 道工序 第6 页河南大学研究生硕士学位论文 加工持续时间。如果机器h 先于机器k 加工工件i ，则应满足如下约束： e t i k - p t f e t 拍 如果机器k 先于机器h 加工工件i ，则应满足如下约束： e 亡抽一p t 曲 e t n 定义变量x 亡，船，则： l1 ，机器h 先于机器k 加工工作i x t i _ | ，, = l0 ，否则 则上述可表述为： 口k p 屯+ l ( 1 一x l i ，七) e t , h ( 1 ) i = l ，2 ，n ；h ，k = l ，2 ，m 其中l 为一足够大的正数。对于在机器k 上加工的工件i 和j ，如果工件i 先于工 件j 在机器k 上加工，则应满足如下约束： e t j k e t , k p t j k 如果工件j 先于工件i 在机器k 上n i e t , k e t j k p t i k 定义变量 f1 ，工件i 先于工件j 在机器k 上加工 y t , j , 2l o ，否则 则上述约束可表述为： 一+ l ( 卜y t , j , ) p t j k ( 2 ) i ，卢1 ，2 ，2 ；仁1 ，2 ，历 因此一个n m g e t m 。c 懈( 力表示工件数，m 表示机器数，g 表示是j o b s h o p 调 度1 ；i n ，e t m 。表示性能指标为最大完成时间) 的j o b s h o p 调度问题的数学模型 河南大学研究生硕士学位论文第7 页 可描述如下： f 铀i nk 所m a x ，q 疗m a x 引 1 5 求解j o bs h o p 问题的研究现状 自从j o h n s o n 提出的两台机床上f l o ws h o p 排序问题的最优算法$ 3 以来。很多 相关j o bs h o p 调度问题的算法被相继提出，大体上可以分为三类：枚举方法，构 造性方法和邻域搜索算法。一些研究机构和高校如清华大学，上海交通大学，西 安交通大学都对j o bs h o p 做过相关研究，并取得了很好的效果和改进。虽然国际 上对j o bs h o p 的研究不到六十年时间，而国内的研究时间不n - 十年时间，但对 于车间作业调度问题的研究慢慢变得成熟起来。但由于车间调度的复杂性，至今 尚未形成一套系统的理论与方法。总结来说，现有的解决方法大体上可以分为以 下几种类型： ( 1 ) 运筹学的方法 该方法运用运筹学的数学规划模型，通过枝定界法或动态规划算法来求生产 调度问题哺3 。其中，分枝定界方法用来动态构造一个树，通过对树的搜索寻找调度 问题的最优解，此树表示调度问题所有可行解。分枝定界法对于工件个数小于2 5 0 的调度问题解决起来还是比较顺手的，但超过这个数，处理起来就显得吃过或无 能为力。另外，分枝定界方法要解决的首要问题是设置上下界值，特别是上界值 的确定非常重要也非常敏感，如果设置不当，则很难得到最优的可行解。由此可 见，分枝定界法只适合于小规模的调度问题，并且这类方法虽然从理论上能求得 最优解，在前期的生产调度研究中起到了很重要的作用，但由于其计算复杂性的 原因，不能获得真正的实用。同样，动态规划在处理车间调度问题时，所显示出 来的优点和缺点和分枝定界方法一样，他们都是早期用来研究车间调度问题的方 法。 ( 2 ) 基于启发式规则的方法h 3 第8 页河南大学研究生硕士学位论文 s t e v e n sa n dg e m m ill 对j o n h s o n 在19 5 4 年的两机器的f l o ws h o p 调度问题进行 了改进和优化，他们在1 9 9 7 年用基于启发式方法解决了此问题。这些启发式规则 简单易行，相对于运筹学方法来说，此方法在解决一些小规模问题时更有优越性， 问题是难以得到全局优化结果，且对问题的性质与应用场合的依赖性较强。 ( 3 ) 基于人工智能的方法 上世纪8 0 年代，s t e p h e n 等人对调度问题进行了深入研究陋1 。其中具有重要研 究意义的就是以c a m e g i e m e l t o n 大学的m f o x 为代表的学者们开展的基于约束传 播的i s i s 研究盼1 ，它标志了人工智能开始真正应用于调度问题。8 0 年代后期，g i f l e r 等人n 们总结了车间调度的理论和实践方面的最新研究进展，从七个方面论述了车 间调度的技术和方法，认为车间调度无论在理论还是实践上都已突破了传统界限。 人工智能包括神经网络方法、专家系统、蚁群算法等。是最早提出针对车间调 度的专家系统。h o p f i e l d 神经网络模型的提出为求解各种有约束优化问题开辟了 一条新途径。2 0 0 2 年，王万良等人介绍了一种随机h o p f i e l d 网络来解决j o bs h o p 调度问题的方法n 。 ( 4 ) 仿真方法 仿真方法建立在排队论、p e t r i 网、极大代数等方法的基础之上，通过仿真分 析在不同情况下系统的性能来进行计划和调度，对同一问题调度，仿真效果可能 不同，这要求提出很好的仿真模型n 羽，为工作增加了难度。另外，对j o b - s h o p l 菌 题有较好性能的方法并不能保证对柔性车间调度问题同样有较好的结果口引。 ( 5 ) 神经网络方法( n e u r a ln e t w o r k s ，n n ) j o bs h o p 调度问题是组合优化问题，神经网络方法已被成功地应用于此问题 的解决，但对于大规模、复杂调度系统，神经网络由于计算速度慢，而且结构参 数难以确定而没有被做为首要考虑解决生产调度问题的方法。f o o 在1 9 9 8 年应用随 机h o p f i e l d 网络来解决调度问题，构造网络能量函数一一l y a p n o v 函数进行优化， 当网络迭代收敛时，能量函数达到最小。 ( 6 ) 领域搜索方法 河南大学研究生硕士学位论文第9 页 邻域搜索技术由于是随机性和启发式的，当搜索解空间时，仅对选定的目标函 数值的变化做出响应，因而通用性强，受到各领域广泛的关注和应用，解的质量 一般能得到显著提高。车间调度问题通常具有大量的局部极值点，它的特点是不 可微、不连续、多维、有约束条件、高度非线性。因此，精确地求解车间调度问 题的全局最优解一般是不可能的。 近些年来，邻域搜索在车间调度领域得到了相当广泛的研究和应用。这类方 法包括模拟退火算法( s i m u l a t e da n n e a l i n g ) ，禁忌搜索算法( t a b us e a r c h ) 和 遗传算法等。 遗传算法( g e n e t i ca l g o r i t h m s ) 遗传算法n 町比较适合于在复杂而庞大的搜索空间中寻找优化解，而j o bs h o p 问题的解空间是比较复杂和庞大的，遗传算法在搜索过程中能够自动获取和积累 有关搜索空间的知识，并自适应地控制搜索过程。遗传算法原理简单、鲁棒性强， 易于并行分布处理，非常适合于解决调度问题。1 9 8 5 年d a v i s n 朝首次将遗传算法用 于解决调度问题，提出了排序中局部交换、环状交换及序基变异操作等。 模拟退火方法n 6 3 ( s i m u l a t e d an n e a l i n g ，s a ) 模拟退火方法模仿晶体的冷却过程，它渐近收敛子全局最优解，但收敛速度 较慢，对参数的设置很苛刻。s a 同样还被用于f l o ws h o p 排序、机器分组和有资源 约束的调度问题。 d o r n d o r f 等用g a 优化工件分配规则序列n 7 3 和s b ( s h i f t i n gb o t tl e n e c k ) 方法 意义下的单机解序列。h a r t n 8 1 等分析t g a 的特点，设计了一个可调整难度的可配 置问题的触发器，证明了g a 具有相当好的鲁棒性。h a j r i n 等提出了一种受控遗传 算法，并采用并行机编码，用启发方法产生初始种群和多交叉操作，同时基于模 糊逻辑和置信来估计遗传操作的参数。近年来，混合遗传算法的研究在国际上受 到广泛重视。1 9 9 1 年d a v i s 首次提出混合算法思想，提出了“h y b r i d i z ew h e r e p o s s i b l e ，1 9 9 9 年c h e n g 渤1 等介绍了一些求解j s p 的混合算法，包括自适应遗传 算子、基于启发式特征的遗传算子和混合遗传算法的设计。在2 0 0 0 年，d i m o p o u l o s 乜 第1 0 页河南大学研究生硕士学位论文 等则对混合遗传算法思想进行了进一步论证，并证明它的可行性；k o o n c e 乜2 1 等利 用数据挖掘算法由遗传算法生成的调度集中抽取知识，从而开发一个规则集调度 器来逼近遗传算法的行为，并取得良好的效果；c a i 乜3 1 等结合局部搜索方法和g a 求 解j s p 问题提出了遗传算法和成组技术相混合，降低了j o bs h o p 问题的复杂性，j o b s h o p 问题在一定程度上转化为f l o ws h o p 问题。 禁忌搜索算法 禁忌搜索是最早由g l o v e r 乜郇乜朝提出，它是用于获取组合最优化难题近似解的 一种高级启发式方法。禁忌搜索通过禁忌移动操作来完成最终的最优或次优解， 在每次移动前，需要依据某种与问题有关的规则确定在现行解周围的相邻解集， 从一个可行解开始逐步移向一个最优或次优解。然后评估每一个相邻解，并移动 到该相邻解集中的一个最好解。从禁忌算法字面上可以看出，这种算法的某些操 作有些移动是禁忌的( 禁止的) ，因为它们会陷入局部最优或导致循环。这些禁忌 的移动被加入禁忌表，一般地，禁忌表的长度越长，则搜索陷入局部最优的可能 性越小。缺点是，长禁忌表需要更多的计算扫描时间，并且在每次迭代中限制了 搜索空间。关于禁忌表的长度，如果要求最合适的长度，它与问题有关，但到目 前为止还没有确定长度的规则可循。g l o v e r 给出了它的基本原理并解决f l o ws h o p 调度问题的禁忌搜索算法。g a r c i a 等人针对求解公共交货期下带有等待时间惩罚 的提前拖期单机调度问题，提出了一种禁忌搜索法。 1 6 车间调度研究存在的问题 由于车间调度问题是n p h a r d 难题，它要求在解决问题时要满足一些约束性， 最终实现以最小化最大完成时间为目标的操作。现代企业在保持质量的时间对作 业交货期的按时完成，已经成为企业生存的关键因素。在实际车间调度中，对于 一般调度方法能够响应系统的动态变化，但不能保证得到好的调度。比如：前面 提到的枚举类型的方法，大多数是建立在对可能调度的部分枚举上，寻找具有多 项式复杂性的最优算法相当困难。 河南大学研究生硕士学位论文第1 1 页 在大多数对车间调度问题的理论研究中，还是集中在针对经典车间调度问题 设计优化算法，比如6 机器6 i 件，1 0 机器l o 工件，3 机器3 工件等。这类调度问题 局限在理想的确定性环境中并且每道工序所使用的机器事先被唯一确定，这样由 于不灵活性直接导致了加工计划和生产调度相脱节与实际相差较大。而在实际生 产中，我们经常会遇到一些突发事件，比如客户订单的取消，劳动力因素、机器 故障、原材料的供应、操作工的误操作、生产过程中每道工序的准备时间、加工 时间、传输时间等的变化，能源的暂时短缺等大量的不确定性因素的的影响；而 且随着加工技术、自动化技术的发展，特别是柔性加工系统( f m s ) 的出现，使得 在实际生产中变得更复杂，f m s 允许一道工序可以在不同的机器上加工，增加了机 器选择的的柔性。因此，在当前先进制造技术环境下，柔性j o bs h o p 调度问题和 不确定性j o bs h o p 调度问题将是一个研究重点和进一步研究的方向，而目前对于 这方面的研究的文献相对来说还比较少。另外，还有很多有待进一步研究的问题， 比如实际车间调度的多目标性、动态随机性等。 1 7 研究的主要内容和论文章节安排 1 7 1 论文的主要内容 本文针企业生产调车间管理与调度的特点，分析了车间作业调度的特点，给 出了通过洽遗传算法与模拟退火算法求解车间作业调度的过程。 主要内容如下： 本文在简要分析车间调度问题研究现状和简要描述遗传算法理论的基础上， 描述了加工路径和j o bs h o p 调度问题的数学模型，设计了混合遗传算法与模拟退 火算法来求解此类问题，并设计了新的交叉方法来解决在交叉运算时出现的不可 行个体，通过仿真实例，验证了本文算法的有效性和优越性。 1 7 2 论文的章节安排 第一章说明了课题的提出背景和研究意义，详细阐述了车间作业调度问题， 第1 2 页河南大学研究生硕士学位论文 分析了调度模型及数学模型描述，总结了车间调度的求解方法，讨论了车间调度 的国内外研究现状，最后给出了本文的研究内容和论文的结构安排。 第二章详细介绍了遗传算法的基本理论，算法的编码、选择、交叉、变异算 子的定义和用法，以及遗传算法的发展史。 第三章介绍基于遗传算法的j o bs h o p 调问题的模型、算子设计方法、以及遗 传算法求解车间调度问题的框架。 第四章在分析了模拟退火算法的基本原理的基础上，整合遗传算法与模拟退 火算法的的优点和长处，通过设计合理、高效的编码以及自适应交叉和变异算子。 并通过仿真实例证明两种算法结合起来的要比单独用遗传算法或模拟退火算法的 优越性，选择新的交叉方法与解码方法，保证了交叉操作后代的可行性和从父代 遗传优良特征。给出了仿真实例和仿真结果，证明了遗传算法在求解车间作业调 度问题的有效性。 第五章对本文作出总结，并对本文进行了展望。 河南大学研究生硕士学位论文第1 3 页 第二章遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是模拟生物在自然环境中的遗传和进 化过程而形成的自全局优化概率搜索算法。由美 m i c h i g a n 大学的j o h n h o l l a n d 教授于1 9 7 5 年首先提出的。起源于6 0 年代对自然和人工自适应系统。对自然界遗 传选择和自然淘汰( n a t u r a ls e l e c t i o n ) 的生物进化过程计算模型，该算法是基 于“适者生存”的一种高度并行、随机和自适应优化算法，此算法把要求的解通 过一串编码即“染色体”来表示，由多个“染色体 组成一个种群，然后对些种 群进行遗传算法的操作( 选择，交叉，变异) ，经过许多代不断的优化最后得到“最 适应环境”的解。目前随着计算机技术的发展，遗传算法愈来愈得到人们的重视， 并在机器学习、神经网络、优化控制、生产调度等领域得到广泛应用。 2 1 遗传算法发展历史 对于遗传算法的研究从上世纪4 0 年代已经开始了，研究者从生物学的角度进 行了生物的进化过程模拟、遗传过程模拟等研究工作。真正的研究起源于六十年 代，美国密执安大学教授h o l l a n d 的开创性工件，其本意是在人工适应系统中设计 的一种基于自然演化原理搜索机制。大约在同一时间，f o e g l 和r e c h e n b e r g 及 s c h w e f e l 弓 入另两种基于自然演化原理的算法、深化程序和深化策略。这三种算 法构成了目前演化计算领域的三大分支，它们从不同层次、不同角度模拟自然深 化原理，以达到求解问题的目的。 h o l l a n d 试图发展一种具有适应任意环境的能力的通用程序和机器的理论，提 出用群体方法搜索以及选择、交换等操作策略的重要性。到7 0 年代，h o l l a n d 教授 又提出了遗传算法的