（管理科学与工程专业论文）基于遗传算法的jobshop车间调度问题研究.pdf

硕i ：论文 基于遗传算法的j o b - s h o p 车问调度问题研究 摘要 如何提高单件产品作业车间调度型( j o b s h o p 型) 的生产制造效率是人们一直关 注和希冀解决的问题。由于其计算复杂性、动态约束性等特点，j o b s h o p 车间调度问 题已经被证明是一个n 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 t h o wt oi m p r o v et h ep r o d u c t i v i t yu n d e rt h ej o b s h o pm a n u f a c t u r i n gm o d eh a sa l w a y s b e e na l li s s u eo fc o n c e r nt ot h ep e o p l e b e c a u s eo fi t sc o m p l i c a t e dc a l c u l a t i o n ，d y n a m i c m u l t i 。r e s t r i c t i o n ，j o b - s h o ps c h e d u l i n gp r o b l e m ( j s p ) h a sb e e np r o v e da sn p h a r d ( n o n - d e t e r m i n i s t i cp o l y n o m i a l h a r d ) p r o b l e m ，a n dm a n yi n t e l l i g e n tc o m p u t a t i o nm e t h o d s a r ei n t r o d u c e di n t ot h i sf i e l di nr e c e n ty e a r s a m o n g t h e s e ，g e n e t i ca l g o r i t h m ( g a ) i so n e o ft h em o s tp o p u l a rm e t h o d sg e t t i n ga ni n c r e a s i n ga t t e n t i o nb yd o m e s t i ca n do v e r s e a s e x p e r t sr e c e n t l y b u ts l o wc o n v e r g e n c ea n dl o wp r e c i s i o ns t i l le x i s ti nt h e s ea p p l i c a t i o n s a n dr e s e a r c h t oi m p r o v et h ep e r f o r m a n c eo ft h e e x i s t i n gg af o rj s pa n ds p e e du p s e a r c h i n gf o rt h eo p t i m a ls c h e d u l i n gs o l u t i o n ，b a s e do nt h eb a c k g r o u n do fam o u l d m a n u f a c t u r i n gs h o p ，t h i sd i s s e r t a t i o ns t u d i e dj s pu s i n ga l li m p r o v e dg a t h r e ep a r t sw e r ec o n t a i n e d ： 1 c h a p t e rl ( b a s i ct h e o r y ) ，i n t r o d u c i n gt h ei m p o r t a n c eo ft h es u b j e c t ，t h es t a t u so f p r e s e n tw o r l d w i d er e s e a r c hi nt h i sf i e l d 2 c h a p t e r2 ( p r o j e c tb a c k g r o u n d ) ，d e s c r i b i n ga n da n a l y z i n gt h ee n v i r o n m e n t ，s t a t u s ， a n dc h a r a c t e r i s t i c so f p r o d u c t i o n ，t h ep r o c e s so f p l a na n dc o n t r o l ，e t c 3 c h a p t e r3 & 4 ( a l g o r i t h ma n a l y s i s ) ，b a s e do n o p e r a t i o n b a s e dr e p r e s e n t a t i o n , d e s i g n i n gk e e p i n g - f r a g m e n t s - r e v e r s e c r o s s o v e r , w h i c hw a sa p p l i e dt oj s pw i t hf u z z y p r o c e s s i n gt i m ea n dd u e d a t e ，t h e nc l a s s i c a la n dr e a l i s t i cn u m e r i ce x a m p l e sw e r eg i v e n w h i c hv a l i d a t e dt h ee f f e c t i v e n e s sa n de f f i c i e n c yo f t h ep r o p o s e dm e t h o d t h er e s u l t ss h o w e dt h a t ：t h i si m p r o v e da l g o r i t h mn o t o n l ye n s u r e dv a l i d i t ya n d d i v e r s i f i c a t i o no ft h ee v o l v i n gd e s c e n d a n t s ，b u ta l s o i m p r o v e dp r e c i s i o no fo p t i m a l s c h e d u l e k e yw o r d ：g e n e t i ca l g o r i t h m ，j o b s h o ps c h e d u l i n gp r o b l e m ，f u z z y a n d d u e d a t e ， k e e p i n g - f r a g m e n t s - r e v e r s e - c r o s s o v e r , r e p r e s e n t a t i o n p r o c e s s i n gt i m e o p e r a t i o n - b a s e d 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 二 研究生签名：= 乒乳 伽暑年6 月珑日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： k 旧g 年月“日 硕一 j 论文 基于遗传算法的j o b - s h o p 车问调度问题研究 1 绪论 车间调度，作为一个生产过程中的关键模块，是整个先进生产制造系统实现运筹 技术、管理技术、优化技术、自动化与计算机技术发展的核心。无论是理论研究，还 是实际运作，车间调度问题一直受到学者们的关注，同时也涌现出各种各样的研究派 别、研究方法和手段等。 在本章中，将在对相关研究的实践背景和理论背景分别做出论述的基础上，指出 目前研究存在的主要问题以及可行的研究方向，给出本论文研究的实践及理论意义， 明确研究的主要内容、技术路线，给出论文的研究框架结构。 1 1 研究背景及其意义 上世纪8 0 年代以来，随着经济和社会的发展，市场环境发生了剧烈变化，传统 的大批量生产方式再也难以适应市场要求。现在用户对产品的质量以及服务质量的要 求越来越高，已不满足于从市场购买标准化的产品，他们希望得到按照自己要求定制 的产品和服务，这些变化导致产品生产方式革命性的变化。面向订单、多品种、中小 批量、高质量、交货期短以及低成本等已逐渐成为制造业明显的生产特征，并已成为 当今工业企业主要生产方式之一。这样的生产方式在学术界也被定义为j o b s h o p 型 生产方式，针对可分解的工作( 如产品制造) ，探讨在尽可能满足约束条件( 如交货 期、工艺路线、资源约束等) 的前提下，安排其组成部分( 操作) 使用哪些资源、其 加工时间及加工的先后顺序，以获得产品制造时间或成本等指标的最优化【l 】。 这种生产方式最大的特点就是能够比较灵活地适应市场的多样化需求，但同时也 带来了诸多困难，产品生产计划和调度控制难度加大了。如何进行j o b s h o p 生产方 式下的计划和调度控制一直是国内外学者广泛关注的问题之一。 本文j 下是以这一现状为研究背景，研究背景项目源于预研项目“x x x 车间快速 制造响应支撑技术”，主要以某企业分厂模具制造车间为研究对象。该项目主要内容 包括：车间层的制造过程及相关资源的重构方法研究、多品种小批量计划调度方法研 究和车间层生产计划控制系统的开发；其中第二部分正是本文研究的主要内容。本论 文研究目的在于通过对j o b s h o p 生产方式特点研究，采用现代生产运作系统理论方 法和优化理论方法，力图针对多品种小批量车间生产的实用、有效的计划调度和控制 方法，为项目系统的丌发提供方法，具有重要的理论意义和现实意义。 1 2 相关领域及其国内外研究现状 1 2 1 车间作业计划调度问题的研究现状 车问作业计划调度问题，是一类特殊的调度问题。调度问题的研究可以追溯到 l 1 绪论 硕j ：论文 1 9 5 4 年，当时，j o h n s o n 提出了两台机器的流水车间调度问题并进行了研究。此后的 近5 0 余年，调度问题得到了理论界和工程界研究人员的广泛关注和研究，尤其是在 运筹学、工业工程和计算机科学等领域。 车间作业调度问题的方法主要有：数学规划方法、控制论方法、人工智能技术、 人工神经网络技术、离散事件解析模型方法、邻域搜索技术( 包括模拟退火法、遗传 算法和禁忌搜索等) 、模糊逻辑以及规则调度等方法【2 】。但正如车间调度领域专家 r e h a u z s o y 教授所指出的目前调度领域分成了两个阵营，一个是理论阵营，对理论非 常感兴趣；另一个是实用阵营，认为理论阵营的文章毫无价值，注重研究的实用性。 在上述提及的各种方法中，实际应用的多是基于规则调度或基于知识的启发式调度， 因为生产的实际情况太复杂，而由实际情况提炼出的规则和知识的调度相对而言比较 简单且更接近于生产实际。但是仅由若干规则或经验知识进行调度又存在着调度结果 不一定是最优的问题。 调度问题通常涉及到四个基本要素：任务、资源、时问和性能指标，针对这四个 要素，调度的目的课间明地描述为将任务在资源和时间上进行合理的分派。其中， “合理”程度的评价是以一个或一组性能指标为依据的。在经典的车自j 作业计划调度 问题中，任务通常是指工序级的，即零件的加工工序，资源通常指加工设备或机器。 根据这两个要素，通常可以对于车间作业计划调度问题进行如图1 1 【3 1 的划分。 隔磊五丽司 ( j o bs c h e d u l i n g ) i 丫 单机调度问题( s i n g j e m a e h i r m s c h e d u l i n g ) 图1 1 车间作业计划调度问题分类 在这些调度问题中，单件车间作业计划调度问题( 即j o b s h o p 调度问题，以下 简称j s p 问题) 是最一般的调度问题也是最复杂的一种排序问题。包括多台机器，每 个任务包括多个操作，操作的顺序不尽相同。本文研究的主要对象是多品种小批量生 产方式的计划调度问题，属于典型的j o b s h o p 调度问题，因此，以下对单件车间作 业计划调度问题( j s p ) 的研究和发展状况进行综述。 硕l 论文 基于遗传算法的j o b - s h o p 车间调度问题研究 1 2 2j s p 问题的研究现状 标准的j o b s h o p 调度问题主要研究的是，1 个工件在m 台机器上加工的组合排序 问题，每个工件包含一系列必须按制定顺序加工的工序，而每道工序的加工又必须在 指定的机器上进行，要求在满足某些约束条件下确定各工序的加工起止时间，并使加 工性能指标达到最优。j o b s h o p 调度问题由m u t h 和t h o m p s o n 于1 9 6 3 年第一次提出， 此后就成了调度问题中与工业相关的一个标准类型的调度问题【4 】，它具有非常重要的 理论和实际研究价值，引起了理论和工程界广泛的关注和研究。j o b s h o p 调度问题的 研究涉及到多个学科和领域，如运筹学、优化理论、图论、系统科学、管理科学、计 算机科学知识等，被认为是最困难的调度问题之一。1 9 7 6 年，r i n n o o yk a n 和 g a r e y m r t 5 】等均证明了j o b s h o p 调度问题为典型的n 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 调度问题的 子问题，并以一定的形式对其进行描述；j o b s h o p 调度问题算法设计的目的是对建立 的模型进行求解，获得优化的调度解。而算法分析的目的则是对算法正确性进行验证、 对调度结果进行评估与预测、对算法的时间复杂度及空间复杂度进行分析掣3 1 。 ( 1 ) j s p 调度问题的模型研究 几十年来，在经典j o b s h o p 调度问题模型的基础上，国内外研究者根据理论研 究意义和实际应用需求，提出了许多j o b s h o p 调度问题的特殊问题和扩展问题模型， 通过分析和总结，可以这些模型将其归类如下： 1 ) 从任务属性的角度分类 工件具有指定交货期的j o b s h o p 调度问题 经典j o b s h o p 调度问题中没有考虑工件的交货期，然而，在大多数制造企业， 特别是在订货型生产企业，工件是具有交货期的，而对交货期的考虑从不同的角度又 可以进一步分为：交货日期( d u e d a t e ) i n - j 题t 6 胴和交货期窗口( d u e - w i i l d o w ) 问题【8 】【9 】，确 定交货期( s p e c i f i e dd u e d a t e ) i n l 题和模糊交货期( f u z z yd u e d a t e ) i n - 题t 1 0 】，单独交货期问 题( d i s t i n c td u e d a t e ) 和公共交货期( c o m m o nd u e d a t e ) i n - j 题。 工件投放时间非零时刻的j o b s h o p 调度问题 经典j o b s h o p 调度问题中所有工件的投放时间均为零时刻。然而，实际生产中， 情况往往并非如此。因此，有些学者研究了工件投放时间非零时刻的j o b s h o p 调度 问题i l l 】。 工件具有不同优先级的j o b s h o p 调度问题 经典j o b s h o p 调度问题中所有工件都是具有等同优先级的。而实际生产系统中， 3 1 绪论硕i ：论文 工件常常具有不同的优先级。优先调度规则种类很多，有学者统计过大约有两百多种 【1 2 1 。为可以分为局部优先规则与整体优先规则两类。局部优先规则仅考虑单个工作地 队列中的信息；整体优先规则不仅考虑本工作地的信息，还要考虑其它工作地的信息。 工序加工时间非确定点值的j o b s h o p 调度问题 经典j o b s h o p 调度问题工序的加工时间是一个事先确定的点值。实际生产系统 中加工工时常常是模糊的、机器相关的或服从一定的分布。文献【1 3 】【1 4 1 研究了模糊加 工时间的j o b s h o p 调度问题；文献【】研究了机器相关( 或机器依赖) 的加工时间的j s s 问题；文献【1 6 】对加工时间服从指数分布的问题进行了研究。 柔性工艺方案的j o b s h o p 调度问题 经典j o b s h o p 调度问题中工件的加工工艺方案是唯一的、线性的，事实上，一 个工件的加工往往有多种可行的方案( 即所谓柔性工艺方案) 。对于这一类问题的研究 通常可分为三个方面：工序加工机器的柔性【17 1 、工艺路线的柔性和整体的柔性【1 9 】 ( 即同时考虑机器的柔性和路线的柔性) 。 2 ) 从机器属性的角度分类 考虑机器停机和故障的j o b s h o p 调度问题 经典j s p 问题中，所有机器不仅都是零时刻即可用的，而且不考虑机器的故障， 即机器任意时刻都是可用的。这显然只是一种理想状态，实际生产中机器可能由于停 电或操作工的原因等产生停机，机器的故障也是不可避免的【2 0 】【2 i 】。 机器准备时间非零的j o b s h o p 调度问题 经典j o b s h o p 调度问题中，所有机器都是零时刻即可用的，即机器的准备时间 为零。实际情况中，机器往往存在一个准备时间。文献【2 2 】研究了机器存在准备时间的 j o b s h o p 调度问题。 3 ) 从机器对工件的加工关系方面分类 可抢占性j o b s h o p 调度问题 经典j o b s h o p 调度问题中，机器对工件的加工是非抢占性的。实际生产中，特 别是在订货型生产环境中，由于交货期的约束及生产过程中的一些意外事件的影响， 常有一些急件需要抢占机器进行加工。因此，可抢占性j o b s h o p 调度问题的研刭2 3 】 具有重要的实际意义。 批处理j o b s h o p 调度问题 经典j o b s h o p 调度问题中，一台机器一次只能加工一个工件，实际生产中，却 往往存在一台机器加工几个相同或相似的零件的情况。文献【2 4 】对此类问题进行了研 究。 4 ) 从性能指标的角度分类 基于库存的性能指标 4 硕l ：论文 基于遗传算法的j o b - s h o p 车问调度问题研究 基于库存的性能指标主要有：平均待加工工件数量、平均未完成工件数量、平均 已完成工件数量、平均机器空闲时间、最大机器空闲时间等。 基于作业交货期 这一类性能指标主要有：最小化工件最大延期、最小化工件平均延期、最小化工 件总延期、最小化工件延期均方差、最小化工件总拖期、最小化加权工件总拖期等等。 综合性能指标 混合性能指标往往是上述几个基本性能指标的综合。如m a k e s p a n 与总拖期的综 合，流经时间与总拖期的综合、e t 指标等【2 5 】。 ( 2 ) j s p 调度问题的算法研究 自从j o b s h o p 调度问题提出以来，研究者们提出了各种求解算法。总的来讲， 这些算法可分为两大类：一类是为了得到问题的全局最优解而进行的精确算法，它要 求求解的问题规模比较小；另一类是利用近似算法来寻找该问题的近似较优解，如图 1 2 所示。 - 1 。1 。1 。一 j o bs h o p 调度问题 算池 i 解析枚举j i 法i 法l ! 兰竺兰兰 图1 2j o b s h o p 调度问题算法分类 具体分类如下： 1 ) 枚举法( e n u m e r a t i v em e t h o d s ) 该类算法同样只对很小规模问题比较有效，对大规模问题计算量和存储量难以承 受。如回溯法( b a c k t r a c k i n g ) 、分支定界法( b o 吼da n db r a n c h ) t 2 6 1 、整数规划法、混合 整数规划法、分解方法、代理对偶方法等。 2 ) 解析法 指针对简单小规模调度问题的解析求解算法，如m o o r e 算法、j o h n s o n 算法。 这类算法只适用于一些特殊类型的单机调度问题和双机f l o w s h o p 调度问题【2 7 1 。 3 ) 构造性方法( c o n s t r u c t i v em e t h o d ) 该类方法能够快速建立问题的解，常情况下解的质量相对较差，但对于实际生产 系统中复杂的、大规模的j o b s h o p 调度问题来说具有很大的优越性。如优先调度规 1ij 上 肛戳触 一 一躲强，二一 丫1 铡u i 绪论 硕i ：论文 则( p f i o d t yd i s p a t c hr u l e ) 算法、基于瓶颈的启发式算法( b o t t l e n e c k b a s e d h e u r i s t i c s ) t 2 8 1 、插入方法( i n s e r t i o na l g o r i t h m ) 等。 4 ) 邻域搜索算法( l o c a ls e a r c hm e t h o d ) 该类算法从一个( 或一组) 初始解出发，通过邻域函数生成解的邻域，再在邻域中 搜索出更优的解来替换当前解，通过不断的迭代过程实现解的优化。其调度解的质量 通常要由优于构造方法，但算法的耗时却要多得多。属于该类的算法主要有： 迭代改进法( i t e r a t i v ei m p r o v e m e n t ) 。 遗传算法( 以下简称g a ) 【2 9 】：该方法由j h o l l a n d 于1 9 7 5 年提出，g o l d b e r g 等人的著作为其奠定了较为全面的理论和应用基础【3 0 1 ，将在下一节做详细综 述。 模拟退火法( 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 等人提出， k i r k p a t r i c k 等首先将其引入组合优化问题的求解过程。 禁忌搜索( t a b us e a r c h ，t s ) ：由g l o v e r 等人首先提出，其核心在于借助禁忌 表的使用，实现某种形式的短期记忆机制。 变邻域搜索( 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 ) 3 1 j 。 5 ) 人工智能方法( a r t i f i c i a li n t e l l i g e n c e ) 该类方法利用人工智能的原理和技术进行搜索，根据系统当前状态和给定的优化 目标，对知识库进行有效的搜索和模糊推理，避开了繁琐的计算，从而选择优化的调 度策略，如神经网络( n e u r a ln e t w o r k ，n n ) t 3 2 1 、蚁群系统( a n ts y s t e m ，a s ) 等。 6 ) 仿真方法( s i m u l a t i o nm e t h o d ) 在实际生产中，实效性和经济性等原因，利用优化算法来进行生产调度还存在这 一些问题。而仿真技术的出现，使得很多学者开始了车间调度的仿真研究。文献f 3 习 主要是关于仿真技术方法在调度问题上的应用。 在上述所有各种算法中，研究较多的主要有：优先调度规则算法、遗传算法、模 拟退火法、禁忌搜索法、神经网络法及各种混合算法。其中，考虑到实际生产系统中 车间作业计划问题的复杂性和规模，目前最为实用而有效的算法仍然是优先调度规则 算法。此外，由于具有并行性和鲁棒性的优点，遗传算法在车问作业计划研究中也受 到非常广泛的青睐，相比于优先调度规则算法，它可以得到更为优化的调度解，且对 于中小规模的实际问题来说，其调度时间也基本是可以接受的。下面对j o b s h o p 问 题遗传算法的研究和发展状况进行综述。 1 2 3j s p 调度的遗传算法研究现状 ( 1 ) j s p 的g a 编码研究 编码问题是设计遗传算法的首要和关键的问题，它影响着算法各个子阶段。在过 6 硕一l j 论文 基于遗传算法的j o b - s h o p 车间调度问题研究 去的几十年来，已经提出了以下几种主要的j s p 编码方式【3 4 】： 1 ) 基于工序的编码( o p e r a t i o n b a s e dr e p r e s e n t a t i o n ) ：由g e nt s u j i m u r a 和k u b o t 提出，将每个染色体用刀m 个代表操作的基因组成，是所有操作的一个排列，其中 各工件号均出现，1 次； 2 ) 基于工件的编码( i o b b a s e dr e p r e s e n t a t i o n ) ：有h o p s a p p l e ，j a c o b ，p a k a 和 z a v e r i 提出，将每个染色体用n 个代表工件的基因组成，是所有工件的一个排列； 3 ) 基于优先表的编码( 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 ) ：将每个染色体用分 别对应于m 台不同机器的m 个子串，各子串是一个长度为刀的符号串，用于表示一种 先后表，各符号表示响应机器上的加工操作； 4 ) 基于优先规则的编码( p f i o f i t yr u l e b a s e dr e p r e s e n t a t i o n ) ：由d o m d o r f 和p e s c h 提出，将每个染色体用一个长度为刀i f 的优先分配规则序列构成，每个基因即为一 种优先调度规则； 5 ) 基于析取图的编码( d i s j u n c t i v eg r a p h - b a s e dr e p r e s e n t a t i o n ) 最早由t a m a k i h e n i s h i k a w a 提出，将染色体用一个长度为l m 的0 1 字符串来表示，该染色体( 由各 弧的操作顺序组成) 作为优先决策，以决定同台机器上发生操作冲突时各操作的顺序； 6 ) 基于工件对关系的编码：n a k a n o 和y a m a d a ( 1 9 9 1 ) 利用二元矩阵表示调度， 矩阵由相应机器上工件对的优先关系确赳3 5 】；善! 7 ) 基于完成时间的编码( c o m p l e t i o nt i m e - b a s e dr e p r e s e n t a t i o n ) ：这是一种最直观 的方式，由y a m a d a 和n a k a n o 提出，利用各个工序完成时间的有序表来表示染色体： 8 ) 基于机器的编码( m a c h i n e - b a s e dr e p r e s e n t a t i o n ) ：将每个染色体用所有机器的 排列，并以此通过移动瓶颈方式来构造调度。其中，由a d a m s ，b a l a s 和z a w a c k 提 出的瓶颈移动启发式可能是作业调度所有启发式算法中最有效的； 9 ) 随即键编码( r a n d o mk e yr e p r e s e n t a t i o n ) ：由b e a n 首先提出，将调度解编码 成随机数，这些值用作排列键来解码。 ( 2 ) 基于g a 的j s p 算法改进 尽管g a 具有种群并行搜索能力，并在总体上把握了进化的方向，但其局部搜索 能力较差，容易出现早熟现象。对g a 的改进主要表现在算法的编码、初始种群生成、 算子设计等方面。s h i ( 1 9 9 7 ) 针对基于操作的编码，提出了有效的交叉方式，在保 证可行性的基础上取得了较好的性能【3 6 】；c h e n g ( 1 9 9 9 ) 综述了求解j s p 的交叉和编 译操作的设计【3 7 1 ；w a n g 等( 2 0 0 0 ) 提出了一种受控遗传算法，采用并行机编码，用 启发式方法产生初始种群，并利用了多交叉操作，同时基于模糊逻辑和置信函数估计 遗传操作的参数；q i 等( 2 0 0 0 ) 提出了一种并行多种群的遗传算法来满足j s p 的动 态特性【3 引。 同时，近年来许多学者在提出改进方法的同时，往往将其与现有方法进行比较。 i 绪论硕j ：论文 t a d e i 等( 1 9 9 5 ) 比较了t s ，s a ，g a 和l a g r a n g i a n 松弛法等解决j s p 的先进搜索方 法的性斛3 9 1 。k u r b e l 等( 1 9 9 5 ) 将s a ，g a 和混合整数线性优化应用于j s p ，并对两 者的优化和时间性能做出比较【加1 。p o n n a m b a l a m 等( 1 9 9 9 4 1 1 ，2 0 0 0 ) 研究了s a ，t s 的求解性能，并与已有的g a 等结果进行了比较。 ( 3 ) 基于g a 的j s p 算法混合及推广 而在算法混合方面，通过在g a 中混合嵌入局部搜索方法或启发式方式来增强 g a 的搜索能力。d a g l i 等( 1 9 9 3 ) 针对非线性多准则目标函数的离散调度提出了将 g a 与人工神经网络的混合算法【4 2 】；杨圣祥等( 1 9 9 8 ) 用g a 结合基于约束满足的自 适应神经网络求解j s p ：k o l o n k o ( 1 9 9 9 ) 将小种群s a 运行于g a 框架，利用自适应 温控与重升温以及面向时间的交叉来解决j s p 问题【4 3 j ；c a i 等( 2 0 0 0 ) 结合局部搜索 方法和g a 有效求解j s p 问题。近年来，混合遗传算法的研究在国际上受到了越来越 多的重视【4 引。 在算法推广方面，近年来j s p 的研究延伸到更具实际意义的动态调度和更具实际 特征的装配线、间歇调度、柔性调度以及模糊调度等问题。方剑等( 1 9 9 7 ) 借助预测 控制中滚动优化的思想提出了周期性和时间驱动的滚动调度策略：l e e 等( 1 9 9 7 ) 研 究了g a 在批量可变的柔性流水线加工问题的应用【4 5 j ；o z d a m a r 等( 1 9 9 8 ) 研究了 一类具有设置时间和超时决策的c l s l p ( c a p a c i t a t e dl o ts i z i n ga n dl o a d i n gp r o b l e m ) 问题，并提出了结合s a 、g a 和t s 的混合启发式方法【删；p r i n s ( 2 0 0 0 ) 针对一类具 有自由工件路径的o p e n s h o p 问题，给出了几种相应的g a 解决方案；钱晓龙等( 2 0 0 1 ) 则对动态调度的研究方法进行了综述；s a k a w a 等( 2 0 0 1 ) 讨论了双目标下的具有模 糊加工时间和交货期的模糊j s p ，并提出了结合模糊技术和g a 的有效方案【4 刀。 1 3 存在的问题及可行的研究方向 综上所述，j o b s h o p 调度问题可以说是生产调度领域的典型代表，而遗传算法可 以说是智能优化技术的典型代表，因此，从g a 的角度去研究j s p 问题是具有重要的 理论意义和实际意义的。这一领域至今尚未形成一套系统的方法与理论，并且多数研 究忽略了很多实际因素和约束，离应用尚有不小的差距，还存在着大量工作有待进一 步深入和完善0 4 。 首先，在j s p 建模过程中，对真实环境进行了大量的简化，不能很好地解决实际 问题。因此将j s p 地数学模型更加现实化，动态调度的研究尤其值得重视，目前已有 许多研究者开始此方面的工作； 其次，在g a 算法方面，随着解规模的扩大，求解速度和精度几何级数下降。尽 管此类算法已有不少改进，但其费时的致命缺点仍无法克服，且问题的规模局限性使 得该算法的实用性不强。鉴于国际学术界对混合系统与算法的日益重视，混合优化策 硕士论文 基于遗传算法的j o b - s h o p 车问调度问题研究 略以及相应仿真环境的开发无疑是一个值得关注的研究方向，尤其是将已有各种调度 方法的有点与g a 有效地融合； 最后，g a 与j s p 方法有待进一步深入结合的问题。j s p 是一类n p 难调度问题， 它有着其自有的特性。而g a 最为一种智能优化算法，也有着其自有的特性。结合j s p 的特性及其局部极小拓扑结构的分析和g a 遗传算子的特性分析与结构设计，有助于 更好地利用g a 解决j s p 问题。而这一方面的研究目前还比较少，这无疑是一个很重 要的研究方向。 总之，随着计算技术、优化技术、数学理论和计算机硬件的发展，g a 、j s p 本 身以及它们的结合将得到更完善的解决，研究与应用领域将更加宽广，必然朝着集成 化、多目标化、动态实用化、高度次优化方向深入进行【3 4 1 。 1 4 研究内容、技术路线 1 4 1 论文内容以及结构 本文以“x x x 车间快速响应支撑技术预研项目为依托，以某企业分厂模具制 造车间为研究背景，从遗传算法的角度进行了j o b s h o p 生产方式下的车自j 调度算法 研究，共分五章，论文的布局结构如图l - 3 所示： 第一章：绪论。主要分析了本论文的研究背景、研究目的和研究意义；对国内外 的车间调度研究、j s p 问题研究以及基于g a 的j s p 问题现状进行了评述；同时对论 文的研究对象、研究内容、技术路线和框架结构进行了说明； 第二章：模具生产运作的现状分析。对本文项目背景某企业分厂模具车间的 生产环境、现状、计划控制流程以及生产特点做详细阐述、分析；在此过程中，对其 计划调度流程进行诊断，分析其流程中存在的问题，为后面的算法研究提供实际项目 背景基础； 第三章：保存基因片段逆序交叉的j o b s h o p 遗传算法。为了更好地研究探寻实 用可行的模具车间实际生产的调度算法，首先从一类的相对简单的经典j o b s h o p 问题 入手进行算法研究，提出了保存基因片段逆序交叉的遗传算法。最后通过经典的 f t 0 6 、f t l 0 两个算例，验证了该算法的可行性和有效性； 第四章：基于模糊加工时间和交货期的j o b s h o p 遗传算法。将保存基因片段逆 序交叉的j o b s h o p 遗传算法应用到模糊加工时间和交货期j o b s h o p 问题中：首先使 用三角模糊数和半梯形模糊数来处理加工时间和交货期；在算法方面，继续沿用该遗 传算法来进行编码等各项操作；在目标函数方面，使用了一致指标求和平均值用 以衡量染色体的适应度值。最后，引用了项目背景的一个实际案例，利用其实际生产 数据进行了实例运算，进一步验证了该算法的有效性； 第五章：总结与展望。对本论文的主要研究工作和创新指出进行了总结；并对论 o i 绪论 硕i j 论文 文尚未涉及、或有待进一步研究的相关问题做了简单的评述。 图1 3 论文结构关系图 1 4 2 技术路线 本论文综合了理论研究背景和实际项目背景，从遗传算法的角度进行了j o b s h o p 生产方式下的车间调度算法研究；本文技术路线如图1 4 所示。从技术路线图可以看 出：本文首先从研究背景、国内外研究现状入手，阐述、分析了本文研究内容的理论 依据和基础；在本文研究背景某企业分厂模具车间生产现状调研的基础上，详细 描述其生产运作、计划监督等主要流程，并对流程中存在的问题进行分析，将这部分 作为本文的实践背景和依据；在理论和实践背景的基础下，提出了本文研究解决的主 要问题基于模糊加工时间和交货期的模具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 问题中去，通过实际算例的验证，进而探讨对实际问题的解决。 1 0 硕一 二论文 基于遗传算法的j o b - s h o p 车问调度问题研究 1 5 本章小结 图1 4 论文技术路线 本章在对相关研究的实践背景和理论背景分别做出论述的基础上，从三个方面论 述了本文研究问题的相关领域及其国内外研究现状，分别是：车间调度研究现状，j s p 问题研究现状以及基于g a 的j s p 问题研究现状。这一部分的描述给论文研究提供了 理论依据。在此基础上，指出目前研究存在的主要问题及可行的研究方向，明确研究 的主要内容、技术路线，给出论文的研究框架结构。 2 模具生产运作的现状分析诊断 硕1 j 论文 2 模具生产运作的现状分析诊断 口 l = | jl 二二j 目_ 曲_ 曲_ 曲蕾柚 1 2 硕i ：论文 堆于遗传算法的j o b - s h o p 车间调度问题研究 料不足时，向所级申请采购等。 计划组主要负责：l 、制定下达月度生产计划、生产完成任务；2 、协调各部 门组织生产准备；3 、工票抄写、统计，制定生产进度台帐，监督生产进度： 4 、根据在制任务的特点，协助班组长，调度生产；5 、紧急任务生产调度； 6 、工人每月工时统计，绩效考核；7 、核算产品总成本等。 在此由于篇幅的原因，生产班组的主要职责就不一一详细叙述。 2 1 2 产品生产的主要特征 该车间的生产方式属于典型的面向订单的多品种、单件小批量研制型生产模式， 产品的主要特征决定了生产运作的模式和运作方法的选择。该分厂十车间模具产品生 产特征具体反映在如下几个方面： ( 1 ) 多品种、小批量 该工模具车间主要负责全所所有分厂的工模夹具的生产，专业化程度高，标准化 模块化程度低，品种变化多，批量小，基本以单件生产为主，月平均在制品是2 0 0 余件；同时也存在着一部分外协、外购件； 嘎 ( 2 ) 生产周期长、工艺复杂 产品从接到图纸、工艺设计到成品入库这一过程周期，平均来看是4 0 - - 6 0 天，加 工周期比较长，工艺过程复杂，加工过程相对独立； ( 3 ) 紧急任务多 由于军工产品生产的特点，要求每个月的紧急插入任务占月平均任务的 3 0 2 5 ，计划变动频繁，因此增大了计划调度以及控制工作的难度； ( 4 ) 交货期急且不稳定 同样因为军工产品生产的特点，在交货期上要求比较苛刻，而且不同于其他产品， 军工模具的交货期并不稳定，随时可能提前，因此预期计划工作难度很大，也给车间 的生产运作带来了极大的困难； ( 5 ) j o b s h o p 型生产组织形式 j o b s h o p 型生产组织形式即是工艺专业化的生产组织形式，是多品种小批量生产 组织生产流程的最常用的生产组织形式。该模具生产车间即采用了这种j o b s h o p 的生 产组织形式，按照生产过程的不同工艺阶段来划分生产单位( 如图2 1 的生产班组) ， 将具有相同工艺特征的工作集中于同一生产单位。 而其内部生产的特点又可以表现为以下几点【3 】： ( 1 ) 产品生产的一次性 模具是典型的非定型产品。种制品对应于- n 模具，一副模具的更新换代，同 一模具的需求也就不存在了。因此，一般情况下，对于一副模具的需求往往是单件的， 2 模具生产运作的现状分析诊断 硕十论文 其产品( 即每- n 模具) 的生产往往是一次性的； ( 2 ) 生产组织的被动性 主要生产任务完全来自于所级任务书。什么时候生产什么产品、生产多少数量等 都是企业