（机械电子工程专业论文）基于装配约束的机械产品生产调度算法研究.pdf

大连理工大学硕士学位论文 摘要 生产调度是机械产品生产中一个很重要的环节，直接关系到产品的生产周期、生产 成本和企业的生存能力。优秀的生产调度方案可以使企业合理地分配各种生产资源，降 低生产成本，实现准时化生产，提高市场竞争力。以往对生产调度的研究大部分集中在 作业车间调度j s p ( j o b s h o ps c h e d u l i n gp r o b l e m ) 上，未考虑产品的装配问题。而现在 的机械产品基本上都是装配型产品，生产调度时必须要考虑机械产品的装配约束，这就 衍生出另一种调度问题装配作业车间调度问题a j s p ( a s s e m b l yj o b s h o ps c h e d u l i n g p r o b l e m ) ，而国内外针对a j s p 的研究却较少。本文针对a j s p 的相关算法进行研究， 将机械产品的装配约束考虑在内，具有很强的实际意义。另外，装配强约束的存在使问 题的建模和算子的设计都具有很大的难度，因此本文的研究也具有较大的理论价值。 本文首先通过建立数学模型详细地描述了a j s p 问题，给出典型的装配结构和装配 约束关系，对遗传算法( g a ，g e n e t i ca l g o r i t h m ) 的关键技术、进化参数等进行概述， 确定本文的染色体编码方案和选择算子，并设计了几种不同类型的适应度函数。然后提 出两种a j s p 的遗传算法：a j s p 的全空间遗传算法和a j s p 的可行域遗传算法( f s s g a ， f e a s i b l es o l u t i o ns p a c eg e n e t i ca l g o r i t h m ) 。a j s p 的全空间遗传算法的难点在于不可行 染色体修复算子的设计。本文提出两种新的修复算子自上而下调整法t d r a ( t o p d o w nr e c u r s i v e l ya d j u s t m e n t ) 和基于父项链表的基因交换法g e ( g e n e se x c h a n g e b a s e do i lf a t h e rl i n k l i s t ) 。二者和文献中的基于设计结构矩阵d s m ( d e s i g ns t r u c t u r e m a t r i x ) 的修复算子在信息熵损、染色体图谱等方面进行详细地比较，结果显示t d r a 和g e 比d s m 更能保持种群的多样性。随后的g a 实验结果也表明g a 运用t d r a 和 g e 两种算子比运用d s m 的确有更好的进化表现。然后对解空间大小进行分析，提出了 解空间大小计算方法，计算结果表明a j s p 的可行解空间远比全空间要小，基于此结果 提出了可行域遗传算法，并设计相应的可行域遗传算子来支撑可行域遗传算法，减少了 搜索空间，省去修复解码操作，从而大大提高搜索效率。另外，分别进行了大规模算例 实验、文献算例对比实验和工程实例实验等验证实验。 最后，针对新算法和算子进行的一系列实验均得到了很好的实验结果。其中修复 算子对比实验的实验结果证明两个新修复算子能更好地保持种群多样性，有利于g a 进 化寻优，g a 实验结果表明全空间遗传算法在a j s p 上具有很好的可行性和寻优性。算 法对比实验和最后的文献算例对比实验结果都证明了可行域遗传算法在性能和质量上 都优于其他算法。工程实例实验结果表明所设计的算法能较好地应用于实际情况。 关键词：生产调度；遗传算法；装配约束；种群多样性；染色体图谱 基于装配约束的机械产品生产调度算法研究 r e s e a r c ho np r o d u c t i o ns c h e d u l i n ga l g o r i t h mf o rm e c h a n i c a l p r o d u c t sb a s e do na s s e m b l yc o n s t r a i n t s a b s t r a c t p r o d u c t i o ns c h e d u l i n gi sa l li m p o r t a n tp a r ti nm e c h a n i c a lp r o d u c t sm a n u f a c t u r i n g ，a n di t h a sd i r e c tr e l a t i o n s h i pw i mp r o d u c t i o nc y c l e ，p r o d u c t i o nc o s ta n de n t e r p r i s es u r v i v a b i l i t y e x c e l l e n tp r o d u c t i o ns h e d u l i n gs c h e m e sa r eh e l p f u lt oe n t e r p r i s ei na l l o c a t i n gd i f f e r e n tt y p e p r o d u c t i o nr e s o u r c er e a s o n a b l y ，r e d u c i n gp r o d u c t i o nc o s t ，r e a l i z i n gj u s t i n t i m ep r o d u c t i o n a n di m p r o v i n gm a c k e tc o m p e t i t i v e n e s s i nt h ep a s t ，m o s to fr e s e a r c ho np r o d u c t i o n s c h e d u l i n gf o c n s e do nj o b - s h o ps c h e d u l i n gp r o b l e m - - j s pw i t h o n tc o n s i d e r i n ga s s e m b l y s t a g eo fp r o d u c t s a s s e m b l yc o n s t r a i n t so fm e c h a n i c a lp r o d u c t sm u s tb ec o n s i d e r e di n p r o d u c t i o ns c h e d u l i n g b e c a u s em e c h a n i c a l p r o d u c t s a r em o s t l ya s s e m b l yt y p eo n e s s o a n o t h e rs c h e d u l i n gp r o b l e md e r i v e s - - a j s p ( a s s e m b l yj o b s h o ps c h e d u l i n gp r o b l e m ) w h i c h i sl e s si n v e s t i g a t e d r e s e a r c hi nt h sp a p e rf o c u s e so nr e l a t e da l g o r i t h mf o ra j s pa n dh a sv e r y i m p o r t a n tp r a c t i c a ls i g n i f i c a n c e i na d d i t i o n , p r o b l e mm o d e l i n ga n da l g o r i t h mo p e r a t o r s d e s i g n i n ga r em o r ed i f f i c u l tf o re x i s t a n c eo fs t r o n ga s s e m b l yc o n s t r a i n t s ，s ot h er e s e a r c ha l s o h a sg r e a tt h e o r yv a l u e f i r s t l y ，t h ep a p e rd e s c r i b e sa s s e m b l yj o b s h o ps c h e d u l i n gp r o b l e mi nd e t a i lt h r o u g h m a t h e m a t i c a lm o d e l i n ga n dg i v e st h ec l a s s i c a la s s e m b l ys t r u c t u r ea n da s s e m b l yc o n s t r a i n t s r e l a t i o n s h i p t h e nt h ee n c o d i n gs c h e m ea n ds e l e c t i o no p e r a t o ra r eb o t hd e t e r m i n e dw h e n s u m m a r i z i n gt h ek e yt e c h n o l o g ya n de v o l u t i o np a r a m e t e r so fg e n e t i ca l g o r i t h m ( g a ) ，a n d s e v e r a lk i n d so ff i t n e s sf u n c t i o n sa l ed e s i g n e d t w og e n e t i ca l g o r i t h m sa r ep r o p o s e df o r a j s p - - e n t i r es o l u t i o ns p a c eg e n e t i ca l g o r i t h ma n df e a s i b l es o l u t i o ns p a c eg e n e t i c a l g o r i t h m ( f s s g a ) t h ed e s i g no fr e p a i ro p e r a t o ri st h em o s td i f f i c u l tp o i n ti nd e s i g n i n ge n t i r e s o l u t i o ns p a c eg e n e t i ca l g o r i t h m t w on e wr e p a i ro p e r a t o r st d r a ( t o p - d o w nr e c u r s i v e l y a d j u s t m e n t ) a n dg e ( g e n e se x c h a n g eb a s e d o nf a t h e rl i n k l i s t ) a r ep r o p o s e di n t h er e s e a r c h t h e ya r ec o m p a r e di nd e t a i l 、历廿lo p e r a t o rb a s e do nd e s i g ns t r u c t u r em a t r i x - - d s mi n i n f o r m a t i o ne n t r o p yl o s sa n dc l l r o m o s o m em a p ，a n dt h er e s u l t ss h o wt h a tt d r aa n dg ec a n r e s e r v ep o p u l a t i o nd i v e r s i t yb e t t e rt h a nd s mi ng a s u b s e q u e n t l y ，s o l u t i o ns p a c es i z ei s a n a l y z e da n dc o m p u t i n gm e t h o di si l l u s t r a t e db ye x a m p l e ，a n di t sp r o v e dt h a tf o ra j s pt h e f e a s i b l es o l u t i o ns p a c es i z ei sm u c hs m a l l e rt h a nt h ee n t i r eo n e b a s e do nt h ea b o v ec o n c l u s i o n , t h ef e a s i b l es o l u t i o ns p a c eg e n e t i ca l g o r i t h mi sp r o p o s e da n dc o r r e s p o n d i n gf e a s i b l es o l u t i o n s p a c eo p e r a t o r sa r ed e s i g n e dt os e r v ef s s g a i n t h a tc a s e ，t h es e a r c h i n gs o l u t i o ns p a c ei sm u c h i i 大连理工大学硕士学位论文 s m a l l e rt h a nb e f o r ea n dt h er e p a i ro p e r a t i o ni ss a v e d ，s ot h ea l g o r i t h me f f i c i e n c yi si m p r o v e d g r e a t l y i na d d i t i o n ，l a r g es c a l ep r o b l e me x p e r i m e n t ，l i t e r a t u r ep r o b l e m sc o m p a r i s o n e x p e r i m e n ta n de n g i n e e r i n gi n s t a n c ee x p e r i m e n ta r ep e r f o r m e d f i n a l l y ，v e r yg o o dr e s u l t sa r eo b t a i n e di nas e r i e so fe x p e r i m e n t sf o rn e wa l g o r i t h ma n d o p e r a t o r s t h e r e i nt h er e s u l to fr e p a i ro p e r a t o r sc o m p a r i s o ne x p e r i m e n tp r o v e st h a tt w on e w r e p a i ro p e r a t o r sr e s e r v em o r ep o p u l a t i o nd i v e r s i t ya n d a r eh e l p f u lf o rg at oe v o l v ea n d s e a r c ho p t i m a ls o l u t i o n t h eg a e x p e r i m e n tr e s u l ti n d i c a t e st h a te n t i r es o l u t i o ns p a c eg e n e t i c a l g o r i t h mh a sp r e f e r a b l ef e a s i b i l i t ya n do p t i m i z a t i o na b i l i t y t h er e s u l t so fa l g o r i t h m s c o m p a r i s o ne x p e r i m e n ta n dl a s tl i t e r a t u r ep r o b l e m sc o m p a r i s o ne x p e r i m e n tb o t hd e m o n s t r a t e t h a tf s s g ai sm u c hb e t t e rt h a no t h e ra l g o r i t h m sn o ti np e r f o r m a n c ea n dq u a l i t y a n dt h e r e s u l to fe n g i n e e r i n gi n s t a n c ee x p e r i m e n ti n d i c a t e st h a tt h ed e s i g n e da l g o r i t h m sc a nb e a p p l i e dt op r a c t i c a ls i t u a t i o nv e r yw e l l k e yw o r d s ：p r o d u c t i o ns c h e d u t i n g ；g e n e t i c a l g o r i t h m ；a s s e m b t yc o n s t r a i n t s ； p o p u t a t i o nd i v e r s i t y ；c h r o m o s o m e sm a p l - 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：基王装配约塞鲍扭越芒昌生芒调度箕洼珏究 作者签名： 墼! 主 幽日期：一圣翌2 年卫月2 尘日 导师签名：号l 乔为荔一 日期：掣年丝日 纱1 大连理工大学硕士学位论文 1 绪论 1 1 课题研究背景 从上世纪8 0 年代末至今，世界经济开始了全球化的过程，中国自从加入w t o ，也 开始真正融入经济全球化的浪潮中去。期间中国的制造业经历了翻天覆地的变化，面临 着前所未有的机遇和挑战。尤其在当今经济危机的严峻形势下，整个国内外市场环境发 生了剧烈的变化，传统的大批量重复性加工生产模式已经难以适应市场需求，单件小批 量的定制型生产以其快速响应市场、满足用户个性化需要等特点逐渐成为现代制造业的 主导潮流。生产方式的改变最直接影响的是车间的生产方式。 、一，一 图1 1典型制造系统信息流图 f i g 1 1 i n f o r m a t i o nf l o wc h a r tf o rc l a s s i c a lm a n u f a c t u r i n gs y s t e m 车间生产的一个很重要的方面是生产调度，在企业制定主生产计划过程中，调度方 案是很重要的一个环节。调度方案直接决定了产品的生产周期、生产成本，从而间接决 定了企业的竞争力和生存能力。在学术上车间生产被抽象为车间作业( j o b s h o p ) 模型， 基于装配约束的机械产品生产调度算法研究 在过去的几十年中，人们对j o b s h o p 问题进行了详细深入的研究，针对不同的目标进行 优化，取得了很多显著的成果。研究的焦点是如何在满足资源约束、交货期约束和工艺 路线等条件下，达到产品的加工时间、制造成本等最优的目标，以快速响应市场和提高 市场竞争力。调度是给一批任务分配一组有限的资源，是有一个或多个优化目标的决策 过程。企业中的资源可以有很多形式。资源可以是车间中的一台机器，某种设备的操作 人员，生产所需的原材料等。优化目标也是多种多样，可以是完工时间最短、提前拖期 惩罚最小和成本最低等。调度从技术实现的角度来说有很大的难度。它的难度和解决组 合优化问题和随机问题模型的难度相当。在现代制造业中，调度具有很重要的地位，它 和制造系统中其余决策部分紧密相联。图1 1 表示的是典型制造系统中的信息流图。 1 2 制造企业生产类型及特点 产品制造涉及到的行业甚多，产品种类千变万化，制造过程及产品工艺也是多种多 样。 ( 1 ) 基本工艺类型划分 产品的生产类型可以分为两大类：流程型和离散型。这两种方法采用不同的生产技 术和生产管理方法。 流程型生产的特点：工艺过程串行、连续，有固定顺序；生产过程自动化程度高； 常见的应用领域：化工、制药和造纸等行业。 离散型生产的特点：无装配约束的装配工件可以并行进行加工；多种加工设备可以 组合使用；应用行业：汽车、机床、电子设备、服装业等。 流程式生产的工艺路线中的前后衔接工序的顺序是固定不变的，生产过程是连续进 行的，中间不能中断。而离散型生产过程具有装配依赖的特点，即产品不仅通过加工过 程进行物理变换，还能通过装配组合装配出新的装配体，因此生产过程中的齐套性的保 证至关重要，直接涉及到生产的效率和节拍。 ( 2 ) 按生产批量划分 按产品生产量划分，可分为少品种大量、中量( 成批) 和多品种少量。而在成批生 产中，又可划分为大批生产、中批生产和小批生产。由于大批和大量生产特点相近，单 件和小批生产特点相近，所以在实际工作中，通常分为大量大批生产、成批生产和单件 小批生产。在一般情况下，大批大量生产具有生产稳定、效率高、成本低、管理工作简 单等特点。但也存在着投资大、适应性差和灵活性差等特点。这样会给产品更新换代带 来巨大损失。单件小批生产，由于作业现场不断变换品种，作业准备改变频繁，造成生 大连理工大学硕士学位论文 产能力利用率低( 人和机器设备的闲置等待) 所以生产稳定性差、效率低、成本高、管 理工作复杂等。因此，必须尽力做好作业准备、作业分配、作业进度计划和进度调整等 工作。中批生产特点介于上述二者之间。 ( 3 ) 按企业组织生产特点划分 按企业组织生产特点，可以把加工装配型生产分为备货型生产( m a k e t o s t o c k ，m t s ) 与订货型生产( m a k e - t o o r d e r ，m t o ) i 罱j 种i l j 。 备货型生产也称存货型生产或按库存生产，是在对市场需求量进行预测的基础 上，有计划地进行生产，产品有库存【2 j 。 型生产是指按用户订单进行的生产。用户可能对产品提出各种各样的要求，经 过协商和谈判，以协议或合同的形式确认对产品性能、质量、数量和交货期的要求，然 后组织设计和制造。例如，锅炉、船舶等产品的生产，属于订货型生产1 2 。 ( 4 ) 按生产的连续程度划分 连续生产它是长时间连续不断地生产一种或很少几种产品。生产的产品、工艺 流程和使用的生产设备都是固定的、标准化的，工序之间没有在制品储存。例如，油田 的采油作业等； 间断生产输入生产过程的各种要素是间断性地投入。生产设备和运输装置必须 适合各种产品加工的需要，工序之间要求有一定的在制品库存。例如，机床制造厂、机 车制造厂、轻工机械厂等。 1 3 国内外研究现状 车间作业调度问题( j s p ) ( n m j c , ) 考虑n 个作业在m 台机器上的分配问趔3 】： 每个作业由一系列工序组成，而且必须不被中断地在每台机器上进行加工。车间调度问 题属于组合优化问题，当问题规模较大时，解集大小会爆炸式增长，属于n p h a r d 问题。 车间调度分为静态调度和动态调度。传统的静态调度满足如下的条件假设1 4 1 ：被调度的 工件集合是确定的；工件的加工时间是确定的；加工工件的机器不会出现故障。而动态 调度的作业数目是动态变化的，所以工件的集合是动态的。调度环境可分为：单机、相 同并行机、异速并行机、无关并行机、流水车间、柔性流水车间、作业车间、柔性作业 车间和开放车间p j 。 车间调度问题始于2 0 世纪5 0 年代。1 9 5 4 年，j o h n s o n 对两台机床的f l o w s h o p 问 题进行了研究，提出了解决车间调度领域的部分特殊问题的优化算法，这代表着车间调 度理论研究的开始。上世纪六七十年代经典调度理论建立起来。1 9 世纪7 0 年代后期调 度理论研究的深入及各种交叉学科的发展，涌现出了许多新的车间调度理论与方法，有 基于装配约束的机械产品生产调度算法研究 以下这些：基于运筹学o r 方法、基于控制的方法、基于启发式规则的调度方法、基于 人工智能的方法、整数规划、仿真调度方法、基于d e d s 的解析模型方法、模拟退火( s a ) 、 禁忌搜索、粒子群算法、蚁群算法以及拉各朗日约束松施法等。d a v i s 在1 9 8 5 年发表了 产品调度的论文，首次将遗传算法( g a ) 应用于产品调度，使用g a 求得车间调度的近似 最优解，为遗传算法在车间调度领域的研究奠定了很好的基础。此后，学者对此做了大 量的深入研究。以d a v i deg o l d b e r g 为代表的研究学者先后提出了一些具有突破性的新 方法和改进，完善了g a 在车间调度中的应用，同时通过在解决一系列经典的测试问题 ( b e n c h m a r k ) 的过程中取得了最优解( 或近似最优解) ，进一步证明了g a 在解决n p h a r d 问题方面的可行性和有效性1 6 。 调度的大部分问题都是n p h a r d 问题，虽然对它的研究已有几十年的历史，但至今 尚未形成一套系统的方法和理论，理论研究和实际应用之间还存在着很大的差距。调度 问题的发展方向有以下几种： ( 1 ) 寻求新的最优算法。基于最优化的方法，寻找具有多项式复杂性的最优化算法 几乎不可能，但其解具有最优性，至今仍是一个研究的方向。 ( 2 ) 解决基于统计优化方法的计算时间复杂性问题。各种基于统计优化的方法，如 模拟退火、遗传算法等，提供了调度问题解决的新途径，但也存在和其他算法类似的枚 举问题，收敛到最优解较难，而且判断解的最优性很难，这方面需要进一步的研究。 ( 3 ) 探索新的近似调度算法，达到解的优劣性和求解难度相平衡。各种近似和启发 式方法，如基于规则的算法等，在合理的时间内产生比较满意的解。但其对可行调度的 研究是关键问题。 ( 4 ) 探索车间计划和调度问题的集成求解方法，在实际的车间调度中，车间计划与 车间调度往往是分层进行的，但这可能造成计划在实际调度中不可行的问题，如何将计 划与调度结合考虑，以求总体的优化也是需要进一步研究的【7 】。 作为j s p 的扩展，装配型产品车间调度( a j s p ) 在j s p 完成后附加了装配阶段。完 工的工件( 这里的工件是广义的，包括装配体工件和普通工件) 如果来自同一产品的物 料清单( b o m ) 就需要进行装配。装配操作可以在所有所需装配工件完工之后和资源满 足的情况下立刻开始。解决a j s p 不仅需要确定机器上工件的加工工序顺序，还要确定 装配阶段的工序的顺序。所以，a j s p 比传统的j s p 的解决难度更大，也是典型的n p 。h a r d 问题。a j s p 的复杂性主要取决于构成产品的工件的数量、每个工件的工序规模和整个 产品的装配层次结构。 大连理工大学硕士学位论文 在过去几十年里，人们已经对j s p 进行了深入详尽的研究。然而，针对a j s p 的研 究工作和文献却比较少哺j 。以下是近年来在a j s p 方面或者和装配型产品调度有关的重 要文献。j u n g u gk i m 等研究了具有多层产品结构和工件间具有装配先后约束关系的产 品的调度问题，其中应用了s a 和g a 两种智能算法，并对两者进行了比较【9 j 。m c k o y 和e g b e l u 提出了一种1 2 步启发式算法来最小化a j s p 的产品流程时间。他们将提出的 启发式算法和混合整数规划针对一些测试问题进行了比较，结果表明混合整数规划在解 质量方面表现突出，然而为了获得最优解却耗费大量的计算时间。于是，当问题规模很 大所需计算较多时，他们提出的算法就更可取【l0 1 。p p o i n g c h a r e n 等针对具有深层产品 装配结构和多重资源约束的复杂产品调度问题开发了一种基于g a 的调度工具g a s t ， 并提出了一种修复过程来识别和纠正不可行调度方案。他们将基因编码成两部分，一部 分是产品结构标识，另一部分是工序号。他们的修复算子是基于复制原理，通过交换冲 突基因来修复工序序列。然后通过一个实际的例子寻找到遗传算法的合适参数值，在给 定执行时间内搜索到最优解i l 。g u i d e 等提出一种处理两个再加工产品的程式化模型， 并测试了静态优先规则在具有拆装和重装配的再加工车间中的共享机器上的性能。在他 们的研究中，修理车间包括一个拆卸区，一个修理区和一个装配区。每个修理的工件有 自己唯一的、固定的工序序列，所以修理车间调度问题实际上可以认为是a j s p ；他们 指出普通分派规则在中大规模的不确定层次结构问题上可能会比复杂优化算法表现更 优列1 2 】。s t h i a g a r a j a n 等针对动态装配作业车间提出一些分派规则来最小化提前拖期 惩罚和作业总完工时间l l 引。z x g u o 等为服装装配构造了一个模型，把g a 应用于一 个混合型和有多级产品装配环境的车间作业调度中，目的是最小化提前拖期惩罚【1 4 1 。 f t s c h a n 等采用一种高效算法和简单分派规则算法首次将批量流和a j s p 结合起来 【l5 1 。砧ia y a s s i n e 等提出一种稳健遗传算法，将其和局部搜索算法相混合来最小化多 资源约束下的多产品调度问题的总完工时间，同时保证不违反资源约束和先后次序约 束。他们在文章中利用设计结构矩阵( d s m ) 来修复不可行的染色体来避免调度序列的 先后顺序冲突i l 州。t c w o n g 等将批流量技术扩展到有资源约束的装配车间作业调度问 题上来最小化所有最终产品的延迟代价。为了增强他们模型的有用性，两个实验因素被 引入，一个是通用零件率和工作量标识。随后一种基于遗传算法的创新方法被提出来。 为了检验方法的有效性，粒子群算法被选作测试方法【l 丌。近年来，国内学者也对装配型 作业调度问题进行了尝试性的研究。其中有代表性的有谢志强等的针对装配型产品调度 问题提出的一系列复杂规则算法。 基于装配约束的机械产品生产调度算法研究 1 4 本文的研究目的和意义 车间调度研究可以为企业提供良好的作业生产排序方案，利于企业制定合理的主生 产计划，合理分配各种资源，减少等待时间，加工准备时间，提高了设备利用率，减少 在制品，从而减少资金占用，降低成本，而且也推动了一大批智能算法，如遗传算法、 模拟退火算法、蚁群算法和神经网络等的发展和进步。 但以往的车间调度研究基本上都集中在加工车间上，如经典j s p 问题都是以加工车 间为背景的，而对装配型产品生产调度的研究却不多。j s p 对多个彼此独立的生产作业 进行调度，生产过程不涉及产品的装配过程。然而，实际中许多产品都是装配型产品， 最后需要进行装配的工艺过程。若某个工件过早生产完成，只能等待其兄弟工件，却不 能进行装配操作【1 8 】【1 9 1 。这样有可能带来的后果就是完工工件较早地占去了生产资源，造 成兄弟部件不能完成，而完工工件只能等待，无法完成装配，丧失了协调性和一致性， 拖长了工期。研究装配型产品的调度可以使装配工件的生产协调有序，步调一致，缩短 工期，提高设备利用率。 本文针对装配型产品的生产过程和工艺流程的特点，在遗传算法应用过程中从两个 方向进行了探索研究：一：将传统遗传算法( s g a ) 应用于全域搜索，提出两种非常优秀 的修复算子，比以往提出的d s m 算子在遗传多样性保持上和最后的优化结果上都具有 明显的优势；二：开发出可行域遗传算法( f s s g a ) ，在遗传算法的各阶段通过运用各种 可行域算子来保持染色体的可行性，缩小了搜索空间，提高了搜索效率。 本文为遗传算法应用于装配型产品调度提供了比较有价值的参考，修复算子的研究 为其他智能算法应用于装配型产品调度问题奠定了基础，具有很强的理论和应用价值。 1 5 本文主要内容 第一章：介绍问题的研究背景、国内外的研究现状和问题研究的目的和意义。 第二章：对车间调度问题进行描述，建立a j s p 的数学模型，对遗传算法的基本概 念和关键技术进行概述，并确定本文设计算法的一些相关技术。 第三章：设计实现a j s p 的全空间遗传算法，设计两种新的修复算子，并在信息熵、 染色体图谱、g a 实验等几个方面进行相应的对比实验，设计基于贪婪式前插的活动派 工调度。 第四章：对可行解空间大小进行计算和分析，设计实现a j s p 的可行域遗传算法， 设计并实现用于支撑可行域遗传算法的可行交叉算子和可行变异算子，并进行相应的对 比实验。 大连理工大学硕士学位论文 第五章：进行大规模实例实验、文献实例对比实验和工程实例实验来验证所设计算 法的有效性，介绍开发的相关界面和使用的工具语言。 1 6 本章小结 本章从研究问题的背景入手，引出装配型产品调度问题，并对此类问题的国内外研 究现状和文献进行了回顾，然后说明了本文的研究目的和意义，最后给出本文研究内容 的总体结构。 基于装配约束的机械产品生产调度算法研究 2 a s p 问题描述和遗传算法概述 2 1a j s p 问题描述 2 1 1 车间调度问题描述 总的说来，车间调度就是将一个加工任务集在一个加工机床集上进行分配，以满足 一个性能指标集。从数学规划的角度看，车间调度问题可表达为在等式或不等式约束下， 对目标函数的优化。典型的车间调度问题包括一个要完成的作业集，每个作业由一个工 序集组成，各工序需要占用机床或其它资源，并且必须按一定的可行工艺次序进行加工， 每台机床可加工工件的若干工序，并且在不同的机床上能加工的工序集可以不同。调度 的目标是将作业合理地安排到各机床，并合理安排作业的加工次序和加工开始时间，使 约束条件被满足，同时优化一些性能指标【7 】。 在实际的f m s 的车间调度中，由于要考虑刀具、托盘和物料搬运系统的调度问题， 因此不但包括作业调度问题，而且也应考虑资源分配问题。“研究了单机、多台并行机 的作业与资源的调度问题1 2 0 1 。目前大部分研究集中在作业调度上，没有考虑资源分配， 一般都直接将资源作为约束处理。为了解决车间调度问题，在数学建模分析中大多采用 基于数学规划的模型。 车间调度问题一般可以描述为n 个工件在m 台机器上加工，一个工件分为若干道工 序，每个工序可以在若干台机器上加工。每一台机器在每个时刻只能加工某个工件的某 道工序，只能在上道工序加工完成后才能开始下一道工序的加工，前者称为占用约束， 后者称为顺序约束，装配作业则需满足子件的所有工序都加工完后才能加工父件的工序 【2 l l ，称为装配约束。 车间调度问题的决策内容包括分配决策( 工件的加工顺序) 和时间决策( 工件各工序 的加工时间) 以及路径决策( 工件工序的加工设备的分配) 。 车间调度问题的特点是多个工件在有限的机器上加工，每台机器在切换不同工件生 产时需要一定的准备时间。切换加工次数增加有利于减少工件的库存，但导致生产率下 降。因此，需要在库存成本和工件切换加工频率之间取得平衡。生产的柔性体现在设备 使用和设备安排两个方面，设备使用的柔性是指设备可用于多个零件的多个工序的加工； 设备安排的柔性是指工件的设备加工路径不是固定和预先确定的，具有可选的路径，可 以通过将若干设备组织为一条或者多条生产线加工一种工件，使得该工件的生产率最 大。 凡琏理i 人学硕f j 学付论文 2 12a j s p 问题数学模型 ( 1 ) 数学模型 a j s p 的研究对象是装配型产品，作为j s p 问题的扩展a j s p 在j s p 后附加了产i 吼 各级： 件的装配操作。图21 所示的是一种经典的多层次产品装配结构。 州n ? 雌2 装配件j 2 中m 绒* j ， r r 裂 z 体) 56 7 o 0 o 1 f 川j 欲 二f n # “) 蚓21 典型多级装配结构 f i 9 2 l c l a s s i c a l m u l t i - l e v e la s s e m b l y q c t u m 在图2 1 所示的结构中，有装配体工件2 、3 、5 和普通工件4 、6 、7 、8 、9 、1 0 组 成，子装配体由更f 缴的予装配体工件和普通工件组成。对于装配树中的某个节点而占， 它可能有h 道在不同机器卜完成的工序纽成口“。 不妨似设有这么一个装配环境，经过一系列的半成品过程，其巾的产品制造系统将 躁材料转变成最_ | 舌的合格装配产品。假设其中有w 台机器 m ，m 埘。 。现在考虑完 成个城配产品 令，o 一c 卅 表示它的各级子装配体( 半成品) 和叶节点工什。 每个件有一个独立雎。的工序序列，用口= i o , 。q ：，“ 表示。其中某道工序需 要在w 行机器中的一台 0 上加工所需的加工时间为，一 在本文的研究中问题模型是基于一些如下的假设： 非抢占式：某道工序在某台机器上加工，一旦开始不能被中断。 部分资源无限：没有原材料不足、机器故障和操作人员缺勤的情况出现。 串行加工性：台机器l 在某时刻只能加工。道工序，没有并行加工能力。 问题模型需要满足的一些约束如f ： ( 2 ) 分配约束 工序必颁被加，而且h 能微对应的机器加工一次。 基于装配约束的机械产品生产调度算法研究 厶= 1 g 每台机器必须至少加工一道工序。 厶1 p ( 3 ) 先后约束 工件工序序列的先后顺序约束 某道工序必须在它的上道工序完成之后才能考虑加工。 s u + t u s i l j n ， 父子间的装配先后约束关系 莲t 。7 5 璺塞 图2 2 父子间工序约束关系 f i g 2 2 c o n s t r a i n e dr e l a t i o n s h i pf o rf a t h e r - s o no p e r a t i o n s ( 2 1 ) ( 2 2 ) ( 2 3 ) 图2 2 表示的是装配树分支的装配约束关系。9 1 a s t 表示工件9 的工序序列中的最后 一道工序，而5 f i r s t 表示工件5 的工序序列中的第一道工序。 只有在其所有子件的工序都完成之后，装配体的第一道工序才能考虑加工。即需要 满足公式2 4 ，其中e 代表a 装配子件i 的最后一道工序： m a r e ：，彰，e ，e l ( 2 4 ) ( 4 ) 目标函数 将产品完工时间( m a k e s p a n ) 的最小值作为目标函数。数学表示如下： m i nz ，w i t hz = m a x i n k , ，r a k e ，m 吒) ( 2 5 ) 2 2 遗传算法概述 2 2 1 遗传算法的生物学基础 地球中的生物能够不断繁衍并不断进化成更高级的形式，这其中必定有优秀的机制 在发挥作用，著名博物学家达尔文开创的生物进化论揭开了其神秘的面纱。生物 进化论的核心思想是“物竞天择，适者生存。 大连理工夫学硕十学位论文 达尔文的外界选择学说仅仅解释了生物的变化被选择性的积累过程，但并不能解释 另一种现象，即促使生物产生性状变化的物质基础或者说是根本原因。这一根本原因直 到1 9 世纪中期才得到初步解释。生物学家盂德尔经过长达数年的研究，对各种豌豆植 株进行杂交培育实验，发现了染色体和基因决定和改变生物性状的规律，并提出了著名 的遗传变异学说。他认为生物体内存在基因物质，能够从父代个体中遗传给子代个体， 因此后代个体在许多性状上与父代个体相似。这是物种能够保持相对稳定的根本原因。 同时指出，生物个体间的基因在父代个体间的交配过程中发生了互换重组，并且在细胞 分裂和基因复制过程中发生了突变，因此这又是生物的性状发生微弱变化的物质基础和 根本原因。而自然选择则是剥这种已经发生的变化进行了定向的选择和积累。 在细胞核中，有种微小的丝状化台物，称为染色体( c h r o m o s o m e ) 。染色体山许多 基i n ( g e n e ) ) 4 段组成，基因是生物遗传物质的载体，决定了生物的各种遗传性状，是遗 传的基本单位。随着分子生物学等的发展，人们已经知道，真t f 产生遗传现象的物质是 一种叫脱氧核糖核酸( d e o x y f i b o n u c l e i ca c i d ，简称d n a ) 的大分子有机物。 幽23d n a 分子示意图 f i g23 s c h e m “i cd i a g r a m f o r d n a 当生物个体中的细胞分裂时，染色体中所携带的遗传物质即d n a 通过复制 忡p r o d u c t i o j 被传递到下一代细胞中，于是子代生物就继承了父代生物的遗传信息，进 而表现出与父代个体相似的性状表现。当繁殖方式为有性生殖时，细胞分裂中的两个同 源染色体将进行交叉( c r o s s o v e r ) ，交叉重组后的新染色体分别继承了来自父代个体双方 的部分遗传信息，这一变化导致子代个体与父代个体间产生了细微的差别。染色体交叉 即两条d n a 双螺