（机械制造及其自动化专业论文）基于改进遗传算法的混合车间调度问题研究.pdf

硕 j 学位论文 摘要 并行工程( c o n c u r r e n te n g i n e e r i n g ，c e ) 、敏捷制造( a g i l em a n u f a c t u r e i n g ，a m ) 、虚拟制造( v i r t u a im a n u f a c t u r i n g ，v m ) ，网络化制造( n e t m a n u f a c t u r i n g ，n m ) 等作为现代化企业主导的先进制造模式，其目的是要以 最低的成本制造出顾客满意的产品。在这些制造模式下如何运用有限的资 源，降低产品的生产成本，缩短产品的制造周期，保证按时交货，提高企业 信誉，赢得更多客户，合理的调度方法与优化技术成为制约以上目标实现的 关键因素，因而车间调度问题也越来越受到学者们的关注。 遗传算法( g e n e t i ca l g o i r t h m ，g a ) 是一类借鉴生物界自然选择和自然遗 传机制的随机搜索算法，因其对优化模型的依耐性不强、求解问题的简单性 和鲁棒性等特点被广泛应用于制造业的各个领域。本文在对遗传算法进行改 进的基础上，围绕混合车间的调度问题进行了研究。 本文主要作了如下工作：文章回顾和总结了车间生产调度问题发展的概 况，以遗传算法为线索，以制造系统调度问题及其相关问题为背景，阐述了 遗传算法调度问题及其相关问题的数学模型：首先针对j i t 作业车间多种工 艺路线的工件调度问题，考虑到生产过程中受许多因素的影响，采用多目标 分层协调策略，建立了柔性多目标函数模型，在混合遗传算法与拉格朗日松 弛算法结合的基础上，提出一种混合改进算法，利用遗传算法更新拉格朗日 乘子得到问题的最优解，仿真实例验证了该模型与求解方法是现实可行的； 其次针对具有多种工艺路线的混合柔性流水车间最小完工时间问题，结合生 产工艺计划与车间调度系统的集成原理，建立了目标模型，通过将简单遗传 算法加以改进，对算法进行研究，把改进后的遗传算法( s g a ) 和模拟退火算法 ( s a ) 有机结合，优化了算法的融合机制和互补结构，形成了较为高效的混合优 化算法，使问题得到求解，给出具体算例，验证算法的有效性和先进性。另 外结合面向对象的方法，基于组件和线程技术，设计了一个应用于实际生产 的优化调度系统模块，介绍了调度系统基于多层次b s 结构的系统结构，并 对系统的业务逻辑作了详细阐述，说明了生产调度管理系统的数据库开发过 程：本文最后对下一步基于改进遗传算法的混合车间生产调度问题将要进行 的工作进行了展望。 关键词：柔性：车间调度：jit ：遗传算法：模拟退火 a b s t r a c t c o n c u r r e n t e n g i n e e r i n g ，a g i l e n e t w o r k - b a s e d m a n u f a c t u r i n g a sa m a n u f a c t u r i n g ， v i r t u a l m a n u f a c t u r i n g ， m o d e r nb u s i n e s ss u c h a sa d v a n c e d m a n u f a c t u r i n gm o d e l ，t h ea i mi st op r o d u c et h e1 0 w e s tc o s tp r o d u c to fc u s t o m e r s a t l s t a c t l o n i nt h e s em a n u f a c t u r i n gm o d e lo fh o wt ou s eo u rl i m “e dr e s o u r c e s 1 0 w e rp r o d u c t i o nc o s t s ，r e d u c et h em a n u f a c t u r i n gc y c l et oe n s u r eo n t i m ed e l i v e r y ， i m p r o v ec r e d i b i l i t y ， w i nm o r ec u s t o m e r s ， ar e a s o n a b l em e t h o do f s c h e d u l i n g c o n s t r a i n t sa n do p t i m i z a t i o nt e c h n o l o g yt oa c h i e v et h e s eo b i e c t i v e sk e yf a c t o r s ， w h i c hs h o ps c h e d u l i n gp r o b l e m sa r em o r ea n dm o r ea t t e n t i o nb vs c h o l a r s g e n e t i ca l g o r i t h m ( g e n e t i ca l g o i r t h m ，g a ) i sak i n do fl e a r nf r o mb i o l o g i c a l n a t u r a ls e l e c t i o na n dn a t u r a lg e n e t i cm e c h a n i s m so fr a n d o ms e a r c ha lg o r i t h m ， w h i c ha c c o r d i n gt ot h eo p t i m i z a t i o nm o d e lo fp a t i e n c ei sn o ts t r o n g ，t os o l v et h e p r o b l e mo fs i m p l i c i t ya n dr o b u s t n e s so ft h ec h a r a c t e r i s t i c so fw i d e l vu s e di na l l a r e a so 士 m a n u 士a c t u r l n g i nt h i s p a p e r ，g e n e t i ca l g o r i t h mo nt h eb a s i so f l m p r o v e m e n t sa r o u n dt h ei s s u eo fm i x e ds h o ps c h e d u l i n gi ss t u d i e d i nt h i sp a p e r ，t h ef o l l o w i n gw o r k ：t h ea r t i c l er e v i e w sa n ds u m m a r i z e st h e w o r k s h o pp r o d u c t i o no fa no v e r v i e wo ft h ed e v e l o p m e n to fs c h e d u l i n gp r o b l e m s 。 f o rc l u e st ot h eg e n e t i ca l g o r i t h mt os c h e d u l i n gp r o b l e mo fm a n u f a c t u r i n gs y s t e m s a n dr e l a t e di s s u e sa st h eb a c k g r o u n do nt h es c h e d u l i n g p r o b l e mo ft h eg e n e t i c a l g o r i t h ma n di t sm a t h - r e l a t e di s s u e sm o d e l ；n r s to fa l l ，f b rav a r i e t yo fj o b s h o p j i tp r o c e s sw o r k p i e c el i n es c h e d u l i n gp r o b l e m ，t a k i n gi n t oa c c o u n tt h e p r o d u c t i o n p r o c e s si sa f f e c t e db ym a n yf a c t o r s ，t h ec o o r d i n a t i o no fam u l t i t i e r e ds t r a t e g y o b j e c t i y e s ，t h ee s t a b i i s h m e n to faf l e x i b l em u l t i o b i e c t i v ef u n c t i o nm o d e l t h e h y b r i dg e n e t i ca l g o r i t h mw i t ht h er u g b yl o n gd a yo fr e l a x a t i o na l g o r i t h m sb a s e d o nah y b r i da 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 mt ou p d a t el a g r a n g em u l t i p l i e r so f t h eo p t i m a ls o l u t i o nh a sb e e nt h ep r o b l e m ，t ov e r i f yt h es i m u l a t i o nm o d e la n d m e t h o dw a sf e a s i b l ea n dp r a c t i c a l ；f o l l o w e db yt a r g e t e dam i x t u r eo fav a r i e t yo f f 。l e x i b l ep r o c e s sr o u t e st h es m a l l e s tc o m p l e t i o nt i m en o w s h o pp r o b l e m ，c o m b i n e d w i t ht h ep r o d u c t i o np r o c e s sp l a n n i n ga n ds h o ps c h e d u l i n gs y s t e m ，t h ep r i n c i p i eo f i n t e g r a t i o n ，t h ee s t a b l i s h m e n to ft h et a 唱e tm o d e l ，b yas i m p l eg e n e t i ca l g o r i t h mt o l m p r o v et h ea l g o r i t h mt o s t u d yt h ei m p r o v e dg e n e t i ca l g o r i t h m( s g a )a n d s l m u l a t e da n n e a l i n ga l g o r i t h m ( s a ) c o m b i n a t i o no fa l g o r i t h m st o o p t i m i z et h e i n t e g r a t l o no 士c o m p l e m e n t a r ym e c h a n i s m sa n ds t r u c t u r e s ，t h ef o r m a t i o n0 fam o r e e f f i c i e n th y b r i do p t i m i z a t i o na l g o r i t h mf o rs o l v i n gt h ep r o b l e m ，s p e c i n ce x a m p l e s a r eg i v e nt ov e r i f l yt h ee f f e c t i v e n e s so fa l g o r i t h m sa n da d v a n c e ds e x u a l a n o t h e r m e t h o do fc o m b i n i n go b j e c t - o r i e n t e d ，t e c h n o l o g y b a s e dc o m p o n e n t sa n dt h r e a d s ， a na p p l i c a t i o nd e s i g n e dt o o p t i m i z et h ea c t u a lp r o d u c t i o ns c h e d u l i n gs y s t e m m o d u l e s ，i n t r o d u c e dt h em u l t i l e v e ls c h e d u l i n gs y s t e mi sb a s e do nb ss t r u c t u r e o ft h es y s t e ms t r u c t u r e ，t h eb u s i n e s sl o g i co ft h es y s t e mm a d ead e t a i l e d d e s c r i p t i o no ft h ep r o d u c t i o ns c h e d u l i n gm a n a g e m e n ts y s t e mo ft h ed a t a b a s e d e v e l o p m e n tp r o c e s s ；t h ee n do ft h i sa r t i c l et h en e x ts t e pt oi m p r o v et h eg e n e t i c a l g o r i t h mb a s e do n am i x t u r eo fw o r k s h o pp r o d u c t i o ns c h e d u “n gw o r kt ob e c a r r i e do u ti nf l l t u r e k e y w o r d s ：f l e x i b l e ；j o bs h o ps c h e d u l i n g ；j i t ；g e n e t i ca l g o r i t h m ；s i m u i a t e d a n n e a l i n g i i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 、黑飞淞日期：y 卞g 月c 1 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 作者签名：r 龟南 导师签名：晰乏一l 日期：m o 、年( 月弋日 日跏尹二月夕日 硕 ：学位论文 第1 章绪论与综述 1 1 课题研究的背景、意义 随着科学技术日新月异的变化，尤其是以电子技术、信息技术、自动化技 术、计算机与网络技术、人工智能技术和新材料技术的迅速发展，市场全球化 进程正在形成，市场响应的快速化、产品的客户化等要求促使制造业必须采用 先进的制造模式来组织生产。在这种时代背景下，快速响应、瞬息万变的市场 需求成为制造系统赢得市场竞争的焦点，因此产生了许多先进的制造系统模 式，如并行工程( c o n c u r r e n te n g i n e e r i n g，c e ) 、敏捷制造 ( a g i l e m a n u f a c t u r i n g ，a m ) 、虚拟制造( v i r t u a im a n u f a c t u r i n g ，v m ) 等。 先进制造模式( a d v a n c e dm a n u f a c t u r i n gm o d e ，a m m ) 是指在生产制造过程中， 依据不同的制造环境，通过有效的组织各种制造要素形成的，可以在特定环境 中达到良好制造效果的先进生产方法。这些先进的生产模式能否被成功运用在 生产实际中，关键是有没有合理的调度方法与优化技术的支撑。车间生产调度 问题也就越来越成为制造业中研究的焦点。 什么是车间调度呢? 车问调度主要是针对一项可分解的工作( 如产品制 造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下， 通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加 工的先后顺序，以获得产品制造时间或成本的最优化。有关资料表明，制造过 程中9 5 的时间消耗在非切削过程中心1 ，合理的建模、有效的调度方法与优化 技术可以更好地解决工件在机器上的调度和资源分配，实现车间调度的合理 化、自动化、集成化：可以实现对生产过程中的物流和信息流的综合管理，使 前后工序紧密衔接，保持物流的一贯性：可以提高设备的生产效率，减少工序 等待时间，降低物料的消耗，减少库存，缩短交货期，降低成本，提高产品竞 争力。因此，在制造业中，车间调度已经成为实现先进制造系统运筹学技术、 管理技术与组合优化技术发展的核心n 】。 车间调度也是企业日常生产活动中必不可少的重要组成部分，随着企业生 产模式的改变，生产调度问题也在不断发生变化。为了适应这种变化，制造企 业的生产经营模式也发生了新的改变：( 1 ) 产品开发周期显著缩短，上市时间 更快，这是2 1 世纪市场环境和用户消费观所要求的，也是赢得竞争的关键所 在。例如，美国制造业的策略从2 0 世纪5 0 年代的“规模效益第一”，经过7 0 年代和8 0 年代的“价格竞争第一和。质量竞争第一”发展到9 0 年代的“市 场速度第一。可见时间的因素被提到了首要位置。( 2 ) 具备赢得竞争，提高 市场占有率的四种基本能力：时间竞争能力，产品上市快、生产周期短、交 货及时；质量竞争能力。产品不仅可靠性高，而且使用户在各方面都满意； 琏丁改进遗传算法的混合车问生产调度问题研究 价格竞争能力。产品生产成本低，销售价格适中：创新竞争能力。产品有 特色、生产有柔性、竞争有策略。( 3 ) 柔性更加提高，以响应“瞬息万变、无 法预测”的市场。企业不仅要具备技术上的柔性还要具备管理上的柔性，以及 人员和组织上的柔性。( 4 ) 全生命周期内的质量保证。产品质量的完整概念是 顾客的满意度。对产品质量更全面的理解是：用户占有使用产品的一种综合主 观反映，包括可用、实用、耐用、好用。( 5 ) 企业的组织形式将是跨地区跨国 家的虚拟公司或动态联盟。( 6 ) 生产过程更加精良。产品开发生产、销售、维 护过程更加简化，生产工序更加简单，从而降低成本、提高劳动生产率、缩短 上市时间。( 7 ) 人员的素质更加提高。21 世纪制造业要求全体职工具有更高的 技术管理和协作素质。( 8 ) 智能化程度更高。在产品设计和制造过程中广泛应 用人工智能技术，各种设备的智能化程度大大提高。在上述这些变化下，车 间调度问题的研究更加成为当今科学研究的热点。 由于大多数车间调度问题属于一类n p 困难组合问题，因此寻找具有多项式 复杂性的最优算法几乎是不可能的哺1 。各种近似启发式方法、诸如基于规则的 算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调 度中，但其往往对所得的调度解的次优性不能进行评估。因此在这方面有必要 探索更好的近似最优调度算法。各种基于统计优化的方法、诸如遗传算法、模 拟退火法等拍，提供了一种解决调度优化问题的新途径，这方面也需要做进一 步的研究。过去的几十年里，基于对实际问题及理论上的考虑，调度问题激励 着人们不断寻找新的算法来提高制造业的市场竞争性。好的生产调度技术能提 高资源的利用率和操作管理水平，生产出具有竞争力的产品。车间的调度优化 工作，因其在提高生产效率，降低生产成本等方面所起的重要作用，正越来越 受到学者们的关注，也是本课题的研究意义所在。 1 2 车间调度问题国内外研究现状 1 2 1 车间调度问题的分类、特点及有关符号的含义 在了解后面的内容之前，有必要对车间调度问题的分类、特点及有关符号 的含义进行了解，以方便对后续内容的理解。 对于车间调度问题，g r a v e s 等人对其进行了分类整理 1 。按照不同的分类 标准，可分为以下6 种类型：开环车间( o p e ns h o p )和闭环车间( c l o s e s h o p ) 。单台处理机( s i n g l ep r o c e s s o r ) ，多台并行机(m u l t i p a r a l l e l p r o c e s s o r s ) ，f l o ws h o p 和j o bs h o p 。基于调度费用和调度性能的指标。 确定性调度( d e t e r m i n i s t i cs c h e d u l i n g ) ，随机性调度( s t o c h a s t i c s c h e d u l i n g ) 。静态调度( s t a t i cs c h e d u l i n g ) ，动态实时调度(d y n a m i c s c h e d u l i n g ) 有序加工，无序加工。现代车间调度类型往往是j o bs h o p 型f l o w 2 硕 ：学位论文 s h o p 型，因此，后面的内容主要围绕这两种类型的调度问题展开。其具有以下 特点：建模复杂性。计算复杂性。动态随机性。多约束性。多目 标性。 处理机、任务或作业和目标函数三要素组成了调度问题。处理机的数量、 类型和环境有近十种情况，任务或作业和资源的约束条件更是错综复杂，再加 上度量不同指标的目标函数，形成了种类繁多的调度问题。为了描述方便，用 g r a h a m 等人陋1 首先使用的三元组来描述调度问题的种类，这样大大简化了调 度问题的表示。三元组记号由三个域组成：aiply 。它们具有下面的含义。 口域表示处理机的数量、类型和环境，它可以为： 1 ：单处理机。 ：聊个同速机。 绒：脚个恒速机。 j i c 。：删个变速机。 ：朋个处理机，流水作业。 d 矗：历个处理机，开放作业。 以：m 个处理机，异顺序作业。 腰：j 类处理机，柔性流水作业。 p 域表示任务或作业的性质、加工要求和限制，资源的种类、数量和对加 工的影响等约束条件。它同时可以包含多项，可能的项主要有： ，；：任务有不同的到达时间。 表示在弓和瓦之间的切换时间( s e t u pt i m e ) 。 脚：加工时可中断。 胛c ，c 加f 船，i n t r p p ，d 甜舭p ：表示任务的相关性，分别表示一般优先约束、链、 入树和出树。 鸩：处理机资格限制。当处理机环境是平行机时，鸩可能出现在卢域中。 当哆出现在卢域中时，不是所有的处理机都能加工任务乃，鸠表示能加工任 务丁，的处理机集合。如果p 域中不出现m ，r 可以在任意处理机上加工。 6 ，捌伽，l ：机器故障表示机器不能连续被使用。在确定性调度中，机器的不 可用时间是固定的。对于同速机，可用的机器数在任何时刻都是时间的函数。 胛“：这个约束只能出现在流水作业中。当p 删甜出现时，作业按先进先 出的原则进行：所有作业的每一道加工顺序性同。 6 ，d 础：阻塞现象只能出现在流水作业中。如果在两个相邻的机器之间有一 个容量有限的缓冲区，当缓冲区被占满时，上流的机器就不能释放加工完的作 基】改进遗传算法的混合下问生严测发问题研究 业，即被加工完的作业阻塞在上流机器上。这就是零缓冲区。 删，：不等待限制只能出现在流水作业中。 陀伽：循环指可以出现在异序作业环境，它表示作业可以多于一次的访问 同一处理机。 ，域表示要优化的目标函数，它可以是 c m 。：时间表长，表示最后一个被加工完任务的完工时间。 k 瓤：最大延误时间。 q ，q ：总完工时间，加权总完工时间。 q ，一q ：总误工，加权总误工。 q ，_ q ：误工任务数，加权误工任务数。 1 2 2 调度问题国内外研究现状 1 9 世纪末2 0 世纪初，内燃机的广泛应用引发了制造业的变革，制造业进 入了以兵器工业和汽车制造业为代表的大批量生产时代，出现了流水生产线， 2 0 世纪2 0 至4 0 年代制造业出现了机群式生产模式阳1 ，但在当时，生产调度主 要依靠经验进行，没有自成体系的理论支撑。自2 0 世纪5 0 年代初期，应用数 学、运筹学、工程技术等领域的学者才开始对制造过程中的调度问题进行大量 研究。在研究的初期阶段，调度问题是作为一个纯粹的数学问题加以研究，5 0 年代早期，针对f s s p ( 流水车间调度) 问题，s m j o h n s o n 【l 们提出了解决 n 2 f c m a x ( n 个工件2 台机器的f l o w s h o p 型调度的最小流程周期问题) 和部 分特殊的n 3 f c m a x 问题有效的j o h n s o n 规则，虽然只是针对流水作业的求解 方法，但它对以后的研究有很大的影响此后相继有利用多项式时间算法求解 2 谳m a x ，j 2lj s 2ic m a x 和j 2it i - 1ic m a x 等特殊的j s s p ( 作业车间调度) 问题，这些研究奠定了经典调度理论的基础，标志着调度理论研究的开始。 最早的调度问题是单机问题，同时也是最简单的调度问题。首先单机调度 问题比较容易求出解决方案，这些方法对于研究比较复杂的调度问题具有指导 作用，可以为处理复杂调度问题提供近似算法；19 5 5 年，j a c k s o njr 针对生 产线上单机调度问题的最小延缓时间做了深入的研究，提出了分派规则n 1 j 。 19 5 6 年，s m i t hwe 对基于多最优的单阶段生产调度问题进行了研究n 引。19 7 3 年l a w l e rel 研究了具有优先约束的单机最优调度，讨论了加权总完工时间 最小的优先调度规则n 引。1 9 7 4 年，b a k e r 对单机作业情况下工期和最早开工时 间最小延迟调度问题进行了详细论述n 劓。1 9 7 5 年，m c m a h o n 等讨论了具有准备 时间和完工日期最短的调度问题n5 1 ，19 7 6 年，l a g e w e gbj 等人研究了单机情 4 形j 学位论文 况下的最短延迟调度问题n 引。随后这类问题一直被作为研究的重点，1 9 7 7 年， l e n s t r ajk 等人，1 9 7 8 年l a w l e rel ，1 9 9 1 年，b u r b r i g ejl ，1 9 9 3 年，b l a z e w i c z 等人，1 9 9 8 年，罗成新，赵玉芳等又从不同角度研究讨论了单机调度问题 。 平行机调度问题是调度中重要的一类问题，其中包括不可中断时间表长问 题，可中断时间表长问题及总完工时间问题。l9 6 1 ，h utc ，19 6 6 ，g r a h a meg 从不同方面对不可中断时间表长问题进行了深入的理论研究引。19 9 7 年，赵 传立等人研究讨论了处理机具有不同开始加工时间的可中断调度问题，此外还 有许多学者在这方面做了大量研究，这里不一一列举。 车间作业调度问题包括同顺序作业调度问题、自由作业调度问题和异顺序 作业调度问题。这类也是研究中涉及最多的问题之一，另外，流水问题也是一 类特殊的作业车间调度问题。1 9 6 5 年，针对j s s p 问题，l o m n u c k i n 训提出了分 支定界法，其主要思路是首先求解整数规划的伴随规划，如果求得的最优解不 符合整数条件，则增加型的约束缩小可行域；将原整数规划问题分支，分为两 个子规划再解子规划的伴随规划，通过求解一系列子规划的伴随规划及不断的 定界。最后得到原整数规划问题的最优解。1 9 6 8 年，g o l o m b 心们等人又提出了 回朔法用来求解j s s p 问题，它的思路是不断切割原问题规划的可行域，使它 在不断缩小的过程中将原问题的整数最优解逐渐暴露且趋于可行域极点的位 置。随后几年，车间调度理论主要围绕着整数规划、动态规划、分枝定界等这 些方法进行，研究并解决了一系列有代表性的调度问题。 由于调度问题本身的复杂性，后来人们逐渐着手寻找更有效的求解方法， 到6 0 年代后期，对于复杂的调度问题，人们开始研究用启发式方法加以解决， 至此调度理论的主体结构基本建立起来。从7 0 年代开始，随着复杂性理论 ( c o m p l e x i t yt h e o r y ) 及n p 一完全问题( n p c o m p l e t e ) 研究的兴起，人们开始注意 并重视调度问题的复杂性研究，证明了许多调度问题是n p 难的( n p - h a r d ) ，即 使简单的j o b s h o p 和f l o w s h o p 问题也是n p 难的，不存在有效的多项式求解 方法，因此只好寻找有效的启发式方法来解决它们，针对不同的问题，人们提 出了大量的启发式算法心2 2 3 h 2 钉。到7 0 年代后期，对调度问题的研究深入，已 作为一门应用数学分支，经典调度理论己逐渐成熟心5 】【2 引。主要侧重计算复杂性 方面的研究，l e n s t r a 等心证明了3 名允c m a x ，j 2ij 5 3 c m a x 和j 3lj s 2i c m a x 三种情况都是n p 难问题b a l a s 心引最早提出j s s p 问题的b & b 算法，此后c a r l i e r 等他引基于j a c k s o n 们的剩余总加工时间最长( m w r ) 规则提出预占先调度( j p s ) 用来求解j s s p 问题，并且取得了较好的结果“ 针对传统j s s p 问题，以运筹学方法研究为解决问题的重点，即研究如何 在m 台处理机床上安排n 个j o b 的处理顺序和处理时间，以使某个目标函数( 调 度长度，拖期惩罚) 极小化。调度长度极小的调度问题可用混合整数线性规划 来求解，但由于约束和整数变量随着问题规模的增加而变得很多，所以只适合 较小规模的调度问题。动态规划法隐含枚举整个空间的搜索方法，它把问题分 解成若干步，然后在每步上搜索最优解它是求解小规模问题的有效算法但它 基于改进遗传算法的混合车问牛产调度问题研究 对组合的需要随问题的规模指数增长，以至求解大规模问题成为不可能1 。 1 9 9 8 年，吴少岩，纪树新等在文献口2 3 3 1 中提出了不同的分支定界法，使得分 支定界法成为求解许多调度问题很有希望的方法，因为它常常可为部分路径 计算很强的下界，所以它成了求解大型组合问题为数不多的方法之一。基于 运筹学方法的研究，这方面的详细论述我们可以参考文献制。值得注意的是， 在用o r 方法研究调度问题时，一般都是寻求调度特例的多项式时间的最优算 法，近似算法或启发式算法。上面的分支定界法在下界精确的情况下是一种精 确最优解。反之，当下界不十分精确时，它就是一种近似解。 二十世纪八十年代初，调度研究转向应用研究阶段副凹6 i 。以f o xms 发表 的文章为标志，开始了人工智能方法( a i ) 在j s s p 调度问题中的研究应用7 1 。 a i 方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。它 主要利用启发式规则来引导搜索并提供有效的搜索程序去寻找复杂问题的较 优解，主要包括以下各方面的内容：一个是启发式搜索规则，研究的内容主要 有宽度优先，深度优先，b e a m 搜，a 撑算法等。宽度优先，深度优先都是穷举 搜索算法，从原理上讲，利用它们都能找到可行解，但却都不适合用于制造系 统。因为可行解的空间非常庞大，超过了搜索时间与储存空间的限制。在a i 中，较著名的搜索方法就是a 拌算法。它将分支定界法与动态规划法相结合， 常用于图的路径搜索中。n i l s s o n 证明了a 撑算法一定可以找到最优解8 i 。第 二个是基于规则与基于知识的方法，单一的数学方法和工具不足以解决实际的 调度问题，a i 和专家系统的出现对解决调度问题的实时性和智能型提供了新 的辅助手段。调度问题适合用a i 和专家系统来解决是因为它本质上是启发式 的，即需要用经验规则来获取可接受的解。它们用于调度可以克服数学规划与 仿真方法的不足，能根据系统当前的状态和给定的优化目标，对知识库进行有 效的启发式搜索和并行模糊推理，避开了繁琐的计算选择最优的调度策略，为 在线决策提供支持。但也存在一定的不足，对新的调度环境适应性差，开发 周期长，成本高，同时由于a i 技术本身发展的限制，完全由计算机实现的系 统大多是不良的。 在8 0 年代后期，y u e h w e r ny 等学者先后开展了基于调度系统处于不同的 状态，采用不同的调度规则策略的动态调度方法的研究2 i ，其共同特点是：在支 持某些活动发生的资源条件具备时砰为决策点) ，根据系统当时所处的属性状 态，决定采取何种规则( 策略) ，确定或选择活动发生的顺序和时间，即所谓的 状态指导的智能调度方法。 另外，为克服数学表示和软件方法的局限性，1 19 8 8 年，d a v i s 等n 6 1 提出基 于数学规划的分解策略，将调度问题分解为多个子问题，分别考虑各子问题及 其限制，提高了计算能力数学分析模型通常用数学关系式表达所研究系统变 量之间的相互关系。大多数分析模型是描述性的，即在一组条件下预测某一方 案的各种结果数值。有一类预测模型需要分辨出最优结果，即需求出最优解， 在车间优化调度中，要从多个调度方案中寻求满足约束条件和目标的最佳 6 硕i ：学位论文 调度方案，这个寻求最优解的过程常称为优化模型。数学优化模型逻辑性强， 能清楚地表示出复杂系统中的各种输入输出变量以及较好地反映出多个变量 之间的关系，并能实现系统的优化，且建模方便，是车问调度问题中应用较多 的一种建模方法。日本学者t a d a om u r a t a 于1 9 8 9 年首次对p e t r i 网的基本性质 和应用做了详细的介绍，并将其用于对调度问题进行建模。基本p e t r i 网模型 具有直观易理解的优点，但其在描述复杂系统时节点数目过多，因而只适用于 简单系统的建模。有关扩展p e t r i 网在调度问题中的研究见m u r a t a 文献n 引， 这里详细介绍了几种典型的扩展p e t r i 网的研究情况。主要有以下几种模型的 应用研究现状。e p n 模型，它通过增加决策节点，使p e t r i 网具有描述诸如f m s 调度决策过程的能力。这种模型由于节点数目过多，只能用于简单系统的建模。 m u r a t a 对此做了详细的论述。1 9 9 1 年w a n gwx 等人对扩展p e t r i 网在制造系 统中的应用做了详细论述比0 1 ，由于c p n 是p e t r i 网的压缩形式，同基本p e t r i 网相比它具有较少的节点数目，所以比较适合复杂系统的建模，但其分析方法 比较复杂。v e n k a t e s h 等人将t p n 模型应用到f m s 的局域网建模，控制和仿 真当中口，它不仅能够描述系统中事件和状态演化中的逻辑关系，而且通过 设置时间与变迁或库所的联系来分析p e t r i 网演化过程。姜思杰将p t p n 模型 应用于g a ( 遗传算法) 和t s ( 禁忌搜索算法) 混合算法的建模当中口，虽然 它比e p n 模型结构简单，但它没有决策节点。j e n s e n 将p t p n 和c p n 结合 起来提出了h l p n 。严洪森在h l p n 和e p n 的基础上提出了e h l e p n 模型 心纠，该网结构简单，节点少，很适合于f m s 的建模，仿真与控制。随着面向 对象( o o ) 技术的发展与应用，人们开始研究如何将p e t r i 网与o o 技术结合 起来，1 9 9 6 年，w a n glc 通过将制造系统分为四个阶段，提出了一个集成的 o o p o 机制，增强了p e t r i 网的设计描述能力和功能实现能力，降低其建模和 分析的系统依赖性与难度乜副。随后他又对o o p o 机制在单元控制建模中的发展 和应用做了系统研究乜引。随着研究的深入，启发式算法因其易于实现，计算复 杂度低等原因，在实际中得到了广泛的应用心纠。，并且多年来一直受到学者们 的广泛关注，不断涌现出许多新的调度规则。例如，p a n w a l k a rsa 对1 l3 种启 发式调度规则作了详细地总结，将其划分为简单规则，复合规则，启发式规则 三类心”。纪树新等在文心引中举了常见的2 0 条规则，并针对一个实际的制造系 统，分析了这些规则对系统性能如作业的平均等待时间、机床的平均利用率、 作业总加工时间等的影响。随着计算机运算速度的飞速提高，人们希望寻找新 的近似调度方法，它以合理的额外计算时间代价，换得比单纯启发式规则所得 到的调度更好的调度，如文 2 9 中提出的移动瓶颈方法。虽然启发式规则常被 用于实际当中，但它们一般不具有全局优化的特点心引。这一阶段硕果累累，解 决了一系列长期困惑人们的难题，为车间调度问题的研究打下了坚实的基础。 随着调度理论研究的更加深入以及各种交叉学科的发展，不断涌现出了许 多新的求解问题的方法。1 9 9 1 年，g e r s h w i n 等人从控制理论的角度出发，全 面阐述了控制理论的方法在制造系统的应用情况心“。控制理论方法比较适合定 7 基r 改进遗传算法的混合车问生产调度问题研究 量地定义基本问题，但它只适合对小规模系统进行求解。1 9 9 3 年，邓子琼，李 小宁对控制理论方法进行了深入地探讨n 引，主要集中在扰动分析法和极大代数 法上面。扰动分析法兼容了仿真法与理论分析的长处，同时也避免了单纯用仿 真法的大量计算和理论分析研究复杂问题所遇到的困难，主要用于研究制造系 统的性能指标( 生产率等) 对参数变化的敏感性，并以此为基础对系统的运行 进行优化，但是它对多参数的扰动很难用表或状态方程表示仿真运行过程，扰 动较大，近似度较差。极大代数法用与解决线性系统相类似的方法对d e d s ( 离 散事件动态系统) 进行建模。它根据系统的运行关系建立起一系列事件发生时 间的关系方程。但此方法必须在工件加工顺序事先确定的条件下，才能进行建 模分析，因而只适合制造系统的性能分析，而不适合调度。1 9 9 3 邓子琼等人利 用仿真语言对此又进行了研究分析，并取得一定的进展，但是此方法主要缺点 是代价很高n8 1 。1 9 9 8 年，姜思杰在基于g a 和t s 的最小平衡算法及其在f m s 中的应用一文中运用数学规划的方法对排队网络用于f m s 做了初步的分析 心。但排队网络只能分析系统的生产率，平均时间等，很难将车间其它资源考 虑进去，并且很难处理系统出现异常时的情况。此外还有对线性规划法理论的 再研究，l e n o n i d ，n i s o nv a s e r s t e i n 等人对此方法的建模重新进行了详细地论述 【2 6 】 o 大量启发式算法的出现解决了过去无法解决的许多实际问题。随着各种新 的相关学科与优化技术的建立与发展，在车间调度领域也出现了许多新的优化 方法，以遗传算法( g e n e t i ca l g o r i t h m ) 禁忌搜索( t a b us e a r c h ) 、模拟退火 ( s i m u l a t e da n n e a l i n g ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 、多智能体 ( m u l t i a g e n t ) 为代表的智能优化算法在理论上取得了很大进展，并应用到车间 调度问题中，取得了理想的效果。 一般的车间调度问题都是对于具体生产环境中复杂的、动态的、多目标的 调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂 性进行分类。文 2 6 中为了帮助区别不同的生产调度策略，给出了典型生产调 度环境的5 个特征：1 ) 边界条件。2 ) 分批大小和调整费用。3 ) 加工路径。4 ) 随 机事件和扰动。5 ) 性能指标和多目标。车间调度问题的研究方法最初是集中在 整数规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决 复杂的问题。 m u r a t a 对基于离散事件动态系统( d e d s ) 的解析模型这一方法进行了较 早的研究，它主要有q n ，极大代数法，动态规划法，但它们都适合制造系统 的性能分析n 引。另外h ugh 等人利用普通随机p e t r i 网对f m s 调度与控制决 策支持系统进行了研究。1 9 91 年，j i a n gcq ，s i n 曲mg 用带有限缓存的排队 网络来描述带有有限存储容量的制造系统拍3 1 ：由于制造系统的复杂性，以至于 很难用精确的解析模型对其进行描述分析。但是仿真却能提供这种理想模型， 且可以定量地进行评估，从而对实际系统采用合适的方法。这一方面，美国， 德国的研究现在处于领先地位，1 9 9 3 年， d o u b l g e r iz ，d a l e