（控制理论与控制工程专业论文）装配车间生产调度优化暨net平台下的系统开发.pdf

| | 1 1 1 iii i i ii i1 u l lii y 17 614 7 3 a ss e m b l ys h o psc h e d u l i n g o p t i m i z a t i o na n dd e v e l o p m e n to f t h es y s t e mo n n e tp l a t f o 蹦 at h e s i ss u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro f e n g i n e e r i n g b y m am e i s u p e r v i s e db y p r o f y a nh o n g - s e n s c h o o lo f a u t o m a t i o n s o u t h e a s tu n i v e r s i t y m a r c h2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：墨董日期：丝! ! ：墨：墨? 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 研究生签名：墨兰导师签名：期：坐弓；p 摘要 装配车间生产调度优化暨n e t 平台下的系统开 发 硕士研究生：马美导师：严洪森教授 东南大学 摘要 随着全球经济的快速发展，市场竞争越来越激烈，企业要想在这样的环境中生存并 取得很好的经济效益，就迫切需要加强企业的信息化建设。文中研究了敏捷制造环境下， 装配车间生产调度优化问题，同时论述了计算机集成制造环境中，n e t 平台下基于c s 三层体系结构的装配车间生产调度优化系统的开发。 依据所研究问题的实际情况，某航空发动机装配车间主要包含部件组装和试车台两 个方面，因此论文分两个方面对问题进行探讨：一是装配车间试车台排序优化问题，二 是部件组装调度优化问题，然后分别对这两个问题进行了数学建模，并选择与设计算法 来求解模型。 首先，针对试车台排序优化问题，分析了试车台排序特征，建立了试车台最优排序 的旅行商模型( t s p ) ，将遗传算法和分散搜索算法相结合以提出一种遗传分散搜索算法 对该模型进行求解，实现试车台最优排序。通过具体算例研究，对算法进行了比较和性 能分析。 其次，装配车间部件组装调度可抽象为典型的i o b - s h o p n p 难问题，基于上述已求出 的试车台排序优化结果，以上述最优排序结果作为产品的投产顺序，从而将部件组装调 度问题转化成典型的i o b s h o p l n 题，简化了实际问题；进而建立数学模型，采用改进遗 传算法，对问题进行求解，获得装配车间部件组装最优序列；最后通过具体算例研究， 对算法进行了比较和性能分析。 接着，文中进行了装配车间调度优化系统的总体架构设计、开发工具的选择、u m l 建模和数据库设计，给出了设计过程中的部分用例图、类图、顺序图、协作图以及数据 库模型。同时，针对该系统实现时出现的难点，本文还具体研究了系统开发过程中的一 些关键技术，如存储过程的设计、查询优化设计、权限管理等等。 最后，对论文的内容进行了总结，并讨论了需要进一步研究的一些问题。 关键词：生产调度，遗传分散搜索算法，改进遗传算法，n e t ，u m l a b s i r a c t a ss e m b l ys h o psc h e d u l i n g o p t i m i z a t i o na n dd e v e l o p m e n to f t h es y s t e mo n n e tp l a t f o r m m a s t e rc a n d i d a t e ：m ame i s u p e r v i s e db yp r o f y a nh o n g - s e n s o u t h e a s tu n i v e r s i t y a b s t r a c t w 1 t l lt h ed e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n , t h em a r k e tc o m p e t i t i o ni sb e c o m i n g f i e r c e r e n t e r p r i s e sp r e s sf o ra c c e l e r a t i n gt h ea p p l i c a t i o no fi n f o r m a t i o n i z a t i o nt os u r v i v ea n d s u c c e e di nt h i se n v i r o n m e n t o p t i m i z a t i o nf o r t h es c h e d u l i n gp r o b l e mo ft h ea s s e m b l ys h o pi n a g i l em a n u f a c t u r i n g i ss t u d i e dh e r e n ed e v e l o p m e n to fa s s e m b l ys h o p s c h e d u l i n g o p t i m i z a t i o ns y s t e mi si m p l e m e n t e do nc st h r e el a y e r sa r c h i t e c t u r ei nc o m p u t e ri n t e g r a t e d m a n u f a c t u r i n g ，b a s e do n n e tp l a t f o r m a c c o r d i n gt ot h ea c t u a ls i t u a t i o n , t w oa s p e c t so ft h ea v i a t i ce n g i n ea s s e m b l ys h o pa r e f o c u s e d l yd i s c u s s e d ：o n ei st h es e q u e n c eo f t h et e s tb e d a n dt h eo t h e ri st h es c h e d u l i n go ft h e p a r t i a la s s e m b l y t h em o d e l so ft h e s et w op r o b l e m sa r ep r e s e n t e ds e p a r a t e l y , a n dt h e nt h e a l g o r i t h m sa r ec h o s e na n dd e s i g n e di no r d e r t os o l v et h em o d e l s f i r s t l y ，t h et s p ( t r a v e l i n gs a l e s m a np r o b l e m ) s e q u e n c i n gm o d e lo ft h et e s tb e dh a s b e e ne s t a b l i s h e da n db yc o m b i n i n gg e n e t i ca l g o r i t h m 埘t l ls c a t t e rs e a r c h i n g ，t h e g e n e t i ca n d s c a t t e rs e a r c h i n ga l g o r i t h m ( w h i c hi su s e dt os o l v et h i sm o d e l ) i sp r o p o s e do nt h eb a s i so f a n a l y z i n gf o rc h a r a c t e r i s t i c so ft h et e s tb e d b yu s i n gt h eg e n e t i ca n ds c a r e rs e a r c h i n g a l g o r i t h m ，t h eo p t i m i z e ds c h e d u l e sa r eo b t a i n e d t h r o u g hs e v e r a lc o m p u t a t i o n a le x a m p l e s ， t h ea l g o r i t h m sa r ec o m p a r e da n da n a l y z e d s e c o n d l y , t h es c h e d u l i n go ft h ep a r t i a la s s e m b l yc a nb ea b s t r a c t e di n t ot h et y p i c a l j o b - s h o pp r o b l e mw h i c hi sn ph a r dp r o b l e m b a s e do nt h eo p t i m i z e dr e s u l to ft h es e q u e n c e o ft h et e s tb e d ，t h es c h e d u l i n go ft h ep a r t i a la s s e m b l yp r o b l e mi st r a n s f o r m e di n t ot h et y p i c a l j o b - s h o pp r o b l e m t h e n , t h es e q u e n c i n gm o d e lo ft h ep a r t i a la s s e m b l yh a sb e e ne s t a b l i s h e d a n dt h em o d i f i e dg e n e t i ca l g o r i t h mh a sb e e nu s e dt os o l v et h i sm o d e la n do b t a i nt h e o p t i m i z e ds c h e d u l e s t h r o u g hs o m ec o m p u t a t i o n a le x a m p l e s ，t h ea l g o r i t h m sa r ec o m p a r e d a n da n a l y z e d t h i r d l y ，t h es t r u c t u r ed e s i g no ft h ea s s e m b l ys h o ps c h e d u l i n go p t i m i z a t i o ns y s t e m ，t h e c h o i c eo ft h ed e v e l o pt o o l s ，t h eu m l m o d e l i n ga n dt h ed a t a b a s ed e s i g na r ea d d r e s s e dh e r e s o m eu s ec a s ed i a g r a m s ，c l a s sd i a g r a m s ，s e q u e n c ed i a g r a m s ，c o l l a b o r a t i o nd i a g r a m sa n d d a t a b a s em o d e l so ft h es y s t e ma r ep r e s e n t e d a c c o r d i n gt o t h ed i f f i c u l tp o i n t si nt h e d e v e l o p m e n tp r o c e s s ，s o m ec r i t i c a lt e c h n i q u e sa r es t u d i e dd e t a i l e d l y , i n c l u d i n gt h ed e s i g no f s t o r e dp r o c e d u r e ，t h ed e s i g no fo p t i m i z e dq u e r ym e t h o d , t h ej u r i s d i c t i o nm a n a g e m e n t , a n ds o 0 n f i n a l l y ，t h et h e s i s i ss u m m a r i z e da n dd i s c u s s e da b o u ts o m ea s p e c t st h a ts h o u l db e s t u d i e di nt h ef u t u r e k e yw o r d s ：p r o d u c t i o ns c h e d u l i n g ，g e n e t i ca n ds c a r e rs e a r c h i n ga l g o r i t h m ，m o d i f i e d 东南大学硕士学位论文 g e n e t i ca l g o r i t h m , n e t ，u m l m 目录 目录 摘要i a b s t r a c t i i 目萄专i v 第一章绪论1 1 1 课题背景。l 1 1 1 装配车间生产调度系统概述1 1 1 2 装配车间生产调度问题的现状和趋势1 1 2 课题介绍。2 1 3 论文结构2 第二章装配车间试车台排序优化方案研究4 2 1 试车台排序优化研究概述4 2 2 装配车间试车台排序优化模型4 2 2 1 问题概述4 2 2 2 试车台排序优化模型5 2 2 3 试车台排序优化算法设计。6 2 2 4 实例求解和分析9 2 3 本章小结1 1 第三章装配车间部件组装调度问题的方案研究1 2 3 1 生产调度研究概述1 2 3 2 装配车间部件组装调度优化模型1 3 3 2 1 问题概述l3 3 2 2 部件组装调度优化模型13 3 2 3 算法设计1 4 3 2 4 实例求解和分析16 3 3 本章小结1 6 第四章装配车间生产调度优化系统的总体设计1 8 4 1 系统开发平台的选择18 4 2 系统整体架构的设计2 0 4 3 系统数据库的选择2 3 4 4 系统的模块划分2 4 4 5 系统的u m l 建模2 4 4 5 1u m l 简介2 4 4 5 2 系统的用例模型2 6 4 5 3 系统的静态建模3 2 4 5 4 系统的动态建模3 8 4 6 数据库设计4 0 4 6 1 数据库设计概述4 0 4 6 2 需求分析41 4 6 3 概念设计4 l 4 6 4 逻辑设计4 3 i v 目录 4 6 5 物理设计4 5 4 6 6 验证设计4 6 4 7 本章小结4 6 第五章系统开发过程中的实现技术4 7 5 1 系统的分层设计与实现4 7 5 1 1 用户界面层的实现4 7 5 1 2 业务逻辑层的实现5 0 5 1 3 数据访问层的实现51 5 1 4 组件调用关系5 2 5 2 存储过程设计5 4 5 3 触发器设计5 4 5 4 查询优化设计5 5 5 5 权限管理5 7 5 6 本章小结5 7 第六章总结与展望5 9 6 1 本文要点总结5 9 6 2 进一步的工作展望5 9 至| 【谢6 l 参考文献6 2 发表论文列表一6 5 v 第一章绪论 1 1 课题背景 1 1 1 装配车间生产调度系统概述 第一章绪论 制造业一直是推动各国国民经济发展的主要力量【l 】，随着科技发展和计算机科学的 迅速发展，传统制造业遇到了前所未有的挑战和机遇。为了赢得市场，制造企业必须提 供交货期短，质量好，价格低的具有竞争力的产品【2 】，以适应日益发展的市场需求。为 此国内外专家提出了很多新的观念，以高度柔性化，集成化，智能化的特点，对制造业 快速响应市场，提高产品质量，缩短产品制造周期，降低成本，增强企业竞争力起到了 重要作用。 目前，人们在研究生产制造的各个环节中，发现装配是影响制造时间和制造成本的 重要环节之一。随着并行工程、c i m s t 3 】的发展和应用，单个零件的生产已经实现了一定 程度的自动化和集成化。相比之下，装配生产还处于落后状态。有关资料显示【4 】，在工 业化国家中产品生产过程中3 0 的人力在从事有关装配生产的活动，超过4 0 以上的生 产费用用于产品的装配，产品装配需要的工时占整个产品生产制造总工时的4 0 - 6 0 。 使得产品装配问题已经成为产品制造过程中的一个“瓶颈 ，解决该问题迫在眉睫。 装配车间生产调度1 5 j 问题研究应运而生，装配车间生产调度主要任务是对可用的加 工设备集合、操作者集合以及原料集合在时间上进行加工任务的分配，通过任务调度来 解决资源的最优安排，为生产计划的执行和控制提供指导，实现生产能力的综合平衡。 装配车间生产调度根据上级下达的生产计划规定的产品品种、数量及大致的交货期的要 求对每个生产单位( 工段、班组、工人等) ，在每个具体时期( 月、日、班等) 内的生 产任务做出详细规定，使生产计划得到具体落实。实际生产过程中，生产计划调度实行 的成功与否，对减少在制品库存、提高交货期满意率、缩短供货周期和提高生产率都有 重要作用。 随着经济全球化的发展，企业的生产特性发生了根本性变化，客户需求的个性化、 市场变化的动态化，导致市场竞争越来越激烈。因而装配车间生产调度系统作为生产制 造中的一个重要环节，其重要性也愈加凸显。一个好的装配车间生产调度系统，可以有 助于实现最大完工时间最短、生产成本最低，这对于制造企业提高生产效率、降低生产成本， 更有效地满足市场需求具有重大意义。 1 1 2 装配车间生产调度问题的现状和趋势 装配车间生产调度是企业顺利生产的前提，是提高企业经济效益的重要条件和保 障。目前，装配车间通常根据调度人员的经验进行调度，当部件很多、工序复杂时，只 靠经验调度难以保证最优调度，而且这种经验调度没有科学性的保证，从而很难实现提 高生产效率和经济效益的目的。 另外，目前从事车间生产管理软件的开发公司和研究单位也很多。但这些现存的软 件中，多数是从财务管理和物料管理的角度开发的，对制造执行过程的管理涉及不深， 东南大学硕士学位论文 基本不能给出详细的工序级调度计划，不能完善解决调度过程中出现的复杂多变问题， 软件的适应性比较差。所以要想为企业带来巨大的经济效益，车间生产调度系统应充分 考虑到车间生产中的各种信息，为企业生产提供优化的计划调度方案，做到既满足生产 要求，又降低生产成本。此外，最近十年以来，计算机技术、网络技术以及数据库技术 的迅速发展和各种新思想的提出，极大地促进了车间计划调度系统的应用与发展。在网 络和数据库技术支持的基础上，车间调度系统与e r p ( e n t e r p r i s er e s o u r c ep l a n n i n g ) 系统 很好的实现了数据和信息的共享，适应用户多层次与多方位的需求。随着w e b 技术和 组件开发技术的日趋成熟和推广，调度系统软件开始由c s ( c l i e n t s e r v e r ，客户服务器) 模式向b s ( b r o w s e r s e r v e r ，浏览器服务器) 模式转变；系统开发方法也由传统的结构化 设计开发模式向应用面向对象设计、开发方法过渡；构建软件系统的方法趋向于将功能 代码开发成为具有独立功能的组件，并应用这些组件构建目标系统。因此软件工程和组 件技术的发展也为开发可重构的车间生产管理系统提供了最新的理论和工具。 1 2 课题介绍 本课题是国家8 6 3 计划先进制造技术领域现代制造集成技术专题探索导向类课题 ( 2 0 0 7 a a 0 4 2 1 1 2 ) 和国家自然科学基金资助项目( 6 0 9 3 4 0 0 8 ，5 0 8 7 5 0 4 6 ) 。 课题的主要内容是研究装配车间生产调度优化问题，依据所研究问题的实际情况， 航空发动机装配车间主要包含部件组装和试车台两个方面，因此论文主要研究两个方面 的问题装配车间试车台排序优化问题及部件组装调度优化问题，然后分别对这两个 问题进行了数学建模，并选择与设计算法来求解模型。同时完成了计算机集成制造环境 中，发动机装配车间生产调度优化系统的开发，下分两个子系统，分别是：试车台排序 优化子系统和部件组装调度优化子系统，分别对应于本文所研究的两个主要课题。并通 过大量算例验证了本文所采用的优化算法在装配生产调度中的应用极大地提高了企业 装配生产调度的效率和准确度，并因此能为企业取得显著的经济效益。 因为该系统的应用主要在企业决策层，故采用c s 结构，相对b s 结构可以减小系 统运行的复杂性同时缩短算法运行时间。与n e t 相比v c + + 的运行速度更快，因而选择 使用v c + + 6 0 编制算法。考虑到n e t 的用户界面制作简单美观，对数据库的连接及操 作更加简洁高效，所以总系统用户界面和基础数据管理模块均采用c 撑n e t 开发。 开发过程中同时考虑了软件的开放性，提高了系统的可扩展性、高质量和稳定性。 系统结构清晰，维护方便，可适应不断变化的业务要求。 由上可见，本课题的研究，既是保障当前企业生产经营活动的需要，也是企业适应 市场变化，不断寻求进一步发展的需要。 1 3 论文结构 本文研究了在敏捷制造环境下通过优化算法实现发动机装配车间试车台排序优化 和部件组装调度优化。针对这两个方面分别建立了优化模型，选择、设计了相应的算法 予以求解，然后提出了装配车间生产调度系统的整体架构，在此基础上分析、设计、实 现了此生产调度总系统，总系统下根据研究的侧重点不同构建了两个优化子系统，并对 子系统的设计也做了进一步详细地分析。论文结构如下： 第一章绪论：简要介绍了课题的背景及其研究意义。 第二章装配车间试车台排序优化方案研究：根据总装车间的实际情况，研究了装配 2 第一章绪论 车间试车台排序优化问题。 第三章部件组装调度优化问题的方案研究：根据总装车间的实际情况，研究了总装 车间部件组装的调度优化问题。 第四章装配车间生产调度优化系统的总体设计：首先研究了系统开发平台和开发工 具的选择，然后设计系统整体架构，选择合适的数据库管理系统：对装配车间调度优化 系统进行模块划分，然后分别对系统的各个模块，给出了需求分析及u m l 建模，其中 包括用例图、类图、顺序图、协作图等等；最后详细讨论了数据库的概念设计、逻辑设 计、物理设计和验证设计。 第五章系统开发过程中的实现技术：对上一章的结果进行细化，针对装配车间生产 调度优化系统实现时出现的难点，详细研究了系统开发过程中的关键技术，如存储过程 的设计，数据统计多样性技术等等。 第六章总结与展望：总结论文中的工作，并提出了有待进一步研究的问题。 东南大学硕士学位论文 第二章装配车间试车台排序优化方案研究 2 1 试车台排序优化研究概述 调度问题是一类应用很广泛的问题，如车辆调度、采购和销售的经营策略、飞机航 线的分配等。它们的本质问题都属于合理利用有限资源的调度问题，只是外在形式不同。 作为一类特殊的调度问题，生产调度是一类在交货期、工艺路线、资源情况约束等 条件下，对各工件的具体操作( 使用哪些资源、开始加工时间、不同操作问加工的先后 顺序等) 进行安排，以使得某些性能指标最优，如最大完工时间最短，制造成本最低等 的问题。调度问题( s c h e d u l i n gp r o b l e m ) 属于n ph a r d 问题，其求解有相当的难度。生 产调度问题也可以看成是一个排序问题，在已知生产任务的边界条件下( 即生产区间) ， 如果生产任务的加工顺序确定了，那么生产任务的开始时间也就确定了。 装配车间生产调度作为企业生产调度的其中一个重要环节，是企业顺利生产、提高 企业经济效益的重要条件和保障。依据实际情况，航空发动机因为用途特殊，质量要求 甚高，在航空发动机总装配车间中增加了试车车间，主要用于发动机性能测试，确保产 品质量。试车成本昂贵，其中试车台是关键所在，它直接影响生产效率和生产成本。目 前，现场主要是根据调度人员的经验进行调度排序，当发动机品种和批量增加时，只靠 经验调度难以保证最优调度。因此针对试车台调度问题的研究成了影响装配车间整体效 益的关键所在，成为解决装配车间调度问题的又一新的研究方向。 目前有关解决类似试车台优化排序的装配排序问题的方法很多，其中广泛应用的如 遗传算法【6 】，模拟退火算法【7 】等智能算法1 8 j 。为了实现装配排序问题的最优求解，改进 和设计更多求解算法必将成为一个重要研究课题。 2 2 装配车间试车台排序优化模型 2 2 1 问题概述 依据航空发动机总装车间实际情况，试车台是发动机装配过程中的关键所在，它直 接影响生产效率和生产成本。只靠调度人员的经验调度排序，无法达到最优调度。因此， 本文在分析了试车台排序特征的基础上，建立了试车台最优排序的旅行商问题( t s p ) 模型。旅行商问题模型【91 0 1 已经被应用于解决排序优化问题，并取得了很好的效果。本 文深入分析试车台排序实际特征，对试车台排序物理模型进行抽象和改进，通过引入一 个虚节点，把试车台排序问题转化成t s p 问题，并建立了适合实际问题的t s p 模型。 目前有关解决装配排序问题的方法很多l l 2 j ，其中遗传算法应用非常广泛，但是遗 传算法1 1 3 1 4 】( g e n e t i ca l g o r i t h m 。g a ) 解决诸如装配排序的组合优化问题时存在收敛性能 差，容易陷入局部最优等缺陷。近年来，国内外学者开始研究用分散搜索算法i l 6 l ( s c a t t e r s e a r c h i n ga l g o r i t h m ，s s ) 解决组合优化问题，由于s s 算法保持搜索在大范围内进行，增 强了g a 算法跳出局部最优的能力，改进了g a 算法收敛性能差、需要时间长的不足， 取得了很好的效果。因此本文采用基于g a & s s 混合算法( 称为遗传分散搜索算法) 对 该模型进行求解，为装配排序优化问题提供了一种科学的新方法。 4 第二章装配车间试车台排序优化方案研究 2 2 2 试车台排序优化模型 2 2 2 1 试车台排序问题的提出 航空发动机装配车间生产调度包括部件组装和试车两部分，实际情况中，试车直接 影响生产效率和生产成本。因此本文先对试车台进行排序优化，以为部件组装调度优化 提供基础。 1 试车台排序的特征 ( 1 ) 需要试车的发动机种类多。 ( 2 ) 不同种类的发动机之间转产需要重新调整试车台，而不同种类的发动机所需 的调整时间不同。 2 试车台排序处理策略 ( 1 ) 试车台排序问题可以简化为调整时间与加工顺序有关的单品种调度问题。 ( 2 ) 单一品种发动机试车时，可以把每一批同品种的发动机看成一个工件，简化 排序复杂度。 2 2 2 2 试车台排序的数学模型 1 目标函数的选取 对于这种排序问题，一批发动机经过试车台试车的最大完工时间不再是常数，它与 试车顺序有关，以“0 表示一定的试车顺序，如夏。) 表示第一位试车的发动机的完工时 间。假设发动机到达时间为0 ，各发动机的完工时间表示为【1 0 】： 夏1 ) = w ( o ) ( 1 ) + 职1 ) 夏2 ) = 夏1 ) + w ( 1 x 2 ) + 职2 ) 夏f ) = 夏“) + w ( h ) + 7 玖f ) 夏。) = 夏。一1 ) + 。一1 ) ( 。) + 职。) 其中心o ) ( ，) 表示机器从闲置状态到第一台发动机被试车所需的调整时间，m 。- d ( o 表示 从测试第a 一1 ) 种发动机到测试第f 种发动机所需的调整时间，杈，) 为每种发动机被测试 的时间，夏。为第i 种发动机的完工时间，这样最大完工时间为： 瓦。= 五。) = 夏。1 ) + w ( 。一1 ) ( 。) + 7 玖。) 。w ( o ) ( 1 ) + 职1 ) + w ( 1 ) ( 2 ) + 职2 ) + w ( 。一1 ) ( 。) + 职。) 2 圣w ( 州i ) + 萎 i l ll - l 5 东南大学硕士学位论文 上式中兰啊n 为刀种发动机被测试的时间之和，是常量，与发动机的试车顺序无关。 i = 1 因此要使最大完工时间最短，只需要芝w ( ) 最小。对于连续测试玎种发动机的情形， j - i 可以假设第一种发动机无需调整试车台而直接被测试，即w ( 唧) 忽略不计，这样就可以 将试车台问题转化为t s p 问题。”种发动机对应，1 个城市，不同种类发动机试车时所需 要的调整时间对应城市间的旅行时间。 2 试车台排序的t s p 模型 旅行商问题是一个闭合回路问题，而实际发动机试车台问题是一个开环问题，每个 发动机只被试车一次，因此需要引入一个虚节点，从虚节点出发，然后再回到虚节点， 这样就成功的把开环的实际问题转换成了闭环的t s p 问题【1 0 1 。 m i n 萎x ，t , ( 2 1 ) ；lj i n + i s t ：置，= l ( = 1 ，2 甩+ 1 ) ( 2 2 ) n + l 五。j = l ( 扛1 2 埘+ 1 ) j = l 乙+ 1 = o ( i 1 ，2 埘) ) ( 2 3 ) ( 2 4 ) 0 一+ l = o ( ， l 2 以 ) ( 2 5 ) 其中玎表示发动机的种类数； 表示从f 种发动机转产到第j f 种的调整时间； 式2 2 、2 3 用于约束每次正在被试车和可直接转产的发动机只有一种；式2 4 、2 5 表示在实际问题中引入的虚节点应满足的条件，以将实际问题转化为t s p 问题。 2 2 3 试车台排序优化算法设计 2 2 3 1 遗传算法( g a ) 的基本原理 遗传算法【6 】是h o l l a n d 教授于1 9 6 9 年提出，后经d e j o n g 等人归纳总结所形成的一 类模拟进化算法。遗传算法的基本原理是模拟自然界遗传机制和生物进化论而形成的一 种过程搜索最优解的算法。具体体现在遗传算法中初始种群的设定，初始种群内的个体 之间交叉，变异，新个体的产生及种群的更新。种群在适应度函数的约束下不断进化最 终得到最优或者次最优的个体。遗传算法最基本的要素为染色体编码，适应度函数，选 择操作，交叉操作和变异操作。 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，由于遗传算法在计 算时不依赖其他辅助信息，只需要目标函数和相应的适应度函数，因此被广泛应用。其 中最主要的应用领域是函数优化和组合优化，可以方便的得到较好的结果。此外，遗传 算法也在生产调度问题、机器人学、图像处理、人工生命等方面获得了广泛应用。 6 第二章装配车间试车台排序优化方案研究 2 2 3 2 分散搜索( s s ) 的基本原理 分散搜索是在禁忌搜索的基础上，最早由g l o v e 于1 9 7 7 年在一篇文章中提出的。 分散搜索的基本原理是首先产生一个初始种群，通过统一的规则组合一个参考解集，再 按照一定选择规则从参考集中分别选出质量好的解组成子参考集1 和多样性好的解组成 子参考集2 。将两个子参考集中的解通过组合机制产生新解，再对这些新解进行改进， 然后把这些符合条件的新解加入参考集。进行新的搜索，最终获得最优或者次最优的个 体【17 1 。 分散搜索是一种启发性质的算法，在这个算法中主要有解的组合方法，多样性产生 方法，解的改进方法，子参考集的更新方法，子参考集的产生方法【l 引。 s s 算法参考集中解的数目相对较少( 一般选择2 0 个) ，用系统方法选择解进行组 合产生新解。因此，s s 算法既考虑了解的质量，又考虑了解的分散性。 s s 算法是确定的、有记忆功能的具有智能性质的算法，用于解决一些问题非常有 效。另外借助于s s 算法的上述特征，以不同方式和途径将它跟其它算法结合可以产生 许多混合算法，能更有效的解决各种实际问题。 2 2 3 3g a & s s 混合算法 鉴于上述遗传算法( g a ) 和分散搜索算法( s s ) 基本原理的介绍，可以发现分散 搜索算法具有遗传算法没有的特征，遗传算法是基于概率的算法，而分散搜索算法是确 定的、有记忆功能的具有智能性质的算法，这些特征正好弥补了遗传算法的不足。因此 本文考虑将两者结合，实现遗传分散搜索混合算法( g a & s s ) 。 s s 算法主要由初始解的生成，参考集合的生成，组合产生新解，解的改进以及子 参考集的更新5 部分组成。g a & s s 算法主要是将g a 算法嵌套到s s 算法框架中，由于 s s 算法保持搜索在大范围内进行，增强了g a 算法跳出局部最优的能力，改进了g a 算 法收敛性能差、需要时间长的不足。为方便表达，给出下面定义： 定义l参考集尺是一些可行解集合，按照一定选择规则从参考集尺中选择b 1 个质 量好的解组成子参考集吊，选择6 2 个分散性好的解组成子参考集尼。 定义2h u m 代表两个解的相同边数目，表示这两个解的分散性。h u m 值越小，这 两个解的分散性越好。 分散搜索算法每部分可以根据具体情况做出灵活的设计，本文的创新部分就是在子 参考集组合产生新解和解的改进以及子参考集更新部分。 本文在通过组合机制产生新解时，选择运用g a 算法：在参考集的两个子参考集中 各选一条染色体作为父本，通过交叉，变异，产生新的染色体( 即新解) 并对新解进行 改进。实现了g a & s s 混合算法，并且获得了很好的效果。 g a & s s 算法步骤： s t e p l ：产生初始种群，初始化参数，生成初始解集合p 对p 中的解进行改进，由 改进后的解组成参考集尼。 s t e p 2 ：按照一定选择规则从参考集厅中选择b 1 个较好的解组成子参考集扁，选择 b 2 个较分散的解组成子参考集恁，且尺= b l + b 2 ( 一般为了效果更好，选择b l = b 2 ) 。保留 当前参考集中最优函数值c u r r e n tb e s t 和最优解sb e s t 。 s t e p 3 ：调用遗传算法对两个子参考集中的染色体按一定交叉概率和变异概率进行交 叉，变异，生成新的染色体。 s t e p 4 ：计算目标函数值，如果f ( s ，) f ( sb e s t ) ，则更新当前最优函数值 7 东南大学硕士学位论文 c u r r e n t b e s t = f ( s j ) 、更新当前最优解s b e s t = 夥；否则转s t e p 5 。 s t e p 5 ：分别计算s j 与参考集中各解之间的h u m ，取其中最大值甩姗h a 】( ( 勺) ，当 f ( s j ) m a x f ( s , ) 时， 用s ，更新子参考集冠中的解毛； 如果 刀材，a ) 【( 0 ) p k ( 3 3 ) 其中式3 2 表示每个工件包含的工序依照一定的顺序加工，只有前道工序完工，才 能开始后道工序； 式3 3 表示每台机器上只能同时加工一个工件，只有当一个工件加工完毕，才能开 始加工其它工件，其中工序( 1 ，五) ，( i s ，五) 为同一机器上进行加工的工序，且( 之五) 在 ( ，石) 前面加工。 3 2 3 算法设计 3 2 3 1 遗传算法( g a ) 的基本原理 遗传算法【6 】是h o l l a n d 教授于1 9 6 9 年提出，后经d e j o n g 等人归纳总结所形成的一 类模拟进化算法。遗传算法的基本原理是模拟自然界遗传机制和生物进化论而形成的一 种过程搜索最优解的算法。具体体现在遗传算法中初始种群的设定，初始种群内的个体 之间交叉，变异，新个体的产生及种群的更新。种群在适应度函数的约束下不断进化最 终得到最优或者次最优的个体。遗传算法最基本的要素为染色体编码，适应度函数，选 择操作，交叉操作和变异操作。 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，由于遗传算法在计 算时不依赖其他辅助信息，只需要目标函数和相应的适应度函数，因此被广泛应用。其 中最主要的应用领域是函数优化和组合优化，可以方便的得到较好的结果。此外，遗传 算法也在生产调度问题、机器人学、图像处理、人工生命等方面获得了广泛应用。 3 2 3 2 改进遗传算法 改进遗传算法【2 5 】是在传统遗传算法中引入最优个体保留机制即将当前种群中适应 度函数值最优的个体直接放入下一代种群中。该算法保证各代种群中总会有目前为止最 好的解，防止最优解的遗失，某种程度上也加快了算法的收敛速度。 改进遗传算法步骤： 遗传算法的主要步骤是初始化种群、依据适应度函数计算适应值、选择、交叉、变 异等。 s t e p l ：产生初始种群，初始化参数，利用约束条件检验初始解的有效性，生成有效 的初始解集合成 s t e p 2 ：利用适应度函数计算各个初始解的适应度值厂( 墨) ，采用轮盘赌选择机制选 1 4 第三章装配车间部件组装调度问题的方案研究 择算子，并将适应度值最优的个体sb e s t 直接放入子代种群中，实现最优个体保留机制。 s t e p 3 ：调用遗传算法对选择出的染色体按一定交叉概率和变异概率进行交叉，变异， 生成