硕士论文-基于遗传算法的多目标动态作业车间调度及应用研究.pdf

基于遗传算法的多目标动态作业车间调度及应用研究 s t u d yo ft h ed y n a m i cj o b - s h o ps c h e d u l i n gb a s e do n m u l t i - 0 b j e c t i v eg a a n d a p p l i c a t i o n s 作者姓名 学位类型堂压亟 学科、专业 扭越电王王程 研究方向 让箕扭塞盛剑造挂盔 导师及职称 筮垡垣副熬援 2 0 0 6 年4 月9 日 基于遗传算法的多目标动态作业车间调度及应用研究 摅要 有效的调度方法与优化技术的研究和应用，对予制造企业提高难产效率、 降低生产成本等方面越着重骚作用，阂而越来越受到学者们的关注。 本文在综会国内努关予车闲调度阕惩辑究状况数基础上，考虑貔霞体避车 间逡作的实际情况。对作业车间的生产调度问题进行了深入系统的研究。 首先，建立了柔性作业车间调度问题的多目标数学优化模型，并结合合肥 车轿有隈责任公司项萄绘出了一个建模实例。 其次，撼篷运用遗传算法求解终媲车阙调发模型。 然质，提出了多目标车间动态调度的实现方案，给出了仿真实例。共采用 面向对象的方法分析和设计了车间调度系统。 最嚣，对前瑟瓣算法串参数的设计蔽及一骜改进漪方法作了理论上的解释。 对如彝进行蠢效的适应度权僮分怒提嫩了均篷是透应法、均蕊波动鑫适应法； 羹 均值引导权薰法三种改进方式。 关键谲：车黼作监菁霉度，多强标傀伍，遗传算法，投值分既 s t u d yo ft h ed y n a m i cj o b s h o ps c h e d u l i n gb a s e do n m u l t i o b j e c t i v eg a a n d a p p l i c a t i o n s a b s t r a c t h o wt op l a na n ds c h e d u l eb e c o m e sak e yi s s u et om a k em a n u f a c t u r ep r o c e s s s m o o t h l ya n de f f i c i e n t l y 。i ti sv e r yi m p o r t a n tt or e s e a r c ho ne f f e c t i v es c h e d u l i n ga n d o p t i m i z a t i o nt oi m p r o v ep r o d u c t i v i t ya n d r e d u c ec o s t 。s om o l ea n dm o r er e s e a r c h e r s p a ya t t e n t i o nt ot h i sr e s e a r c h o nt h eb a s i so ft h et e c h n i c a lr e v i e wo nt h ed o m e s t i ca n df o r e i g nr e s e a r c h ，t h i s t h e s i sh a sa ne x t e n s i v ea n ds y s t e m a t i cs t u d yo nt h ej o b s h o ps c h e d u l i n gc o m b i n i n g t h ea c t u a lj o b s h o po p e r a t i o n 。 f i r s t l y ，c o n s i d e r i n gm u l t i - o b j e c t i v eo fs h o ps c h e d u l i n g ，t h em a t h e m a t i c a lm o d e l o ff l e x i b l ej o b - s h o ps c h e d u l i n g ( f j s s ) f o rb i - o b j e c t i v ei se s t a b l i s h e d a tt h es a r a e t i m e ，am o d e l i n ge x a m p l ei sg i v e nc o m b i n i n gt h ep r o j e c to fh e f e ia u t o m o b i l ea x l e c o ，l t d s e c o n d l y ，t os o l v et h i sm o d e l ，ag e n e t i ca l g o r i t h mi sd e v e l o p e d 。 t h i r d l y ，t h e r e a l i z a t i o n p r o j e c t o fm u l t i - o b j e c t i v eo p t i m i z a t i o n ( m o ) o f j o b s h o ps c h e d u l i n gi sp r e s e n t e da n das i m u l a t i o ne x a m p l ei sg i v e n t h i sp a p e r a n a l y s e sa n dd e s i g n st h ej o b - s h o ps c h e d u l i n gs y s t e mu s i n gt h eo b j e c t - o r i e n t e d a n a l y s i sm e t h o d f i n a l 玲，e x p l a n a t i o n sa r eg i v e nf o rp a r a m e t e r sd e s i g na n ds o m ei m p r o v e d a p p r o a c h e so ng e n e t i ca l g o r i t h m ( g a ) a p p e a r e di nt h ep a p e r 。t h r e ek i n d so fn e w a d v a n c e da p p r o a c h e sa r eo f f e r e di no r d e rt od i s t r i b u t et h ew e i g h t so fo b j e c t i v e f u n c t i o n se f f e c t i v e l y t h e ya r ea v e r a g ea d a p t i v ew e i g h ta p p r o a c ha n da v e r a g e a n df l u c t u a t i n ga d a p t i v ee v a l u a t i o nf u n c t i o na p p r o a c ha n da v e r a g e l e a d i n gw e i g h ta p p r o a c h 。 k e y w o r d s ：s h o ps c h e d u l i n g ，m u l t i - o b j e c t i v eo p t i m i z a t i o n ，g e n e t i ca l g o r i t h m ， d i s t r i b u t i n gt h ew e i g h t so f o b j e c t i v ef u n c t i o n s 捶豳清单 图1 1 全文结构安排9 图2 1f j s s 模型的输入输如图1 3 图3 1 不可行和非法性1 9 鹫3 2 褪始染色棒群鹣生蔽2 0 图3 3 求解多目标f j s s 问题的遗传算法主要构造过程示意圈2 4 銎3 4 参数输入爨露3 1 图3 5j o bs h o p 遗传操作遥算主界面3 l 圈3 6 半活动调度鸟活动调嶷敕缝浆毙较3 2 图3 73 工件3 机器j s p 的传统析取图3 3 图3 83 工l 牛3 机器j s p 机器有向柝取图3 4 图3 9 实例中机器有向析取图展示3 4 图4 i 输入界面4 d 鹜4 2 程穿蠢动生成的首特瀚4 l 图4 _ 3 调度超时提示框4 l 舀4 4 完全俊佬完工辩蠲运簿参数裙始设鬣4 2 图4 5 运算结果输出图4 2 壅4 。6 霹嚣撬琵嚣令嚣标瓣运算参数农始莰器4 3 图4 7 主体邋算界面4 4 图4 。8 多个嚣标同时优纯熬运算譬聚4 4 图5 1 双目标最大化意义下的受支配结和非受支配解的示意图4 6 图5 。2 取样区闼4 8 图5 3 离散函数样本取值示意图5 0 图5 4 算法输入参数界面5 图5 。5 使用改进法运算结采输出甘蒋图5 5 图5 6 仿真调试程序流程图5 9 图5 。7 菜耱群在凝定最大遴能代数爵褥羽豹翠熬解6 0 袋格清单 表2 14 5 ，g 坨m a x f j s s 的加工数据1 6 表3 。1 个体凝惫体豹适应疫及其瓣痊轮盎建选择概察分配3 0 表4 1 本铡审鹣麴工数鬟3 9 表4 2 各机器加工工件的费用综合值3 9 表5 1 随机抽样的染色体及对威备目标函数值5 2 符号清单 i ：工 窿号，i = l ，2 ，3 ，。n j ：_ - c i 鹊王彦号，j = l ，2 ，3 ，j k ：机器序号k = l ，2 ，3 ，k n ：工件数挺 k ：机器总数 m 社：工件i 的第j 道工序在枫器k 上的加工时闻 n k ：撬骥k 革谴鞋趣热工戒零 。辩：工释i 静第j 逶工痔在撬瓣k 上静开始对丽 “社：= i 二件i 的第j 道工序在机器k 上的完工时间 l 职：所有工件在机器k 上的完工时间 砩：所有工件在机器k 上加：_ 【= 的总成本 m s ：j 舞蠢工毂二的最后完：j ：时间 h s ：掰蠢工纷懿最鑫完工慈藏本 q ：i i 豹交货期 。：工仆i 提前完工的惩罚系数 ：工件i 拖期完工的惩罚系数 。“：个体i 被选中的概率 。t 耐：逑废度 r ：震瓣蕊 o ：机器成本矢量 m ：第。台机器的开机工作时间 7 ：机器开机运行时间欠量 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成聚。 撵我掰知，豫了文中黪翮翔鞋稼注帮致潦鹣地方努，论文巾不包含箕健入已疑发表或撰写 过的研究成果，也不包禽为获得 盒a 王些盘堂 或其他教育机构的学位或证书而使 霜过静穗辩。每我一翳工作静辩志对本磷究掰簸豹任蔼贡靛均己在论文中终了胡确静说明 并表示谢意。 黜嫦器签名；稚粼宇 签字嚣期妇蟛年箩弱争西 学位论文版权使用授权书 本学谯论文于# 者完全了瓣众l 篓兰塑塞雯有关傈窘、使用学位论文静筑定，有较傈留 并向阑家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权佥 疆薹驻盍生蜀虢蒋学佼论文蠹孽众帮或部努肉容编入有关鼗据库进行检索，胃潋采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 豫密豹攀经论文巍解密鑫逶用本授投书) 学位论文作者签名：辱坚矾字 签字日期：劲嘭年f 月手日 导师签名 签字日年0 月斗翻 工搏革链：譬绞屯毫崭赦髹翼岔鼋窖i 爹砖乒警毽话：。州一f ，善鼻卯。 通讯地址：中l 通蔷缎舌肥辛墀玛歇j l g 运k 编：j3o 口岁 致谢 值此论文定稿之际，我衷心感谢导师朱华炳老师。在两筇半的攻读硕士学 位期间，朱老师在学习狙科砑上绘予了我悉心的指器，生活上绘予了炙熬蛉关 悔，论文的字里幸亍阉滗不凝聚麓老师的心斑。朱老掰严谨求嶷的治学 节风、诲 人不倦的师者风范时寡0 激励着我克服困难，认真完成本论文的工作。他求是创 新戆科研璇糖彝言健蹙教匏烬纛鼹蓖，将使我在以藤戆磅究z 终孛受慈匿浅。 他热情随和、宽大为怀的个性修养更将便我受益终身! 感谢制造与工业正程系的尹志强、宋守许、刘悫峰、桂贵生、王淑旺老师， 凌警对掌霹鞫工终孛绘予瓣罨渤帮支持。感滚嚣冬多寒窝我一起共事过豹嚣凭 弟姐妹们。他们是：张怀、薛峰、董艳萍、李红英、范仁杰、吕冬梅、潦付军、 柳欣、余成菔、周文广、金鑫、阐震、槎淤坤、俞辉、王慧。感谢他们绘予我 豹鼓藏、帮鞠与窝笈。 感谢机电2 0 0 3 硕士研究生班的所有间学，特别是：余伟、何平、吕义等。感 谢健们嚣年多来给予我的关1 2 、，謦爨帮裴。 感谢挚发张怀博士、刘琼博士、郑彩霞硕士、陈波硕，感谢室发余成益 硕士，感谢他们在工作和生活上对我的关心和支持，永远难忘读研期间和他们 共溺度过熬鄂段美磐孵毙。 并祝愿他们在今爝的人生路上一帆风顺! 最后，感谢未婚娄张燕在缴活和工作上给予我的支持与避解，感谢父母对 筏多年稳麓莽，镌稻黢凌戆蘩爨释无尽豹关环是簸藏我不断送彀静动力。浓滚 泶情，无以宙报! 感谢我的妹妹程汝、感谢张燕父母和姐姐、姐夫，他们给予我 耪神上和物质上的支持，是我漫漫求学路上的力量源泉，我愿与他们共享收获 熬喜悦i 谨以此文献给所肖关心、帮助和支持过我的人们! 作者：程翔宇 2 0 0 6 年4 月 予合王大 第一章绪论 i i 课糕的提出疑意义 敏捷露l 遥佟必2 l 毽纪众、篮浆受遴毒l 造模式，综合了j i t 、并行工程、精麓生 产等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品， 即是完全强向顾客豹。在运季中模式下如何进静组织管理，包括如德组织动态联 鼗、魏何重梅率阉移单元、如俺安稚生产计耄l l 、鲡 琴避稃调度都怒我 f 面l 黼的 主要问题。其中车间作业调度与控制技术是实现生产高效率、高泶性和高可靠 性的关键，有关爨料表明，制造过瑕中9 5 之阅的消耗怒在非切削过程中“。因 诧，裔效的谲震方法与优化技本酶磷究稻应弼，己成为先进稻造技术( a 骶一 a d v a n c e dm a n u f a c t u r i n gt e c h n o l o g y ) 实践的基础和关键。 那么赞么是攀闽调度? 车闽调度生要是针对一顼可分解静王馋( 鲡产品铡 造) ，探讨在尽w 能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下， 通过下达生产指令，安排旗组成部分( 操作) 使用哪些资源、其加工时间及加工 兹先嚣蹶j 挚，以获褥产品制造对耀鬣藏奉豹最优化“。农理论礤究孛，车阗终 业调庹问题常被称为排序问题或资源分配问题或组合伐化问题。猩过去的几十 年里，旗于实际的及理论上的考虑，不断地激励着人们寻找新的调度算法，其 孛一个囊要琢因楚产燕毒l 逑雾静枣场竞争蛙在不瑟提高，好熬玺产调度憝怒嶷 资源的利用率和操作管理水平，生产出具有竞争力的产晶。车间的调度优化工 作，因其在提高生产效率，降低生产成本等方筒所起的燕要作用，正越来越受 笺学毒稍熬关藏，也是零渫蘧豹磅究意义蘑袭。 1 2 车间调度问麟研究现状 调度问题的研究始于2 0 世纪5 0 年代，j o h n s o n 提出了解决n 2 f c m a x 和部分 特臻瓣n 3 f c m a x 蠲遂鹣俊纯算法，徒表调度壤论磷究瓣开始：6 0 7 0 年鼗建 立了调度理论的主体( 经热调度理论) 并重视调度复杂性的研究。随着7 0 年代后 期调度理论研究的深入及镑种交叉学科的发展，又涌现出了许多新的车间调度 理论每方法“，翔棒经霹络、穰叛避灾法、遗传算法等。 过去十年来，如何运用遗传算法解决工业正程中的备类问题融成为管理科 学、运筹学、工她与系统_ i 程领域许多学者和忑程实践人员的研究课题，其原 嚣在予遗传箕法怒一耱强蠢力静、疲胡范围十努广泛静魏祝搜索後纯技寒，它 对许多传统方法难以解决的问题是非常有效的。在大多数工程优化问题中，常 常邦带窍复杂豹约束条件，簿摹的遗传算法往往不能很好地解决这类工程优化 阊避。谶诧，翻僻结合阀溅的特性簸成为面商王堑工程逡传算法滟研究焦煮。 1 2 1 率问调度问题的描述、分类及特点 扶数学觏划的旁度看，车阈调度可表达为程等式或不等式约震下，对一个 或多个离标函数的优亿。现代典型的率闻调度问题是：将作业均衡堍安排至i 各处 理机上，弗合理地安排作业的加工次序和开始时间，侵约束条律被满怒，同时 优化一些憔能指标。 对于举间调度问题，g r a v e s 等人进行了分类憋理“3 按照不同的分蹙标准， 可分为以下四种类型： ( 1 ) 投擐热工系统的复杂程度，可分为单祝、多螽并行瓿、f l o ws h o p ( f s p ) 窥j o bs h o p ( j s p ) 。 单枫调度问题是所有的操作任务都在单台机器上完成，为此存在强务的优 化排队问鼹 多台并行机的调发问题更复杂，因而优化问题更突出：f l o w s h o p 型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序； j o bs h o p 遐最一般的调度类型，不同的作业具有不同的加工操作和加工顺序， 著不限列佟照瓣热工设备。 ( 2 ) 禳攥缝猎标，分为燕予诞廑费蠲帮调度歉能戆指标两太类。 ( 3 ) 根搬生产环境的特点，w 将调度问题分为确定性调度和随机憾调度问 题。 ( 4 ) 根据作业的加工特点，w 将调度问题分为静态调度和动态调度。 现代率澜调度类型往往是j o bs h o p 型的，本渫题的研究针对j o bs h o p 型 熬调度闫麓袋矛。 生产系统串，j o bs h o p 网鼷移 究对象是由m 螽橇器 m l ”，魄；撩量n 耱工 牛f j ”，j 。 。其中，称所加工的工件为任务，工件在机器上的加工为操作，工 件基于加工工艺所决定的限制谯某些机器m 上的加工顺序为约束条件。并且， 设0 。，为第i 个工件j 1 在第j 个机器m ，上的操作，同时设每个操作0 。所需要的 作业时阗怒潮定豹。对于生产线调度问题即加工排序阍题，要对每台机器玩来 疆定n 令王移五( i = 1 ，n ) 熬一令热_ i 颓廖，农与工艺约束条羚稳餐豹藜 提下，使新搬定的某个性能指撩这至最优。 对于上述生产调度问题，m x n 的工件顺序矩阵总共有力，个可能的排序方案。 以机器数m 一1 0 和工件数n = 2 0 的祭生产线的调魔问题为例，要从2 01 个可能排 序方案中，找出一个排序方案使性能指标达到最优，无疑是个计算高度复杂 躲趣题，复杂程度己超越了传统倪他方法豹处理携力。这类闯题称为n p 雅闯疆。 实际溪发熬类鍪是j o bs h o p 黧，毒戮下特点： ( 1 ) 复杂谯 由于漱卸作业、装卸设备、库场、搬运系统之间相互影响、相互作用、每 个作业又骚考虑它的到达时间、装卸时间、准备时间、操作顺序、交货期等， 因而相当笈杂。而且调度问题怒在等式或不等式约束下求性能指标的优化，在 圣 算量上钱钱楚n p 难阉嚣，帮骧麓茂瑟援摸戆增大，瓣子求簿最优纯憨诗粪量 至捂数增长，傻褥一些常惑戆最馋纯方法往往无缝必力。 ( 2 ) 动态随机性 2 在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达 时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现 一些突发偶然事件，如设备的损坏修复、作业交货期的改变等。 ( 3 ) 多目标性。 实际的计划调度往往是多目标的，并且这些目标间可能发生冲突。k i r a n 等人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基 于生产成本的目标“1 。这种多目标性导致调度的复杂性和计算量急剧增加。 1 2 2 车间调度问题的研究方法 在对车间调度问题进行研究的方法上，最初是集中在整数规划、仿真和简 单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各 种新的相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优化 方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等，使得调度问题 的研究方法向多元化方向发展。总结起来，现有调度问题的研究方法大体上可 以分为以下几种类别。 ( 1 ) 基于运筹学( 0 r ) 的方法 o r 方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝 定界法或动态规划算法进行解决调度最优化或近优化问题，属于精确方法。这 类方法虽然从理论上能求得最优解，但由于其计算复杂性的原因、因而不能获 得真正的实用。对于复杂的问题，这种纯数学方法有模型抽取困难、运算量大、 算法难以实现的弱点，仅适合较小规模的调度问题。 ( 2 ) 基于启发式规则的方法 从实用的角度来看，启发式算法因其易于实现、计算复杂度低等原因，在 实际中得到了比较广泛的应用，并且不断涌现出许多新的调度规则，可将其分 为三类：简单规则、复杂规则、启发式规则。虽然启发式规则常被用于实际当中， 但它们一般不具有全局优化的特点”1 。 ( 3 ) 控制理论方法 g e r s h w i n 等人从控制理论的角度出发，较全面地阐述了控制理论方法在制 造系统的应用情况”1 控制论方法比较适合定量地定义基本问题，但还没有形成 一套有效的调度模型表达、分析设计的技术。其缺点是：模型描述能力有限，建 模时不得不对真实环境进行大量的简化，求得最优解的时间随着问题规模的增 大而呈指数规律增长。因此也只适合对小规模的系统求解。 ( 4 ) 基于人工智能( a i ) 的方法 a i 方法是通过提高调度方法的智能而解决各类生产调度问题方法的总称。 单一的数学方法和工具不足以解决实际的调度问题，a i 和专家系统的出现对解 决调度的实时性和智能性提供了新的辅助手段。它们用于调度可以克服数学规 划和仿真方法的不足，根据系统当前的状态和给定的优化目标，对知识库进行 有效敬痘发焱搜索秘共牙模糊接理枫裁，避汗了繁琰懿诗葵，蒡选撵最撬静调 度策略，为在线决策提供支持。在綦于知识和规则的调度系统中，常用的知识 表示法有产生式规则、语义溺络、攒絮等；零嗣的调度技零凑生产缎烈、探试 法援索、机会主义的推理、仿真和分级式的分解等。 专家系统作为一个较好的调度方法，存在一些不足之处：对新的调度环境 静遥癍性较麓。搿发竭籁长、藏本昂贵。需要缎多现场调度入爱丰富韵调 度经验和知识，然而获取调度人员的调度经验是较困难的和有限的。同时，由 予矗l 技拳本巍发展承平豹疆懿，它蠢三个臻驻缺黧：t m 7 逮凌浸、对异步发囊稳 外来事件不敏感，系统不通用嘲。 ( 5 ) 基予d e d s 戆惩柝模型方法 对于车间类型的d e d s ( d i s c r e t ee v e n td y n a m i cs y s t e m ，简称d e d s ) ，间样 可用其解析模型与方法来解决车间调度问题。如极大代数法、动态媲划法等。 但它们都只逡合予翻造系统瀚性能分析。p e t r i 两除黩有并发、动态、奁观等优 点外，还有自遵循最小物流费用原则,采用布局的块树表达方式,对车间设备布 局进行了遗传算法优化设计,并按照优化结果生成车间的虚拟场景,计算结果表明了算法的有效性;考虑到车间物流费用和车间面积双目标优化问题,提 出了车间设备布局的多目标优化方法,仿真结果表明算法取得了良好的效果;将脑模型联接控制器与遗传算法相结合,提出了一种全新的车间布局多目标 优化方法,该方法具有自学习,自适应的特点,并运用算例验证;研究机床-工人双资源、时间-成本双目标的车间作业调度问题,提出了启发式规则、模糊 优选技术与遗传算法相结合的调度算法,算例验证了启发式规则和模糊优选技术的引入提高了遗传算法的实用性和搜索效率;根据本文提出的框架模型 和算法,对系统进行模块划分和功能描述,开发了车间虚拟制造软件系统,并将其mes软件集成,正在某大型企业试用. 8.期刊论文 曹成辉.王坚.cao cheng-hui.wang jian 基于改进遗传算法的多目标jsp调度研究 -信息技术2009(5) 针对多目标车间作业调度问题(jsp),提出了一种混合遗传算法,将多目标遗传算法得出的初步优化结果作为粒子群算法的初始粒子,利用粒子群算法 强化局部搜索,加快收敛速度,改善了简单遗传算法局部搜索能力差、迭代效率低的问题.仿真结果表明了该算法对jsp调度的良好效果. 9.学位论文 鞠海华 基于nsga-算法的作业车间调度研究 2008 车间调度方法与优化技术的研究已经成为先进制造技术的基础和关键。在制造业车间，调度问题的规模巨大，所涉及的对象复杂，系统动态性强。 调度问题本身是一类组合优化问题，也是典型的np(np-complete)问题。 车间作业调度问题具有计算复杂性、动态约束性、多目标性等特点。多目标优化问题在科学和工程等领域是一个热点问题，同时也是研究的一个难 点。传统的多目标优化方法在某些复杂的多目标优化问题中存在不足，因此渐渐地被一些优越的多目标优化算法所