（控制理论与控制工程专业论文）求解jobshop车间作业调度的混合算法研究.pdf

摘要摘要作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s p ) 是一类满足任务配置和顺序约束要求的资源分配问题，是最困难的组合优化问题之一。有效的生产调度方法和优化技术的研究和应用是实现先进制造和提高生产效益的基础和关键。求解的方法以启发式算法为主，基于优先权规则，即从未排序的工序特定子集中选用工序的规则。鉴于精确方法仅适合于小规模问题，本文以混合算法来求解j o b s h o p 调度问题。主要工作如下：首先，通过对国内外作业车间调度问题的研究，介绍了已有的求解j o b s h o p调度问题的各种算法。其次，在阐述遗传算法基本概念、原理、方法的基础上，针对普通遗传算法在求解j o b s h o p 调度问题时，存在着收敛速度慢和易出现“早熟现象的缺点，提出算法混合思想。接下来分析了遗传算法和禁忌搜索算法及蚁群算法的优缺点，遗传算法能以较大概率找到全局最优，但局部搜索能力不强，对车间调度系统进行优化时需较长时间。禁忌搜索算法收敛较快，局部搜索能力强，但其收敛性和初值的选择有很大关系。蚁群算法的正反馈和并行搜索特点提高解的质量和稳定性，但算法时间长，且容易陷入局部最优解。本文提出了作业车间调度的混合算法。经过多次试验，发现在遗传算法完成后，直接选用遗传算法得到的最优解作为禁忌搜索的初始解进行计算得到的最终解和用遗传算法所得到的最终解相差无几，但平均进化代数减少，避免了遗传算法的早熟收敛。对于混合蚁群遗传算法由于遗传算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用却无能为力，当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低，蚂蚁算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并行全局搜索能力，但初期信息素匮乏，求解速度慢，算法是将遗传算法与蚂蚁算法融合，采用遗传算法生成信息素分布，利用蚂蚁算法求精确解，优势互补。最后通过对标准作业车间调度问题的测试，与传统算法进行比较，证明了本文的算法在求解j o b s h o p 调度问题方面有较好的效果。关键词：作业车间调度；遗传算法；禁忌搜索；蚁群算法a b s t r a c ta b s t r a c tj o bs h o ps c h e d u l i n gp r o b l e m ( j s p ) i so n eo ft h em o s td i m c u l tc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s w h i c ha l l o c a t e sr e s o u r c e si no r d e rt op e r f o r man u m b e ro ft a s k s ，s u c ha sh a s k sc o l l o c a t i n ga n do r d i n a lr e s t r i c t i o n t or e a l i z em o d e mm a n u f a c t u r ea n dp r o m o t ep r o d u c t i o ne f f i c i e n c y ，r e s e a r c ho ne f f e c t i v ep r o d u c t i o ns c h e d u l i n gm e t h o d sa n do p t i m i z a t i o nt e c h n i q u e sa n di t sa p p l i c a t i o na r e t h ef u n d a m e n t a la n de s s e n t i a lp r o b l e m s a se a r l ya si nt h e19 5 0 sm u c hr e s e a r c hh a v e b e e nd o n ea n dt h em a i ns o l v i n gm e t h o d sa r eh e u r i s t i ca l g o r i t h m s ，w h i c hb a s e do np r i 耐t y ，t h a t sa r r a n g i n go p e r a t i o n sf r o mt h es p e c i a ls u b s e t so fu n o r d e r e do p e r a t i o n s a st h ee x a c tm e t h o d sa r eo n l ys u i t a b l ef o rs m a l ls c a l ep r o b l e m sa n dt h ec o n s t r u c t i v em e t h o d sp e r f o r mp o o r l ya n dl a c kf l e x i b i l i t i e sa sw e l l t 1 1 i sd i s s e r t a t i o np r o p o s e sah y b r i da l g o r i t h mt os o l v ej s p t h em a i nr e s e a r c hw o r ki sl i s t e da sf o l l o w s ：f i r s t l y ，t h ed i s s e r t a t i o nr e v i e w sh i s t o r i c a ld e v e l o p m e n t so nj s pd o m e s t i c a l l ya n di n t e r n a t i o n a l l y ，i n t r o d u c e se x i s t i n gm e t h o d ss o l v i n gj s p s e c o n d l y ，b a s e do nt h ed e s c r i p t i o no fb a s i cc o n c e p t s ，t h e o r ya n df u n d a m e n t a lp r o c e d u r e t h ed i s s e r t a t i o np u t sf o r w a r dt h eh y b r i dg aw h 记hc o m b i n e st a b us e a r c h ( t s ) a n dg aa n da n tc o l o n yw h e nc o n s i d e r i n gt h ed i s a d v a n t a g e so ft h es t a n d a r dg ao nj s p ( e g p r e m a t u r ea n dl o wc o n v e r g e n c es p e e d ) f i n a l l y ，a n a l y z e dt h ee x c e l l e n c ea n df l a w so fg e n e t i ca l g o r i t h ma n dt a b us e a r c ha l g o r i t h m s g e n e t i ca l g o r i t h mc a l lf i n dt h eg l o b a lo p t i m i z a t i o nw i t ht h ep r o b l e m b u tt h ea b i l i t yo fl o c a ls e a r c hw e a k ，n e e dm o r et i m et oj o b s h o ps y s t e m t a b us e a r c ha l g o r i t h mc o n v e r g e n c ef a s t ，t h ea b i l i t yo fl o c a ls e a r c hs t r o n g b u ti t sa s t r i n g e n c yi sc o n c e r n e dw i t hi n i t i a lv a l u e a n tc o l o n ya l g o r i t h m ( a c af o rs h o r t ) i sp r o p o s e df o rj o b s h o ps c h e d u l i n gp r o b l e m ap r o b a b i l i t yp r i o r i t yi si n t r o d u c e df o rt h ei n i t i a ld i s t r i b u t i o no fa n t s m o r e o v e r , q u a l i t ya n dr o b u s t n e s so fs o l u t i o n sa r ei m p r o v e db yt l l en a t u r eo ff e e d b a c ka n dp a r a l l e lp a r a d i g mo fa c at or e m a i nt h ev i r t u e sa n dw e a k e nt h ef l a w so fg e n e t i ca l g o r i t h ma n dt a b us e a r c h ，t h eg e n e t i c t a b us e a r c hm i x t u r ea l g o r i t h mf o rr e a c t i v eo p t i m i z a t i o ni nj o b s h o pp r o b l e mw a sp r e s e n t e d b yr e p e t i t i o u st e s t ，d i s c o v e r i n gt h eo p t i m i z a t i o nr e s u l tg a i n e db yd i r e c t l ys e l e c t e dt h ec l a s s i cs o l u t i o no fg e n e t i ca l g o r i t h m sa st l l eo r i g i n a ls o l u t i o no ft a b us e a r c ha l m o s te q u a lt h eo p t i m i z a t i o nr e s u l tg a i n e db yu s i n ge v e r yu n i to ft h ef i n a l l ye r aa st h eo r i g i n a ls o l u t i o no ft a b us e a r c h ，b u tt h et i m ew a sc o n s u m e d l ys h o r t e n s om sa l g o r i t h mf i r s t l yu s e sg e n e t i ca l g o r i t h m st og e tt h ei n i t i a lv a l u eo ft a b us e a r c h ，t h en u s e st a b us e a r c ha l g o r i t h m st og e tt h eo p t i m a ls o l u t i o n a st h ea n tc o l o n ya l g o r i t h mf o rh y b r i dg e n e t i ca l g o r i t h mw i t hr a n d o mr a p i dg l o b a ls e a r c hc a p a b i l i t y ，b u tu s eo ft h ef e e d b a c kw a sp o w e r l e s st od oa n y t h i n g ，t os o l v ear a n g eo fi n a c t i o na r eo f t e nag r e a td e a lo fr e d u n d a n c yi t e r a t i o n ，a n de x a c ts o l u t i o n so fl o we f f i c i e n c y ，a n tc o l o n ya l g o r i t h mt h r o u g hp h e r o m o n e s ，a n dt h ec u m u l a t i v eu p d a t eo nt h ec o n v e r g e n c eo ft h eo p t i m a lp a t h , w i t ha大连交通大学j r 学硕士学位论文d i s t r i b u t e dp a r a l l e lg l o b a ls e a r c hc a p a b i l i t y ，b u tt h ei n i t i a ll a c ko fp h e r o m o n e s ，s o l v es l o w l y ，g e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h m sa r em i x e d ，a n di n t e g r a t i o na l g o r i t h mu s i n gg e n e t i ca l g o r i t h m st og e n e r a t ei n f o r m a t i o nd i s t r i b u t i o n ，u s eo ft h ea n ta l g o r i t h mf o re x a c ts o l u t i o n s ，c o m p l e m e n te a c ho t h e r f i n a l l y ，b yt e s t i n gt h es t a n d a r de x a m p l e st h ea n n o u n c e dm a k e sp a n sa r eo b t a i n e d ，w h i c hc a np r o v et h en e wa l g o r i t h m sb e t t e rp e r f o r m a n c eo nj s p k e y w o r d s ：j o bs h o ps c h e d u l i n gp r o b l e m ；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 tc o l o n ya l g o r i t h m大连交通大学学位论文独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成果，也不包含为获得太董塞通太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。本人完全意识到本声明的法律效力，申请学位论文与资料若有不实之处，由本人承担一切相关责任。学位论文作者签名：粥日期：矿年月z 矿日大连交通大学学位论文版权使用授权书本学位论文作者完全了解太整交通太堂有关保护知识产权及保留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属太董銮通太堂，本人保证毕业离校后，发表或使用论文工作成果时署名单位仍然为太董銮通太堂。学校有权保留并向国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查阅和借阅。本人授权太董銮通太堂可以将学位论文的全部或部分内容编入中国科学技术信息研究所中国学位论文全文数据库等相关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论、又。( 保密的学位论文在解密后应遵守此规定)猢黼张禳住日期： 们7 占年7 声月i 力日导师签名：日期： 州矿年i7 月) 伊日学位论文作者毕业后去向：幸晟彬身孕公太蕾礼孕多舾甭啦裥工作单位：审饿嘲翱船哟奄陬谰电话：通讯地址：电子信箱：邮编：izo ) ，引言引言迈入2 l 世纪。企业间竞争的加剧，必然迫使企业努力提高生产率，参与更激烈的市场竞争。目前，企业面临竞争的压力，大多采取的是采用更先进的设备改进生产结构，而制造过程的自动化水平提高，必然要求更加合理高效的生产调度与之相适应。依赖人来指挥生产加工过程的传统模式已经远远不能适应制造环境的需要，迫切需要研究有效的生产计划调度方法和建立实现这些生产计划调度方法的计算机生产计划调度管理系统。生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的生产调度方法和优化技术的研究和应用，是实现先进制造和提高生产效益的基础和关键。从上个世纪5 0 年代起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科学家的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法，研究并解决了一系列有代表意义的调度和优化问题。但是，人们普遍把c o n w a y ，m a x w e l l 和m i l l e r _ 三人有关调度的研究工作作为调度理论研究的正式开始，他f f 3 人也被人们称为调度理论的奠基人。此后3 0 多年的调度理论和应用研究都受到他们的影响。调度问题涉及面非常广泛，所以有很多种调度问题。根据加工系统的复杂度，生产调度可以分为单机调度、j o bs h o p 调度、f l o ws h o p 调度、o p e ns h o p 调度、多机器并行加工( km a c h i n e si np a r a l l e l ) 调度等几个基本类型。单机调度是指所有的操作任务都在一台机器上完成，需要对任务进行优化排队：j o bs h o p 调度是最一般的调度类型，它是指由m 台不同的机器加工n 个有特定加工路线( 顺序) 的工件，不同工件的工序间没有顺序约束，工序加工不能中断；f l o ws h o p 调度假设所有工件都在同样的设备上加工，并有一致的加工操作和加工顺序；多机器并行加工调度是指多台机器并行加工工件，而且并行加工的机器和工件都是类似的。实际的调度问题通常是上述几种调度类型的组合。本文主要研究求解j o b s h o p 车间作业调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s p ) 。j s p 是一种资源分配问题，这里的资源主要是指设备资源，问题的求解目标是要找到一个将一组工件安排到设备上去，以使作业可为“最优完成的方案。一个调度是按先后顺序条件将所有任务安排到设备上的一种方案。通常，约束的数目很大，使j s p 成为一个非常难解的组合问题( n p 完全问题) 。车间调度作为c i m s 体系结构中连接生产计划和生产控制层的中间环节，发挥两方面的重要作用：方面接受计划决策信息，在空间和时间上合理配置任务和资源，形成具体生产实施方案，驱动整个生产系统高效运作，保证计划的大连交通大学t 学硕十学位论文实现；另一方面，接受生产过程的实际信息，通过统计分析，有机协调整个生产系统，并向决策层反馈计划执行情况。2第一章车问调度第一章车间调度1 1 车间调度在企业生产中的重要性科学技术的发展为制造业的技术进步创造了条件，同时也使制造企业面临越来越激烈的竞争。企业必须在竞争中求生存，在竞争中求发展。传统制造业面临着新的机遇和挑战，为了能在市场竞争中立于不败之地，如何缩短产品上市时间，提高质量，降低成本是企业永无止境的追求，要做到这些，不仅需要生产过程的自动化，而且要求与生产过程相关的调度、计划、决策等也实现自动化。1 1 1 车间调度问题的定义车间调度就是对一个可用的d n i 机床集在时间上进行任务集分配，以满足一个性能指标集。典型的车间调度问题包括一个要完成的作业集，每个作业由一个操作集组成；各操作的完成需要占用机床或其他资源，并且必须按一些可行的工艺次序进行加工；每台机床可进行零件的若干操作。在约束条件下，调度的目标是将作业合理地安：b l b n 各机床，并合理安排作业的加工次序和加工开始时间，同时优化一些性能指标皿1 。在实际车间调度中，一般需要考虑两个方面的问题，一是生产作业的调度，二是生产资源的分配。本文考虑生产作业的调度，把资源问题当成约束来考虑。1 1 - 2 车间调度的重要性车间调度是制造系统生产管理的核心，生产管理任务j l r 页n 实施与完成，最终要靠合理的车间调度来保证。它研究的是如何合理配置加工过程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备利用率与生产效率，降低生产成本。车间调度对任务的交货时间、各项生产任务的生产周期、设备利用率和在制品占用量都有影响。因此，及时准确的车间调度对生产系统的高效运行有着重要的影响，主要表现在车间调度可以保证：生产计划的有效实施；高效低耗地使用生产资源；均衡生产，减少在制品的资金占用。所以，车间调度是制造业生产中最活跃和生产系统研究的前沿问题之一。1 2 车间调度问题概述1 2 1 车间调度问题的分类与特点车间调度问题的分类，根据研究的侧重点不同有不同的分类方法。( 1 ) 按照资源约束种类和数量，可分为：大连交通大学丁学硕十学位论文单资源车间调度( s i n g l er e s o u r c ec o n s t r a i n e d ) ：只有一种资源制约着车间的生产能力。在绝大多数的相关科技文献中，单资源一般指车间生产环境中，只有机床设备的数量不能同时满足所有可能可加工工序立即被加工的要求。双资源车间调度( d u a lr e s o u r c ec o n s t r a i n e d ) ：同时有两种资源制约着车间的生产能力。机床设备往往是制约资源之一，车间有时会缺乏有经验或一技之长的工人，也可能某种类型的刀具数量有限，因此这两种资源可以是机床设备和工人或刀具。车间中也常常会发生一些辅助资源有限的情况，如一个车间只有一辆或两辆自动物料运送车，然而需要同时传送的零件数量可能较多，在这种情况下，自动物料运送车也会成为制约车间提高生产能力的一个重要因素。同理，奇缺的刀具、夹具以及运送零件的叉车、吊车和货盘等都可能成为第二种制约资源。多资源车间调度( m u l t i p l er e s o u r c ec o n s t r a i n e d ) ：同时有两种以上的生产所需资源制约着车间的生产能力。这些资源包括员工、机床设备、机器人、物料运送系统和辅助资源，如货盘、夹具和刀具等。( 2 ) 按照零件和车间构成，可分为：作业车间调度( j o bs h o p ) ：在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。这是一种最典型的车间调度形式。流水车间调度( f l o ws h o p ) ：在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件依次从流水线的一端进入，最后从另一端流出瞄1 。开放车间调度( o p e ns h o p ) ：每个零件的工序之间的加工顺序是任意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。单车间调度( s i n g l es h o p ) ：在这种车间调度中，每个零件只能有一道工序。( 3 ) 按照加工特点，可分为：静态车间调度( s t a t i cs c h e d u l i n g ) ：所有的零件在开始调度时刻己经准备就绪。车间的调度不考虑零件在加工过程中出现的意外情况，如机床突然损坏、零件的交货期提前、有更紧迫的零件要求被加工等等。动态车间调度( d y n a m i cs c h e d u l i n g ) ：车间的调度要求考虑零件在加工过程中出现的各种意外情况。这种调度方法要求调度能随时响应车间加工能力的变化，在有突发事件出现后，能立即根据当时的车间加工能力，对待加工零件重新展开调度，以确保在任何时候，都能保持车间的加工性能指标处于最优或次优状态。车间调度问题有以下特点：4第一章车间调度( 1 ) 复杂性：一是生产因素的多样与复杂，二是车间调度问题是在等式或不等式约束下优化某些性能指标，在计算量上往往是n p 完全问题，因此，在求解车间调度问题上，一些常规的优化方法无能为力。( 2 ) 动态随机性：生产中会出现设备故障、产调度需要根据生产情况做出动态调整。( 3 ) 多目标性：车间调度往往是多目标的，成时间的目标、基于生产成本的目标等口1 。1 2 2 车间调度问题的研究现状急件插入、人员误操作等不可预见因素，生可分为基于作业交货期的目标、基于作业完调度问题的研究始于2 0 世纪5 0 年代，j o h n s o n 提出了解决n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的优化算法，代表调度理论研究的开始；6 0 蛰j 7 0 年代建立了调度理论的主体并重视调度复杂性的研究。随着7 0 年代后期调度理论研究的深入及各种交叉学科的发展，又涌现了许多新的车间调度理论和方法h 1 。我国“八五”期间也有一些高校和研究机构如清华大学、上海交通大学、西安交通大学、北京机械工业自动化研究所等进行此类问题的研究，并已开发出相应的计算机辅助生产调度与管理系统，逐步从理论研究阶段走向应用阶段。虽然对车间调度领域的研究已有几十年的历史，但至今仍是一个研究的热点和难点，存在的问题还很多：( 1 ) 车间调度很难形成一套系统的方法与理论，因为大多研究对约束问题考虑不是很周全，建模时对真实环境也进行了大量的简化，还不能很好地应用到实际生产中。( 2 ) 实际的生产系统是一个动态生产环境，即实际生产系统中存在着很多不确定性的变化，如加工设备的故障与维修造成的加工环境的变化，经常变化的市场需求所带来的任务变化，以及生产任务的变化导致所追求的生产目标的变化等。所以，实际的调度应该是动态调度，只用静态调度的理论解决问题不会达到最好的效果。( 3 ) 虽然针对车间调度问题开发了不少软件，但调度系统应用到生产实际中，和实际结合一定会有不如意的地方，所以调度系统再发达，也不可能完全忽略调度专家的作用。( 4 ) 多种调度方法结合的问题。在过去几十年中，人们将许多算法应用于调度领域，但是人们使用各种调度算法需要特定的应用环境，判断何种算法适合何种环境是一个很有现实意义的问题。经过5 0 多年的发展，车间调度问题的研究方法经历了从简单到复杂、从单- n 多元的过程。但由于车间调度的复杂性，至今尚未形成一套系统的理论与方法。大连交通大学工学硕十学何论文1 2 3 车间调度问题的研究策略由于调度问题的复杂性，其研究策略主要形成了以下几种：分解与成组策略：利用分解生产计划或成组技术的调度策略，可以大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。实时或动态重调度策略：车间制造过程的随机性、不确定性需要不断进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策略有：周期调度，事件驱动调度，周期与事件驱动的混合调度等。多目标权衡调度策略：实际调度问题往往是多目标的，而这些目标往往相互冲突。对此类多目标优化问题，常用数学规划中的约束法、评价函数法、分层序列法等。1 3j o b s h o p 调度问题1 3 1j s p 模型j o b s h o p 调度问题是许多实际生产调度问题的简化模型。j s p 研究刀个工件在小台机器上的加工。已知每个工件在各个机器上的加工次序和每个工件的各个工序的加工时间。要求确定与工艺约束条件相容的各机器上所有工件的加工开始时刻、完成时刻、加工次序，使加工性能指标达到最优。各个工件和机器应满足以下约束：( 1 ) 在整个加工过程中，每个工件只能被所有的机器都加工并且只加工一次；( 2 ) 各个工件必须按工艺路线以指定的次序在机器上加工；( 3 ) 加工过程不能间断；( 4 ) 每一时刻每一台机器只能加工一个工件。j o b s h o p 调度问题的求解就是要找到一个合理的安排使每个工件都能在满足工艺约束的条件下在各台机器上加工，使得总的加工时间最短。对于工件f ，c 破为第f 工件在机器k 上的完成时刻，f 廿为第f 工件在机器k 上的加工时间，如果机器h 先于机器砌口工工件f ，则应满足如下约束：c 业一f 腑c 曲如果机器k 先于机器办加工工件f ，则应满足如下约束：cl h ti i c 嗽定义变量x 掀，则：f 1 ，机器办先于机器砌口工工件，一1o ，否则则上述约束可表示为：6第一章车间调度c 腑一t 睹屹( 1 一x 曲) c 圻，i = 1 ，2 ，nh ，k = - 1 ，2 ，m其中上为一足够大的正数。对于在机器址加工的工件f 枇，如果工件f 先于工衔在机器忌上加工，则应满足如下约束：cl t ci k t 囔如果工佑先于工件f 在机器七上加工，则应满足如下约束：f i 一c 廿f 腑定义变量y 肼，则：f 1 ，机器厅先于机器砌口工工件，v ，= 0 t 暾i 0i = 1 ，2 ，刀拓l ，2 ，mx t h k2 0 0 r l ，i = 1 ，2 ，刀h ，肛1 ，2 ，my 嘛2 0 0 r l ，i ，_ ，= l ，2 ，刀k = - i ，2 ，m、，、j、，、，qg6大连交通大学t 学硕十学位论文1 3 2j s p 的表示1 ) 甘特图表示对于m 台机器( m a c h i n e ) m i ，m 2 ，m m ) ，z 个工件( j o b ) j t ，儿讥) 的加工过程，所谓调度就是分配各工件在各机器上的加工时间，调度通常用甘特图表示。甘特图( g a n t tc h a r t ) 是在2 0 世纪初由亨利甘特开发的。它基本上是一种线条图，横轴表示时间，纵轴表示机器。甘特图直观地表明任务计划在什么时候进行，以及实际进展与计划要求的对比。图1 1 为3 个工件3 个机器面向机器的甘特图。机器时闯图1 13 件工件3 台机器甘特图f i 9 1 13 j o b sa n d3 m a c h i n e sg a n t tc h a r t2 ) 析取图表示析取图是描述j s p 的常用工具，对于拧个工件、m 台机器( 共个工序) 的j s p ，所对应的析取图为g = 彳，剧。其中，哟所有工序构成的顶点集，包括目和历两个虚拟工序( 分别表示a nt _ 开始和结束) ；a 为，z 条子边构成的边集，子边( 实线) 表示某工件按约束条件在所有机器上从开始到结束的加工路径；e 为m 条子边构成的弧集，子弧( 虚线) 表示同一机器上加工各工序的连接。图1 2 为3 个工件3 个机器的一种可能的j s p 析取图表示。8第章乍间调度图1 23 件工件3 台机器析取图f i 9 1 23 j o b sa n d3 m a c h i n e sd i s j u n c t i o nm a p若以最大完成时间为指标，则对j s p 的求解就归结为到各弧( 即机器) 上作为优先决策的各工序的一组顺序( 即走向) ，当同一机器上有多个工序出现冲突时，上述顺序用于决定各工序的先后，最终得到各工序间没有冲突的一个有向非循坏图，其关键路径长度即为最大完成时间。1 3 3j s p 的复杂性算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和空间的需要量称为算法的时间复杂性和空阳j 复杂性。j s p 是经典的n p h a r d 问题，f 件工件 , 台机器的j o b s h o p 调度问题共有( n om 个可能解，即6 i 件6 机器的j o b s h o p 调度问题共有( 61 ) 6 = 1 4 宰1 0 ”个可能解。1 4 求解j o b s h o p 调度问题的算法研究现状自从j o h n s o n 首& 解决j o b s h o p 调度问题以来，经过众多学者的努力，提出了多种求解j o b s h o p 调度问题的算法，主要可以分为三类：精确算法、启发式算法和智能搜索算法。( 1 ) 精确算法精确算法主要是指数学规划方法，其通常采用整数规划、动念规划以及决策分析等方法来解决调度最优化或近似优化问题。生产调度中广泛使用的是混合整数线性规划9火连交通大学 ：学硕十学位论文( 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 ) 方法。用于求解调度问题的数学规划方法主要有分支定界法和动态规划等。分支定界方法通常是把全部可行解空间反复地分割为越来越小的子集( 称为分支) ，并且为每个子集的解值计算一个下界( 称为定界) 。在每次分支后，凡是界限超出已知可行解的那些子集不再作进一步分支，这样，解的许多子集就可以不考虑了。进行这种分支直到找出最优解为止。动态规划是另一种求解调度问题的重要数学规划方法。它将问题的整体按时间或空间的特性分成若干前后衔接的时空阶段，然后逐个加以解决，最后求出整个问题的最优决策序列。同时他们还提出了解决这类问题的“最优性原理”，根据这个原理，在求解的每一个阶段中，以后的最优策略只取决于当前的状态。这样就创建了求解最优化问题的动态规划方法。严格的说，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊的算法，因而不像线性规划那样有一个标准的数学表达式和明确定义的一组规划，一般需要对具体问题进行具体分析处理。数学规划方法在理论上能够求出问题的最优解，他们的有效性当然是最高的，适应范围也比较广，几乎能适应任何一种调度问题，但是计算复杂性很差( 算法复杂度为指数函数) ，这使得它们的计算规模容易受问题规模的限制，即使用来验证其他算法时，也是在小规模问题上验证，因此难以得到实际的应用，所以人们主要将之同其它一些算法混合起来使用。( 2 ) 启发式算法启发式算法是一种根据已有的信息进行推理和计算，从而获得近似最优解的方法，用于调度问题求解的启发式调度算法主要有调度规则、启发图搜索算法和拉格朗日松弛算法。调度规则：调度规则也称为调度规划、分派规划、优先级规则或启发式规则，是一类简单的启发式方法，其本质是按照规则从尚未调度的工序的一个子集中提取任务。调度规则是最经典的调度算法，由于其简单、易于实现、计算复杂度低，并且能用于动态实时调度，许多年来一直受到学者们的广泛研究，并不断涌现出新的调度规则。经过多年的研究，学者们提出了多种分配规则。p a n w a l k a r 和i s k a n d e r 阳1 于1 9 7 7 年总结了1 1 3 个分配规则，包括简单分配规则和组合分配规则，其中常用的列举如下：a ) 简单分配规则：1 0第一章车间调度i s p t ( s h o r t e s tp r o c e s s i n gt i m e ) ：即选择加工时间最短的工序。i i l p t ( 1 0 n g e s tp r o c e s s i n gt i m e ) ：即选择加工时间最长的工序。i i i ff c f s ( f i r s tc o m ef i r s ts e r v e ) ：即选择同台机器上工件队列中最先的工序。i v e f t ( e a r l yf i n i s ht i m e ) ：即选择完成时间最短的工序。v l f t ( 1 a t ef i n i s ht i m e ) ：即选择完成时间最长的工序。v i m w r ( m o s tw o r kr e m a i n i n g ) ：即选择总剩余加工时间最长的工件。v i i m n o r ( m o s tn u m b e ro f o p e r a t i o n sr e m a i n i n g ) ：即选择总剩余工序数最多的工件。v i i i f n o r ( f e w e s tn u m b e r so f o p e r a t i o n sr e m a i n i n g ) ：即选择总剩余工序数最少的工件。i x e d d ( e a r l yd u ed a t e ) ：即选择交货期最早的工件。x 。凡d o m ( r a n d o m ) ：即随机选择。b ) 组合分配规则i f c f s s p t ：即对等待时间超过约定时长的工件使用f c f s 规则，如果所有等待调度的工件等待时间小于约定时长则使用s p t 规则。i i l p t s p t ：即等待的工件数少于一定的数量就使用l p t 规则，否则，使用s p t 规则。c h a n g 等旧1 于1 9 9 6 年使用线性规划模型对4 2 条规则进行了评估，结果显示s p t 规则性能最好，而l p t 性能最差。启发图搜索算法：启发图搜索算法是经典人工智能领域中图搜索策略的一种。所谓的图搜索策略，就是把问题求解过程用图或树的结构来描绘，即图中的每一个节点代表一个问题的状态，节点间的弧代表应用的规则，那么问题的求解空间可以用隐含图来描述。图搜索方式就是采用某种策略选择应用规则，并把状态变化过程用图结构记录下来，一直到得出解为止，也就是从隐含图中搜索出含有解路径的子图来。但是，对于图搜索算法，如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。在所有求解j o b s h o p 调度问题的启发式方法中，由a d a m s 、b a l a s 和z a w a 伽于19 8 8 年提出的移动瓶颈方法是目前最好的方法之一，它将各个机器逐一排列，每一时刻在未排列的机器中定义一台机器为瓶颈，当一台新机器被排列时，所有先前已经建立的排列将被再次优化。其中，瓶颈的确定和局部再优化过程基于重复解决某一个单机调度问题( 即原问题的一个松弛) 而进行。显然，该方法的性能依赖于瓶颈的定义和各瓶颈机器的排列顺序。拉格朗日( l a g r a n g e ) 松弛算法：拉格朗日松弛算法是由e v e r e t t 提出的一种求解复杂优化问题的近似算法，它是将原问题中的某些约束吸收到目标函数当中，使松弛后的新问题在多项式时间内求得最优大连交通大学t 学硕十学位论文解，这个最优解能够逼近原问题的最优解。拉格朗同松弛算法分成两阶段：次梯度优化和可行化。前一阶段的次梯度优化主要是对问题进行松弛处理，当计算结果是不可行解时，进入后一个阶段进行可行化。拉格朗日松弛算法出于其能在较短的时间内获得高质量的次优解，并能进行性能评价等优点，受到了学术界的广泛重视，近年来已经成为解决复杂车间调度问题的一种重要的方法，血i l u h 等在研究并行机器调度时使用了拉格朗日松弛技术。熊锐等用这种方法求解了集成车间计划与调度问题。( 3 ) 智能搜索算法智能搜索算法是一类模仿自然界的某些演化机制的算法。主要有人工神经网络方法、进化算法、模拟退火算法和禁忌搜索算法等。人工神经网络：人工神经网络( a n n ) 是模仿生物脑结构和功能的一种信息处理系统。虽然目前的模仿还处于低级水平，但己显示出一些与生物脑类似的特点：大规模并行结构，信息的分布式存储和并行处理，具有良好的自适应、自组织性和容错性，具有较强的学习、记忆、联想和识别功能等。神经网络己在信号处理、模式识别、目标跟踪、机器人控制、专家系统、组合优化和网络管理等众多领域的应用中获得了引人注目的成果。人工神经网络已经被用于求解调度问题，国内如张长水等。于海滨，叶飞帆等提出的基于h o p f i e l d 模型的f 1 0 w s h o p 排序方法，大部分结果于最优结果相当逼近，有的还达到了最优解，然而随着问题规模的扩大，其各种指标缓慢下降的趋势。人工神经网络的效率受训练影响很大，并且在问题规模较大时，存在计算速度慢与结构参数难以确定的弱点。模拟退火算法( s a ) ：s a 最早f l j k i r k p a t r i e k 等在1 9 8 3 用来求解组合优化问题，它是首先引进跳出局部极小值陷阱机制的算法。算法的基本步骤是首先建立一个初始解( 随机或者是启发式构造)并且设置一个初始温度歹；然后在当前解s 的邻域n ( s ) 中产生一个候选解j ，如果f ( s ) f ( s ) ，那么s 替代s ，否则构造一个关于丁和f ( s ) - f ( s ) 函数，用它们作为接受的概率，这个函数一般选用b o l t s m a l l 分布函数e x p ( 一上堕掣) 。as a 以概率m i n 1 ，e x p ( 一竺) ) 来接受新状态，其中为新旧状态的目标差值，为温t j度。算法保留了向优良解概率l 的趋化过程，同时容许搜索接受比当前质量差的解，以1 2第一章车间调度避免搜索陷入局部极小值陷阱，但它们的接受概率在逐步减少。k o l o n k o l l 2 】将模拟退火算法运用至l j j o b s h o p 调度问题的求解上，取得了很好的成果。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，难以用于实时动念调度环境。禁忌搜索算法( t a b us e a r c h ，t s ) ：g l o v e r n 踟n 钔首先提出了禁忌搜索算法的基本思想：禁忌搜索算法一方面通过领域搜索从先前的局部最优点出发继续搜索，另一方面通过设置禁忌表( t a b ul i s t ) 来阻止搜索过程回到已经搜索过的解；另外，通过设置藐视准则来奖励和赦免一些优良状态( 例如判断状态是否优于“b e s ts of a r ”状态) 。禁忌搜索过程中产生的新解不是在当前解的邻域中随机产生的，而是优于“b e s ts o陆”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。d e l l a m i c o等n 朝于1 9 9 3 年提出了一种有效禁忌搜索算法来求j o b s h o p 调度问题，得到了f t l 0 的最优解。禁忌搜索算法受到了中外许多学者的重视，女u l a