（机械电子工程专业论文）基于遗传算法的模糊车间作业调度问题的研究.pdf

大连理工大学硕士学位论文 摘要 随着全球经济一体化和知识经济的到来，企业间的竞争愈演愈烈。为了增强核心竞 争力，企业必须要改善内部生产管理，尤其是生产管理的核心技术一生产调度技术。生 产调度是企业充分利用资源、制定合理的生产计划、保证按时交货、降低制造成本、提 高设备利用率的关键。而在此领域，车间作业调度问题又是最普遍、最复杂和最具难度 的，并且由于其具有可推广性和可移植性，引起了学术界和工业界的广泛关注。然而以 往人们多将目光投在确定性车间作业调度问题上，但现实生产中，受多种随机因素的影 响，加工时间和交货期往往都是模糊的，所以，本文在现有理论的基础上，较深入地研 究了模糊车间作业调度问题。 本文首先分析了制造业环境的变化，阐明了生产调度技术的重要性，回顾了其研究 历程和研究方法。进而给出了车间作业调度问题的定义，分析了其特点，讨论了计算此 问题的复杂性，对其建立了数学模型，重点探讨了几种目前看来最有效的邻域搜索算法。 然后，比较分析了多种编码方式、遗传操作的优劣，设计了一种适用于车间作业调度问 题的动态自适应遗传算法。此算法融入了保优策略和反复交叉变异策略，并且可以自适 应调整交叉概率和变异概率。进而，又采用模糊数来表示工序加工时间和交货期，定义 了客户满意度来表示产品完成时间令客户满意的程度，利用模糊数的运算、评价准则和 所设计的遗传算法，定义并研究了多目标模糊车间作业调度问题。 在算法应用方面，首先用典型车间作业调度问题的几个算例验证了算法的有效性和 可行性，再将其用于模糊车间作业调度问题。计算机仿真结果表明，此算法能够较快地 得到最优解，避免传统遗传算法中“早熟收敛”现象的产生；且所得模糊车间作业调度 的研究结果对于车间的实际生产具有一定的指导意义。最后，对全文进行了总结共对模 糊车间作业调度问题未来的研究做出了展望。 关键词：自适应遗传算法；生产调度；模糊车间作业调度；反复交叉变异 大连理工大学硕士学位论文 r e s e a r c ho nf u z z yj o b - - s h o ps c h e d u l i n gp r o b l e mb a s e d - o ng a a b s t r a c t w i t ht h ec o m i n gf o r t ho ft h e 酉o b a le c o n o m yi n t e g r a t i o na n dk n o w l e d g ee c o n o m y , t h e c o m p e t i t i o nb e t w e e ne n t e r p r i s e sw i l lb em o r ed r a s t i c 。i no r d e rt oi n c r e a s et h e i rc o r ec a p a c i t y o fc o m p e t i t i o n ，e n t e r p r i s e sm u s ti m p r o v et h e i ri n n e rp r o d u c t i o nm a n a g e m e n t ，e s p e c i a l l yt h e c o r eo fp r o d u c t i o nm a n a g e m e n t - p r o d u c t i o ns c h e d u l i n g i ti st h ek e yp r o b l e mt om a k et h ef u l l u s eo f r e s o u r c e s ，w o r ko u tt h er a t i o n a lp r o d u c t i o np l a n ，e n s u r et h ed e l i v e r y j u s ti nt i m e ，l o w e r t h ec o s to fp r o d u c t i o na n dh e i g h t e nt h ee f f i c i e n c yo fu t i l i z i n gt h ep r o d u c t i o ne q u i p m e n t s i n t h ed o m a i no fp r o d u c t i o ns c h e d u l i n g ，j o b s h o ps c h e d u l i n gp r o b l e mi st h em o s tp r e v a l e n t ， c o m p l i c a t e da n dd i f f i c u l tp r o b l e m f u r t h e r m o r e ，b e c a u s e i tc a nb ep o p u l a r i z e da n d t r a n s p l a n t e d ，i th a sb e e np a i dc l o s ea t t e n t i o nt ob yb o t ha c a d e m i aa n di n d u s t r y n e v e r t h e l e s s ， s c h o l a r so f t e nf o c u so nc e r t a i nj o b s h o ps c h e d n l i n gp r o b l e mi nt h ep a s t ，b u tb e c a u s ei ti s a f f e c t e db ym a n yu n c e r t a i nf a c t o r si nr e a l i t y , t h i sd i s s e r t a t i o nr e s e a r c h e sa b o u tf u z z y j o b s h o p s c h e d u l i n gp r o b l e mi nd e p t hb a s e d - o ne x i s t i n gt h e o r i e s i nt h i sd i s s e r t a t i o n ，t h ec u r r e n tc h a n g i n gt r e n do fc i r c u m s t a n c ei nm a n u f a c t u r i n gi s a n a l y z e df i r s t l y s e v e r a la d v a n c e dm a n u f a c t u r i n gi d e a sa r ei n t r o d u c e ds i m p l y t h er e s e a r c h c o u r s ea n dm e t h o d sa r er e v i e w e d f u r t h e r m o r e ，t h ed e f i n i t i o no f j o b s h o ps c h e d u l i n gp r o b l e m i sg i v e n i t sc h a r a c t e r i s t i c sa r ea n a l y z e d t 1 1 cc o m p l e x i t yo fc o m p u t i n gi ti sd i s c u s s e d ，t h e m a t h e m a t i c sm o d e la b o u ti ti sc o n s t r u c t e d a n ds e v e r a li m p o r t a n tn e i g h b o r - r e g i o ns e a r c h i n g a l g o r i t h m sw h i c ha r et h em o s te f f e c t i v ei n t e l l i g e n tm e t h o d su n t i ln o wa r ed i s c u s s e d t h e a d v a n t a g e sa n dd i s a d v a n t a g e so fd i f f e r e n tc o d i n g ，g e n e t i co p e r a t i o n sa r ec o m p a r e da n d a n a l y z e d t h e nt h ed y n a m i ca d a p t i v eg a i sd e s i g n e dt o w a r d ss o l v i n gj o b s h o ps c h e d u l i n g p r o b l e m t h es t r a t e g yo f “h o l db e s tr e s u l t ”a n d “r e p e a t e dc r o s s o v e ra n dm u t a t i o n a r eu n i t e d i n t og aa n dt h ep o s s i b i l i t yo f c r o s s o v e ra n dm u t a t i o nc a nb ea d j u s t e da u t o m a t i c a l l ya c c o r d i n g t ot h er e s u l t so fo p t i m i z a t i o n t h ep r o c e s s i n gt i m eo fo p e r a t i o na n dd u e d a t ea r er e p r e s e n t e d b yf u z z yn u m b e r sa n dt h es a t i s f a c t i o nd e g r e eo fc u s t o m e r si sp r e s e n t e df o rs h o w i n gt h e d e g r e et h a tt h ec o m p l e t i o nt i m ei ss a t i s 划n gw i 血c u s t o m e r s t h e nu s i n gt h eo p e r a t i o n sa n d e v a l u a t i o nc r i t e r i o n so ff u z z yn u m b e r s ，m u l t i o b j e c t i v ef u z z yj o b s h o ps c h e d u l i n gp r o b l e mi s d e f i n e da n ds t u d i e d t h ed e s i g n e dg ai su s e da sam e t h o df o rs o l v i n gf u z z yj o b s h o pp r o b l e ma f t e ri ti s v a l i d a t e dt h a ti ti sav e r ya p p l i c a b l ea n de f f e c t i v em e t h o db yb e n c h m a r kp r o b l e m s t h er e s u l t s o fs i m u l a t i o ne x p e r i m e n t si n d i c a t et h a tt h i sg ac a ng a i nt h eb e s to p t i m i z a t i o nr e s u l t sq u i c k l y a n da v o i dt h ep r o b l e mo f “i m m a t u r ec o n v e r g e n c e ”e x i s t i n gi nt h et r a d i t i o n a lg a t h er e s u l t s t o w a r d sm u l t i o b j e c t i v ef u z z yj o b s h o ps c h e d u l i n gp r o b l e ma r eb e n e f i c i a lf o rt h er e a l i s t i c p r o d u c t i o ni nw o r k s h o p i nt h ee n d ，t h ew h o l ed i s s e r t a t i o n i ss u m m a r i z e da n df u r t h e r 陈东升：基于遗传算法的模糊车间作业调度问题的研究 d e v e l o p m e n t s0 1 2 f u z z y j o b s h o ps c h e d u l i n gp r o b l e ma r ee x p l o r e d k e yw o r d s ：a d a p t i v eg a ；p r o d u c t i o ns c h e d u l i n g ：f u z z yj o b s h o ps c h e d u l i n g ； r e p e a t e dc r o s s o v e ra n d m u t a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名； 醯：五：翌日期：逸丝；! 至8 三妒 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 豳：矗：盐 塑 磁( 年王月盟日 大连理工大学硕士学位论文 1 绪论 1 1 制造业的变革 随着新世纪的到来，人类社会正朝着信息化社会的方向大踏步地前进，但物质经济 仍然作为社会经济的主体的地位却稳如泰山，岿然不动。制造业作为国民经济发展的基 础产业，在目前愈演愈烈的国际竞争中也扮演着不可或缺的重要角色，遭遇了前所未有 的挑战，为了适应当前的社会需要，其自身也发生了巨大的变革，具体如下： 1 ) 客户、市场方面：市场日益全球化，客户对产品的个性化要求更高。企业的客 户和制造工厂遍布全球，这带来了市场需求的多样化，产品开发和生产的分散化。使得 大批量少品种转变为小批量、多品种并且直接面向客户。变化如图1 1 【1 。 1 9 6 0 1 9 7 01 ，b o1 9 9 0 2 0 0 0 图1 ，1 市场需求变化图 f i g 1 1c h 姆u go f m a r k e td e m a n d 2 ) 生产技术方面：柔性设计、制造技术的发展( c a d c a p p c a m 技术) 提高了产 品质量，降低了生产成本，同时使得生产周期缩短，产品转型快，设备利用率高。 3 ) 信息技术方面：如今，信息时代和网络时代已经到来，信息技术使得大规模的、 实时的、跨时空的信息交换成为可能，从而诞生了很多新的生产理念和制造模式。 1 2 先进制造模式概述 由于制造业环境所发生的变革，一些适应时代需要的先进制造模式也应运而生，主 要包括敏捷制造，精益生产，计算机集成制造和智能制造等，下面分别加以简要介绍。 1 ) 敏捷制趔2 4 】 敏捷制造是将柔性生产技术、熟练掌握生产技能的雇员与促进企业内部和企业间相 互合作的灵活管理集一身的全新制造模式，以最大程度满足客户对产品个性化和快速上 市的要求为目标，能够使企业在复杂激烈的竞争环境下快速成长进步、并能对客户及市 场需求做出迅速反应。 陈东升：基于遗传算法的模糊车间作业调度问题的研究 对于企业敏捷性的评价，目前较为通用的评价指标有以下四个：成本c 、时 n t 、鲁 棒性r 、自适应性s 。这些指标衡量了企业从一个平衡点转移到另一个平衡点的消耗和结 果，是一套动态指标，比较直观地反映了企业的敏捷性。另外，敏捷制造强调组织虚拟 企业。在虚拟企业中，为了抓住稍纵即逝的市场机遇，企业致力于自身核心能力的建设， 并依靠与其他企业建立动态的协作关系来发展和壮大自己。在这种商务活动中，企业的 边界和能力可以在保证客户满意度并且付出较小代价的前提下灵活地伸缩。 2 ) 精益生产2 + 4 精益生产是美国麻省理工学院( m i t ) 在调查分析了日本、美国和欧洲汽车制造业的差 距后，于1 9 9 0 年在“国际汽车计划( r m w ) 研究报告”中归纳出的一种适用于现代制造企 业的组织管理方法，它主张消除生产过程中一切不产生附加值的活动和投资，以整体化 观点将企业中各种功能合理地加以组合，使企业具有更好的应变能力，取得更大的效益。 精益生产强调以“人”为中心，以“简化”为手段，以“尽善尽美”为最终目标，逐步 地、不停顿地建立和实现更高的标准。其成功的关键包括全面质量管理、及时库存、工 作小组、过程系统改进、供应商关系、柔性制造、自动化等。 3 ) 计算机集成制造 2 5 美国人m e 麦切恩特( m e m e r c h a n t ) 于1 9 6 9 年提出了计算机集成制造的概念。1 9 7 4 年美国人约瑟夫，哈林顿( j o s e p h h a r r i n g t o n ) 出版了计算机集成制造一书，进一步发展 了c i m 思想，指出企业生产的各个环节，从市场分析、产品设计、加工制造、经营管理 到售后服务等全部生产活动，是一个紧密联系、统一考虑的整体，其核心是集成，这种 集成不仅仅是物流和设备的集成，更重要的是信息的集成，整个生产过程就是一个信息 采集、传递和加工处理的过程，产品是信息的物质表现，计算机是集成的工具。 我国8 6 3 计划c i m s 主题组将c i m s 定义为：c i m s 是通过计算机软硬件，并综合运用 现代管理技术、制造技术、信息技术、自动化技术、系统工程技术，将企业生产过程中 有关的人、技术、经营管理三要素及其信息与物流有机集成并优化运行的复杂的大系统。 4 ) 智能制造4 1 智能制造系统是以日本在1 9 9 1 年首先提出的智能制造系统国际合作研究开发计划为 契机发展起来的。它是一种由智能机器和人类专家共同组成的人机一体化系统，在制造 过程中能进行诸如分析、推理、判断、构思、决策等智能活动，并且强调制造过程中的 自组织能力。智能制造技术的宗旨在于通过人与智能机器的协作，扩大、延伸和部分取 代了人类专家在制造过程中的脑力劳动，实现制造过程的优化。智能制造对于提高产品 质量、降低成本、提高生产效率有重要意义。 5 ) 虚拟制造p o 虚拟制造采用计算机仿真与虚拟现实技术，在计算机上群组协同工作，实现产品设 大连理工大学硕士学位论文 计、工艺规划、加工制造、性能分析、质量检验以及企业各级过程的管理与控制等产品 制造过程，以增强制造过程各级的决策与控制能力，其应用过程是用数字形式“虚拟”地 制造产品，即在计算机上建立产品数字模型，并在计算机上对该产品的形式、配合和功 能进行评审、自发修改、往往只需制作一次最终的实物原型，免除了以往原型机漫长的 试验、评审过程，并可使新产品开发一次性获得成功。 1 3 生产调度问题的提出及概述 随着人类社会生产力水平的不断提高，人类的生产等社会活动对资源的需求量急剧 上升，资源的有限性问题逐渐摆在了人们面前，对资源的合理配置与优化利用已变成了 一个非常棘手的问题，同时也是一项具有挑战性的难题 ”。这个问题贯穿于社会生活的 方方面面，从一个国家的宏观经济活动到企业的微观经济活动，无不受到资源条件的制 约。所以，人们就从不同的领域，不同的行业开展了对它的研究，其中，在制造业的生 产领域产生了一个非常重要的理论，也就是生产调度理论。 制造业是国民经济的支柱产业，没有发达的制造业，就没有国家的真正繁荣和强大。 制造技术是完成制造活动所需的一切技术手段的总称，是支持高质量制造业的技术后 盾。其中，生产调度技术又是最重要的制造技术之一，在制造企业中有着举足轻重的地 位口】。尤其在制造业发生了翻天覆地变化的今天，显得格外重要。一方面，随着电子技 术、计算机技术的发展，制造设备的自动化水平和加工能力得到了极大的提高，制造过 程自动化水平也逐渐提高，使得生产调度问题变得更加复杂，往往超过人的正常决策能 力。另一方面，随着市场竞争的激烈化和国际化，出现了前文所述的多种先进理念及制 造模式，它们的核心思想无一不是为了适应市场小批量、多品种和更具个性化的要求， 缩短供货周期，控制产品成本，提高产品质量，提高设备利用率等。所以，传统的依赖 人来指挥生产加工过程的模式已经远远不能适应新的制造环境的需要，迫切需要研究有 效的生产调度方法和建立生产调度软件系统，使得生产过程能够更加合理和高效运行。 生产调度的理论和方法属于软科学，运用它既不需要增加投资和设备，又不需要增加人 员，就可以提高生产和工作效率。因此，研究生产调度的理论和方法，对于力求建设“节 约型”社会的今天，提高工作效率和经济效益，有着重要的现实意义。 生产调度就是解决如何按时间的先后分配资源来完成不同的生产任务，使预定目标 最优化的问题 8 l 。追本溯源，它来源于对制造车间生产计划与控制的研究，但是又不能 将它与生产计划混淆。工程应用体系中，经常从时间周期角度定义长期规划、中期计划 和短期计划【9 】，调度则仅限于在生产故障或出现异常情况下的动态调度和再调度问题。 但这种体系仅针对特殊情况，不具有广泛意义。还有一种体系是将调度的概念泛化f 1 叱“】， 将整个车i n 的生产指挥范畴的活动均称为调度问题，并将其分解成几个层次进行研究， 陈东升：基于遗传算法的模糊车间作业调度问题的研究 涉及计划和调度等一系列活动。然而，本文为了问题阐述和研究的方便，摒弃上述两种 概念体系，将工艺计划归入计划问题，将调度问题明确为针对加工活动的排序和加工时 间的确定问题。另外，需要说明的是，生产调度与人们常说的排序并非同义。排序只是 确定不同工作任务共享有限资源的顺序，生产调度则不仅包括确定任务的处理顺序，而 且还包括确定每个资源处理每个任务的开工时间和完工时间。对于同一排序结果，由于 有“任务等待”和“资源闲置”两种情况的存在，可以对应多个生产调度，而一种生产调度 只对应唯一的一种排序。 总而言之，生产调度理论从诞生至今，经过几十年的研究与探索，已逐渐发展成为 一个比较完整的科学理论，在企业的生产中得到了相当程度的应用，而且其研究成果的 应用也已经从制造业的车间扩展到了物资、能源、交通运输和社会服务等诸多行业。生 产调度理论是目前国际上发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领 域之一 1 2 】。 1 4 生产调度方法研究进展 截至目前，研究调度问题的基础理论仍然是经典调度理论，s m 1 0 h n s o n 1 3 】于1 9 5 4 年对h 2 f c o 和部分特殊的n 1 3 1 f c 。问题的求解是经典调度理论诞生的重要标 志。直至五十年代末期的研究成果主要是提出了针对一些特殊情况和规模较小的单机和 简单的流水车间问题的解析优化方法，研究范围较窄，但是这些研究却成为经典调度理 论的基石。 六十年代，多是利用混合或纯整数规划、动态规划和分枝定界法解决些有代表性 的问题。如s t o r y 的研究【1 4 ，同时也有人开始尝试用启发式算法研究此问题，如g a v e t t 提出的方法( 1 卯。六十年代末期，经典调度理论体系初步形成。 七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属于n p 一完全问题 或n p 一难问题，难以找到多项式算法，因此开始关注启发式算法。p a n w a l k a r 总结和归纳 出了1 1 3 条调度规则，并对其进行了分类【1 “。七十年代末期，经典调度理论趋向成熟。 八十年代初期，s t e p h e n 等【 l 从三个方面对调度进行了重新考察，对未来发展做了 分析和预测，认为理论与实际的结合将会成为研究热点。这个富有挑战性的课题吸引了 机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应用到研究中。其中最引 人注目的就是以c a m e g i e m e l l o n 大学的mf o x 1 8 】为代表的学者们开展的基于约束传播的 i s i s 研究，它标志了人工智能开始真正应用于调度问题。八十年代后期，r o d a m m e r 等人 【旧】总结了生产调度的理论和实践方面的最新研究进展，从七个方面论述了生产调度的技 术和方法，认为生产调度无论在理论还是实践上都已突破了传统界限。 九十年代至今，各种方法在生产调度问题的研究中得到了充分的发挥，同时新的研 大连理工大学硕士学位论文 究手段层出不穷。智能调度已成为调度研究的主流。 纵观目前国内外的研究成果，从总体趋势上来讲，经典调度理论依然是调度理论不 可动摇的基石，但智能调度理论已崭露头角，逐渐趋于成熟，不妨做出大胆的预测，不 久的将来，智能调度理论必将取代传统调度理论，n - - 者的融合也将会成为一种趋势。 14 1 经典调度理论 1 ) 调度规则 调度规则是最传统的研究方法，一直受到学者们的广泛研究。p a n w a l k a r 等人 m 】总 结了1 1 3 条规则，并将它们按形式分为了三类：简单规则、复合规则、启发式规则。对于 启发式规则的研究尤为热烈，它最早是由g i f l l e r 和t h o m p s o n 19 提出来的，其基本思想 是预先指定一个启发式规则，按此规则，从待调度工序集合中选择优先级最高的工序， 为之分配机器，直到待调度工序集为空为止。比较常用的启发式调度规则有： ( 1 ) s p t l p t ( s h o r t e s t l o n g e s t p r o c e s s i n g t i m e ) ：选择加工时间最短最长的工序。 ( 2 ) m w g 几w r ( m o s t l e a s t w o r kr e m a i n i n g ) ：选择总剩余加工时间最长最短的工件。 ( 3 ) m o r l o r ( m o s t l e a s to p e r a t i o nr e m a i n i n g ) ：选择总剩余工序数最多最少的工件。 ( 4 ) e d d ( e a r l i e s td u ed a o ：选择交货期最早的工件。 ( 5 ) f c f s ( f i r s tc o m e f i r s ts e r v e d ) ：选择同台机器上工序队列中最先的工序。 ( 6 ) r a n d o m ( r a n d o m ) ：随机选择。 总的说来，调度规则，尤其是启发式调度规则比较直观、简单、符合人们思维习惯、 易于实现。但是实验结果表明它不具备一般性、推广性。因此，单纯地使用此方法来调 度已渐渐失去了光芒，不能适应如今的环境。 2 ) 多项式算法 这种方法以特定的调度问题为研究对象，能够在多项式时间内求得问题的最优解， 即所求的最优解的时间可以用调度问题变量( 机器和工件数) 的多项式函数来度量。尽管 此类方法对某些大规模的调度问题仍然有效，但它们只是针对某些特定的领域 1 。到目 前为止，只有少数的问题找到了有效的最优化方法，主要有单机和简单的并行多机问题。 3 ) 解析法 它包括数学规划和随机优化。在数学规化方法中，研究较多的是分枝定界法、割平 面法、动态规划及拉格朗日法：在随机优化领域中，则是应用排队论，贮存论、批量技 术和可靠性理论。然而，由于大部分的生产调度问题属于n p 完全问题，对其求解会导致 组合爆炸。对于规模稍大的问题，这种纯数学方法有模型抽取困难、运算量大、算法难 以实现的弱点。 综上可知，经典调度理论经过近2 0 多年的发展，取得了一些重要的成果，形成了一 陈东升：基于遗传算法的模糊车间作业调度问题的研究 门基本成熟的应用数学学科。单纯在算法研究上来讲，已比较成熟，但是多年来在生产 实际中的应用还是暴露出一些不足，存在很多局限性，主要体现在以下几个方面： ( 1 ) 模型较简单 经典调度理论在数学上日臻成熟，但欠缺对整个生产系统定性和定量的分析，对实 际的生产环境大量的简化，脱离了生产实际，因此其结果难以适应复杂的生产环境。 ( 2 ) 方法较单一 生产调度系统是一个复杂的大系统，而对大系统必须在不同层次用不同的方法和模 型进行研究。经典调度理论总试图用一般系统的研究方法来解析大系统，结果可想而知。 ( 3 ) 适用范围较狭窄 经典调度理论中的每个算法，基本上都只针对某种具体环境，而一旦环境发生变化， 这种算法即不再适用。 ( 4 ) 运算效率较低下 由于经典调度理论中的算法均属于确定性方法，采用单点串行运算，所以其求解所 需时间会随着问题规模的扩大而呈指数上涨，即所谓的指数时间算法，运算效率低下。 1 4 2 智能调度理论 智能化的生产调度方法属于“智能自动化”【2 0 1 范畴，是智能自动化概念、理论和方法 在生产调度领域中的应用。智能化的生产调度方法是基于“智能自动化”的“广义模型”和 “广义优化”原理，应用人工智能、计算智能技术，通过提高调度方法的智能程度，解决 各类生产调度问题方法的总称。按照智能调度的推理控制策略特征，可以将智能化的生 产调度方法分为【2 1 ：约束指导的搜索、模式匹配驱动的调度( p d s - - p a t t e r n d i r e c t e d s c h e d u l e r ) 和基于智能技术的邻域搜索方法。 1 ) 约束指导下的智能搜索 约束指导下的智能搜索是通过对生产约束的合理表达，利用生产约束条件，智能地 生成、过滤、定量评价各搜索状态，从而实现对搜索过程的指导。m f o x 等人最早在解 决车间作业调度问题时提出这种思想，并构建了著名的智能调度信息系统( i s i s ) 。在此 基础上，s t e p h e ns m i t h 2 2 】等人将调度和再调度的“机会”选择概念引入i s i s o o ，开发了机 会型智能调度系统( o p t s ) 。1 9 8 6 年美国国家航空航天局( n a s a ) 的a m e s 智能研究部在解 决宇航系统的调度问题时，认识到了递归修复调度方法的实际意义。z w e b e n 2 3 】等人提 出了通过增加极小化原始调度扰动的约束条件，将i s i s 思想应用于基于修复的搜索过程。 h e n t e n r y e k1 2 4 提出了基于约束的编程语言，简化了系统的构建，使它得到了广泛的应用。 2 ) 模式匹配驱动的调度 模式匹配驱动的调度系统将调度系统看作是一个模式驱动的决策过程。首先抽取调 度系统的特征模式，以刻画系统所处的状态，然后，确定系统调度可以采取的策略，通 大连理工大学硕士学位论文 过在系统状态和调度策略间建立起合适的联系，作为驱动调度系统的知识库。若采用规 则来表达调度策略，则模式匹配驱动的调度系统就是动态的规则调度系统，它比启发式 规则调度系统增加了系统的柔性和适应性，相关的研究见【2 5 】 3 ) 邻城搜索方法 应用予生产调度问题的基于智能技术的并行搜索方法主要有：禁忌搜索( t s t a b u s e a r c h ) 、模拟退火( s a - - s i m u l a t e da n n e a l i n g ) 、遗传算法( g a - - g e n e t i ca l g o r i t h m ) 和人工 神经网络( a n n - - a r t i f i c i a ln e u r a l n e t w o r k ) 等优化算法。下面的章节将有详细叙述。 1 5 生产调度问题的分类和表示方法 生产调度的分类方法较多，下面逐一进行简要介绍。 1 ) 按定义分类【1 2 j 这是最基本的，最传统的分类方法。由定义可知生产调度问题基本上是由机器的数 量、种类与环境，作业的性质以及目标函数组成。在此，我们采用三元组的形式来描述 度问题，表示为：a l i y 。a 域表示机器的数量、类型和环境，分类情况如下： ( 1 ) 只有一台机器的调度称为单机调度，用1 表示；否则称为多机调度，用m 表示。 ( 2 ) 在多机调度中，如所有的机器都具有相同的功能，称之为平行机调度。平行 机调度中：若所有的机器具有相同的加工速度，称之为同速机调度，用p m 表示；若加 工速度不同，但每台机器的加工速度都是常数，不依赖于被加工的工件，称之为恒速机 调度，用q m 表示；若加工速度依赖于被加工的工件，称之为变速机调度，用r m 来表示。 生产调度 s c h e d u l i n g 平行机调度 l 乘性i 】| i 水作业调度l 单机调度 | | 多类机调度 p a r a l l e lm a c h i n e s i f l e x i b l ef l o ws h o p i s i n g l em a c h i n e | i 同遮机调度 i d e n t i c a lm a c h i n e s 恒速机调度 u n i f o i - mm a t h i n e s 变速机调度 u n r e l a k dm a c h i n e 流水作业调度 f l o ws h o p 开放作业调度 o p e ns h o p 车问作业调度 j o bs h 0 0 幽1 2 按机器分类 f i g1 2c l a s s i f i c a t i o na c c o r d i n gt om a c h i n e s 陈东升：基于遗传算法的模糊车间作业调度问题的研究 ( 3 ) 多机调度的另一种情况是多类机调度。多类机指的是具有不同的功能的加工 机器。在多类机调度中，被加工的工件需要在每台机器上加工。若每个工件在机器上的 加工顺序相同，称之为流水作业调度，用f m 表示；若每个工件可按任意顺序加工，称 之为开放作业调度，用o m 表示；若每个工件有自己固定的，相异的加工顺序，称之为 车间作业调度，用j m 表示。 ( 4 ) 在多类机中，还有一种就是柔性流水作业调度，它是流水作业和平行机的推 广。可表述为有s 类处理机，第j 类有s i 个平行机，每个工件有s 道工序，每道工序耍在每 类平行机中的台机器上加工，且每个作业的加工顺序相同，用f f s 表示。 机器的各种类型和环境总结见圈1 2 。口域表示工件的性质、加工要求和限制，资 源的种类、数量和对加工的影响等约束条件。在此，有必要先介绍一下工件的一些性质， 下面的数据描述了工件的性质。 ( 1 ) 加工时间向量 工件的加工时间向量0 = ( 钆，f ：，0 ) ，其中勺是工序乃的加工时间。 ( 2 ) 准各时间( r e a d y t i m e ) 准备时间r 是工件，；已经准备好可被加工的时间。 ( 3 ) 交货期( d u e d a t e ) 交货期d ，表示对工件，限定的完工时间。如不按期完工，应受到一定的惩罚。 ( 4 ) 优先因子 优先因子哆表示工件相对于其他工件的重要程度。加工时的一个重要限制是工 件间的优先约束( p r e c e n d e n c ec o n s t r a i n t s ) ，这种优先约束是一种偏序关系_ 。正 意 味着必须加工完才能开始加工。若至少有两个工件受到优先约束的限制，这些工件 幽1 3 优先约束圈 f i g1 3c h a r to f p r e c e n d e n c ec o n s t r a i n t s 大连理工大学硕士学位论文 称为相关的( d e p e n d e n t ) ，否则称为无关的( i n d e p e n d e n t ) 。一般用优先约束图来表述工 件间关系。图中点对应工件，弧对应偏序关系，始点为以，终点为，的弧对应以 ， 称z 为，i 的先驱，为上的后继。图1 3 是优先约束图的一个例子。 以上介绍了工件的一些性质。下面我们来介绍口域中常出现的一些约束条件： ( 1 ) ，：任务有不同的准备时间：如此域中不出现r ，则说明，= o ，j = 1 ，2 ，m 。 ( 2 ) p r m p ：加工时可中断；如不出现，则表示不可中断。 ( 3 ) p r e c ：表示工件的相关性；如不出现这些项，则表示工件问是无关的。 ( 4 ) b r k d w n ：机器故障( b r e a kd o w n ) 表示机器不能连续被使用。在确定性调度 中，机器的不可用时间是固定的，对同速机，可用的机器数在任何时亥0 都是时间的函数。 ( 5 ) n w t ：不等待( n o - w a i t ) 只出现在流水作业中，它指被加工的作业不允许在两 相邻机器闻等待。典型的例子是轧钢厂，被加工的钢材不允诲在两道工序之间等待，否 则钢材会凉下来不能继续加工。 以上所述任何一项都可以出现在口域中，并且还可以同时出现多项。 ，域表示要优化的目标函数，下面简要介绍几种常用的目标函数： ( 1 ) q 。：时间表长( m a k e s p a n ) ，可定义为：c 二= m a x q ，它等于最后9 n t - 完 的工件的完工时间，小的时间表长意味着机器有很高的利用率以及调度的合理性。 ( 2 ) q q ，0 ：加权总完工时间( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) ，总完工时 i n ( t o t a lc o m p l e t i o nt i m e ) ；加权总完工时间可定义为：c = 翻，c ，此处的权重意味着 两 月 工件的重要度；当( 0 7 = l ，j = 1 ，2 ，”时，就变成了总完工时间，即：c = 乏：c ，。 了= i ( 3 ) 哆d j ，d j ：加权总误工( t o t a lw e i g h t e dt a r d i n e s s ) ，总误工( t o t “t a r d i n e s s ) ； 加权总误工可定义为：d = o ) j d ，此处的权重涵义同上；如脚，= 1 ，j = 1 1 2 ，n ，就转 = l 变为总误工，即：d = f d ；。 葛。 这样，当口，口，y 中的内容自由组合时就会产生多种类型的调度。举例如下： 例： 砌i 助= p ，i 哆d j 表示的是m 台机器的、每个作业的所有工序的加工时间 都相等的、目标函数是极小化加权总误工的流水作业调度问题。 2 ) 按照工件准备状态分类 当所有的工件在调度时，都已进入待加工状态，可以开始加工，称之为静态生产调 度：反之，若工件陆续进入待加工状态，要随时对它们调度，称之为动态生产调度。 陈东升：基于遗传算法的模糊车间作业调度问题的研究 3 ) 按照调度问题参数性质分类 各工序的加工时间和其它有关参数是已知的确定量时，称之为确定生产调度；反之， 当它们是模糊量时，称之为模糊生产调度。 1 6 本文课题来源与主要内容 1 ) 课题来源 本课题来源于8 6 3 项目( d l o c o m i e 总体规划与解决方案，在大连机车厂，产品 设计、工艺规划、车间生产组织管理等过程中涉及到很多应用系统，主要包括：c a d 、 c a p p 、p d m 、e r p 、m e s 等。但目前这些系统还处于单元技术的应用，各部门业务管 理过程的集成和整合方面有待提高，企业需要迸一步建立集成化信息管理平台，支撑企 业业务过程的集成和整合，进而提高核心竞争力。所以我们在深入研究各系统业务流程、 需求功能、信息集成等的基础上，结合生产管理、企业信息化等方面的最新技术，本着 “立足现在，面向未来”的原则，提出了信息化总体规划与解决方案。而在对m e s 系统的 应用情况和生产调度技术的研究过程中，发现了企业在车间作业调度方面的落后，因此， 本文对其进行了重点研究，研究结果对于企业生产管理具有一定的指导意义。 2 ) 主要内容 因为利用遗传算法解决典型与模糊车间作业调度问题时，算法结构是一致的，区别 在于解码过程的差异和适应度函数的不同，所以本文先对传统遗传算法进行了改进，并 以此为工具应用于典型车间作业调度问题的几个算例，待验证了算法的有效性和可行性 以后，结合模糊集合理论对模糊车间作业调度问题进行了解码并设计了适应度函数。 第一章主要分析了制造业环境的变化，介绍了几种先进的制造模式，从而引出研究 生产调度技术的重要性和必要性，进而总结了其研究进展并对其进行了分类。 第二章主要对车间作业调度问题进行了定义，分析了其特点，建立了其数学模型， 引出了模糊车间作业调度和典型车间作业调度问题，并对解决此问题的最有效的几种邻 域搜索算法做了简要介绍。 第三章重点叙述了遗传算法的起源、发展、生物模型、基本思想、特点和基本操作 流程，并且对模糊集合理论的发展、模糊数的操作及评价方法做了较详细介绍。 第四章主要是在分析比较了多种编码方式、遗传操作方式、算法终止条件优劣的基 础上，设计了一种自适应遗传算法，并设计了模糊车间作业调度问题的适应度函数。 第五章主要是介绍了实现此算法的一些伪代码和仿真实验结果。 第六章得出了全文的结论并对未来模糊车间作业调度问题的研究做出了展望。 大连理工大学硕士学位论文 2 车间作业调度问题的研究 2 1 车间作业调度问题概述 车间作业调度问题是最一般的、最复杂的和最具难度的生产调度问题【”。正如 c o n w a y 等人在生产调度理论【2 6 所述：“一般的车间作业调度问题