（计算机应用技术专业论文）基于神经网络的流水调度算法研究.pdf

东南大学硕士学位论文 摘要 调度问题是工农业生产、国防、科研、交通运输以及各种服务行业中普遍遇到的问题。 调度问题要研究的主要内容就是根据产品制造需求合理分配产品制造资源，进而达到合理利 用产品制造资源、提高企业经济效益的目的。无等待流水调度问题是目前应用系统中最常见 的一类调度问题，理论上已经证明无等待流水调度问题为n p 问题，因此研究能够在较短时 间内得到高质量近似最优解的调度算法具有重要意义。 考虑最小化最大完工时间( m a k e s p a n ) 和最小化总完工时间( t o t a lf l o w t i m e ) 的无等 待流水调度问题，提出基于h o p f i e l d 神经网络( h n n ) 的可变化阈值混沌模拟退火( v a r i a b l e t h r e s h o l dc h a o t i cs i m u l a t e da n n e a l i n g ，v t c s a ) 神经网络算法和基于构造优化神经网络 ( c o n s t r u c t i v e - o p t i m i z e rn e u r a ln e t w o r k ，c o n n ) 的c o n n 算法、n c o n n ( n e w c o n s t r u c t i v e - o p t i m i z e rn e u r a ln e t w o r k ) 算法。将无等待流水调度问题对应的约束优化问题 转化为无约束优化问题，通过构造适当的能量函数将无等待流水调度问题映射到h o p f i e l d 神经网络上；向神经元的阈值添加一个逐渐减小的因子，采用可变化的神经元阈值扩大神经 网络的搜索空间，增大神经网络发现全局最优解的概率；利用竞争学习算法在插入操作的邻 域内搜索以提高解的质量，通过网络在构造状态和优化状态间切换，使得c o n n 、n c o n n 具有跳出局部极小值的能力。 通过使用t a i l l a r d 标准测试实例，将c o n n 、n c o n n 与目前最好的几个快速算法( d s 算法、目标增量法和p h i p 算法) 进行比较。结果表明：对于最小化m a k e s p a n 问题，小规 模问题d s 算法能够得到最好的结果但比c o n n 算法花费更多的时间，大规模问题c o n n 算法在时间性能和结果的最优性方面都优于d s 算法和目标增量法；对于最小化t o t a l f l o w t i m e 问题，o e d , 规模问题n c o n n 算法在时间性能和结果的最优性方面都优于p h i p 算法，大规模问题n c o n n 算法花费的时间稍多于p h l p 算法但能够得到最好的结果。 关键词：无等待流水调度，最大完工时间，总完工时间，神经网络 东南大学硕士学位论文 a b s t r a c t s c h e d u l i n gp r o b l e m s 耐s tw i d e l yi ni n d u s t r y ，a g r i c u l t u r e ，e n f o r c e m e n t , s c i e n t i f i cr e s e a r c h ， c o m m u n i c a t i o na n ds e r v i c ei n d u s t r i e s i t st a r g e tl i e si nt a k m gu s eo fr e s o u r c e se f f e c t i v e l ya sw e l l a sm e e t i n gr e q u i r e m e n t so fm a n u f a c t u r i n gp r o c e s s e s n o - w a i t f l o w s h o pi s aw e l lk n o w n s c h e d u l i n gp r o b l e m h o w e v e r , i ti sn p - h a r da n do f t e ns o l v e db yh e u r i s t i ca l g o r i t h m si np r a c t i c e , w h i c hp r o d u c e sh i g hq u a l i t yn e a ro p t i m u ms c h e d u l e si nr e a s o n a b l ec o m p u t a t i o n a lt i m e n o - w a i tf l o w s h o pw i t hm i n i m i z i n gm a k e s p a na n dt o t a lf l o w - t i m ei sc o n s i d e r e di nt h i st h e s i s t h r e en o v e ln e u r a ln e t w o r ka l g o r i t h m sa r ep r o p o s e d , w h i c ha r et h ev a r i a b l et h r e s h o l dc h a o t i c s i m u l a t e da n n e a l i n g ( v t c s a ) n e u r a ln e t w o r k ，t h ec o n s t r u e t i v e - o p t i m i z e rn e u r a ln e t w o r k ( c o o o ， a n dt h en e wc o n s t r u c t i v e - o p t i m i z e rn e u r a ln e t w o r ko q c o n q ) t h es c h e d u l i n gp r o b l e mi s t r a n s f e r r e di n t ou n r e s t r a i n to n ea n dt h e nm a p p e do n t ot h en e u r a ln e t w o r k su s i n gi n v e s t i g a t e d e n e r g yf u n c t i o n 。ad e c r e a s i n gf a c t o ri sa d d e dt ot h et h r e s h o l do ft h en e u r a lt oe x t e n dt h es e a r c h s p a c eo ft h en e u r a ln e t w o r k ，w h i c hr e s u l t s i nah i 【g hp o s s i b i l i t yt of i n dg l o b a lm i n i m a a c o m p e t i t i v es t u d ym e t h o di sa d o p t e dd u r i n gt h es e a r c hp r o c e s st of i n dh i g hq u a l i t ys o l u t i o n s l o c a lm i n i m ao fc o n na n dn c o n nc a nb ea v o i d e db ys y s t e m a t i c a l l ys w i t c h i n gb e t w e e n c o n s t r u c t i v ea n do p t i m i z i n gs t a g e s e x p e r i m e n t a lr e s u l t so n10 0b e n c h m a r ki n s t a n c e so ft a i l l a r ds h o wt h a tc o n no u t p e r f o r m s t h eb e s te x i s t i n ga l g o r i t h m s ，s u c ha sd sa n dt h eo b j e c ti n c r e m e n tm e t h o df o rm a k e s p a n m i n i m i z a t i o n n c o n no b t a i n sb e t t e rs o l u t i o n st h a nt h eb e s t - s o - f a ra l g o r i t h mp h lpf o rt o t a l f l o w t i m e k e yw o r d s ：r i o - w a i tf l o w s h o ps c h e d u l i n g ；m a k e s p a n ；t o t a lf l o w - t i m e ；n e u r a ln e t w o r k 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查 阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：厄都暨 导师签名： 研究生签名：垒重3 聋 导师签名： 第l 章绪论 1 1 调度问题及其分类 第1 章绪论 1 1 1 调度问题的背景 调度问题是工农业生产、国防、科研、交通运输以及各种服务行业中普遍遇到的问题， 有着广泛的应用背景。调度问题研究的主要内容就是根据产品制造需求合理分配产品制造 资源，从而达到以合理的尽可能底的成本利用产品制造资源、提高企业经济效益的目的。 这里的资源可能包括加工时间、占用的库存空间、使用的机器以及人力资源等。调度问题 是产品制造行业中共存的问题，与c i m s 中的减少时间( t ) 、降低成本( c ) 、提高质量 ( q ) 、提高服务满意度( s ) 为宗旨的工厂管理理念在产品制造层的应用紧密相关，是c i m s 领域中研究的重要课题。 一般地说，凡是有多个不同任务要完成，就有调度问题的存在。这些问题的共同特征 就是要将多个等待执行的任务安排一个执行的顺序和时间，将有限的人力、物力资源分配 给不同的任务，使预定的目标达到最优。这里的目标可能是最小化产品的制造时间或生产 成本等性能指标。对于n 个工件在m 台机器上执行的问题，可能有多个候选的执行顺序， 怎样安排执行顺序，才能得到最优或近似最优的目标函数值( 制造时间或生产成本等) ， 就是调度( s c h e d u l i n g ) 问题。寻找合理调度方案的过程就是对工件的作业顺序进行组合优 化的过程，故调度问题有时候也称为排序( s e q u e n c i n g ) 问题。其中，“机器”可以指工厂 里的各种机床、维修工人、轮船要停靠的码头、计算机的中央处理器、存储器、输入和输 出设备等，即代表“服务者”；而“工件”，则是等待机床加工的各种零件、待修理的机 器、即将停靠码头的轮船、等待处理的程序，即“服务对象”。对于一般的调度问题，“机 器”和“工件”都有多个，调度问题要解决的是确定服务者对服务对象的服务顺序和时间， 使目标函数达到最优。由于同一台设备往往可以加工多个零件，一个零件也可能有多道工 序要到多台设备上去加工，不同零件的加工工艺路线也可能不相同，而每道工艺的加工时 间也可能不相同，这就使得调度问题非常复杂。 调度问题的研究不仅具有重大的现实意义，而且具有深远的理论意义。理论上已经证 明流水调度问题是n p 难题【1 1 ，要想用多项式时间复杂度的算法找到最优解是不可能的。因 此，求解调度问题的近似最优解是十分有必要的。目前的研究主要可以分为两类方法：启 发式方法( h e u r i s t i c s ) 和元启发式方法( m e t a h e u r i s t i c s ，包括人工神经网络【2 】、遗传算法例、 模拟退火算法【4 】、禁忌搜索5 】和蚁群算法1 等) 。启发式方法虽然能够快速给出结果，但在 最优性方面，元启发式算法在总体上优于启发式算法。目前文献中提出的元启发式算法的 计算复杂度普遍较高，求解大规模问题要花费更多的时间，在实际应用系统中采用元启发式 算法的系统还比较少【刀。因此，研究高质量近似最优解的快速算法具有重要意义a 熏礅丈学礤虫鬻攮谚鬻 l 。l o 满寝润越静努粪 1 鬻纛瓣瓣蘩爨誉鬻黪辩穗嚣壤；煮誉游蘸黪黉露蔑黼，黎麓瓣黪羹蠢蒗毽黎蒸粼穗溪。 糕务鞠鹳麟瓣鼗麴特镪势樊游。 撩糍鬟静释粪黎熬蕊攀鬻，群嚣势舞蘩瓣纛、零耩掣彝斟蒋黼萄赜索瞬港赛，攀辩溱、 辩移撬霹撬r 辘麟燃躺轻嗡谡魔，所誉罐磐瓣藤王鼹线巍酝枢藤黪潍感车潴耀l 瓣 霉襄彝薅耱爹耩溪纛辫鼗蕊枣赫静簿熬麓漆魏蠢攀撵溪黎攀髂鬻溪篓歉渗辍鞫瓣雾彀 测糜润趱。 攘援器裂这攀瓣婺媾獯零露，霉鼗势羚簿寨溺囊耪萄慧瓣壤薅袭，箕孛簿瓣镳瀵 燃掇姆枣雠务郡融猁瀵纂阕* 排序越辩辫窀程】一次封苣擎# 瓣穗悫灏度怒攒檄辫黪 然鬻慈攀麓* 薰黪黪蘩溱黎黧擦霞戆蕊熬鬻黪遴壤瓣纛。 羰器瓣涵黢瓣莽游，蠛露麟魏海爹耱粼澜游罐凝蠲麓，翔瓣争潮攀溺溅瘩溯攫 瓣瓣；暴小鞋慧凳篡瓣瓣墨珏瓣l 箩融熬嘲襄爨冬嵇豢突黧羹麓惩溯隧鞲# 酶黎爨 黼潦幂丽的晦题。熟京王黠嗡最小霹激憷馕赛滁稳趱鬻激滟莉丽、任务撼糗滤趱 瓣蕊鬟糕蒸痒霉爨枣爨麦窕忑黪簿爨零辫耋襄壤疹霪熬鬟声溪装憋懑。蕊黪蒸慧 黼黎溪躐麴芏露l 潦嚣簿餐瓣滚黪然麓溪。蒸稳鬻耩灞懿港麴濑参戳游麟然耱 嬲翻赙赫端程葶剡艇褰嚣魍匿中掷套簿举辩羽器裳。 燃攥参数触性质幂脯* 霹璐静静穗茂髓润藕羹徽裙美参熬瓣酶定常堂彝确懑粼谣 壤瓣舔纛熬王黪灏黪蒸健裰焚参熬麓麟懿黛囊熬嚣穗爨溅辚鏖勰霪察骧爨瓣溪塞 灏豢羚遮濒辩穗蕊瓣蓬雀灏浚妻浚毫鬻嚣褰馥羧熬繁黼。霪蜜蒸瓣瓣囊瀚麓枣， 锄蕊，薄枫塑占糖馘瀵羹聱些，警然，嘏鬻鞭多调瘦髑麟熬藕予确遵型鞠稠缝。 辩予禳雾滋舔簿藤，漆予箕随瓿霹索麟跨静逡黧箍夺，黼赭藏 | j 褥菇髓鬣麟瓣霪 粼黻翘趱采遴姆涨瓣，速鼯蚕蔽鼹燃熬寮卡静方麓，黼鼹褥载瓣绩暴巍躐渡耱 瓣；瀑器潲爨蜜麟熬蘩震； 躐壤产需求每鬻，磷黻黪为投骜簿脊勰辫、耩黎艇稳芋爨鞲秽釜躺搿赦率润嘞霸 黥静静添凄裙需豢慧剩蘑窬穗菇瞪镧瓣瓣瓣攀霹c 孙学醚器酾灏灞度瓣蘧。 统话粼糕鼹添，搬夸大黪麟静乏憋虚鹰蔬麟l 鸭毽耩趣王劁髓，攥装。鼹舞爨麟嚣患 蕊蹙蓑囊恭蕊露蕊瀵漆鬻囊醭簿褰蠛瓣，蠢攀麟瀵蕊瀵蹙黪燕一蕊爨鎏瓣溱露鬓囊瓣霪瑟 露譬霎瓣燮黼藏攒静德。辫疯瓷器瓣躲黼鼙孛魏黻酝e 零黼桶疆雒、貔t o t a lf | o w - t l 辫瓣 髹豹尧游德瀵塞诿壤溺邃。 l ，l 。3 瀵攫游霪熬零瓣簿潼 袋麟瞄蕊褥蘧舔嚣滏邈瓣努辫嚣黧，一囊穗黼溅落潦，一粪畿爨德惩薄滋* i 髓缀寨勰方疆 最德稳绺潦瓣藏嚣鼗攀z 蕊帮缝德潼矧浚，渤藩蕊潮法，拣稿鞠霹乘予港、静藏灌爨 蘧漆。纛童遴熊法枣。线魅麟粼瀵舔懿毒窿黪蛾黪；寒梅邂燮蠛娥黪糠惑撩张鳃策燕髅纛 辩懑缝稔羲港蕊藏躐麓虿喾蕊。黪妻激冀液程瀵产疆霪蠛邀爨一啼露霪辩蕤穗簿潦* 霪 蓥 第1 章绪论 的效率与众多因素密切相关，如：搜索树的空间结构、定界方法和剪枝规则等。如果能合 理设计这些因素，可将其用于中小规模调度闻题精确求解。然纛，由于调度趣题是个典 型的n p 难问题，最优求解方法只能解决一些中小规模问题，对于大规模问题要想快速得到 鑫凄量可行解就要采用近戗最优解求解方法。 ( 2 ) 近似最优解求解方法 霉 l 蓍对调度问题零耀懿近议最优然求解方法主要可戳分为嚣类：嬲发式方法( h e u r i s t i c s ) 和元启发式方法( m e t a - h e u r i s t i c s ) 。 窟发式算法是针对一个特定氡遂斡性质穰目标蚕数，建用或设计有效酶诱度撬嬲来获 取近似最优解。较典烈的启发式算法有基于作业优先级的p a l m e r i “】算法、c d s 1 2 】算法、 g u p t a 1 翊算法、r c 1 4 1 算法、b 嚣算法1 习和基于经务插入酶n e 西1 妨算法。 元启发式算法不像启发式算法那样依赖于具体问题的特性，而是种能够用于求解多 种阊题的方法。目前常用的元启发式算法包括遗传算法f 1 飞g a ) 、模拟退火算法疆联s a ) 、禁 忌搜索算法f 1 9 】( t s ) 、蚁群算法【2 川( a c a ) 、粒子群优化算法口1 1 ( p s o ) 和人工神经网络口1 ( 姗 等，不阎的算法各有优势，被广泛地应用在各种领域中。本节将对神经网络算法的基本概 念进行简要的余绍。 神经网络优化算法作为一种元启发式算法，具有智能性、高容错性、便于硬件实现、高 速并行处理数据等优点闭，近笨来受到众多学翥熬关注。人工辛枣经网络的砑究是以生物享孛经 元学说为基础的。生物神经元学说认为，神经细胞即神经元是神经系统中独囊的营养和功 能攀元。生物神经系统包括中枢神经系统襄大脑，均怒由各类襻经元组成。生物神经元豹 结构大致描述如图1 1 所示。 凰1 - 1 生物神经元结构 神经元由细胞体和延伸部分的突触组成，突触根据形态缩构和功能的不同，可分为树 突和轴突。树突占延伸部分的犬多数，用来接受来自其它神经元的僚息；轴突用来传递帮 输出信息。单个神经元通过树突可以接受多达上千神经元的输入信息，通过轴突将加工后 的信息发送给其它神经元。一个神经元接受的信息，在时间和空间上常呈现璐一种复杂多 变的形式，需要神经元对它们进行积累_ 和整合加工，从而决定其输出的耐机和强度正是 3 东南大学硕士学位论文 神经元这种整含作用，才使得亿万个神经元在神经系统中有条不紊、夜以继日地处理各种 复杂的信息，执行着生物中枢季申经系统鳇各种信息处理功能。 经过对生物神经元的长期广泛研究，1 9 4 3 年美国心理学家m c c u l l o c hw 和数学逻辑学 家p i t t sw 根据生物毒枣经元生物瞧和生物化学魏运行机理提出神经元鳃数学模型，朗蓑名鲍 m p 模型。图l 一2 给出m p 模型的示意结构。 x l x 2 迤 鹜1 - 2m p 稷垄 神经元i 接受k 个其它神经元j ( i l ，2 ，妁的输入信号x j ，神经元j 对神经元i 的影响大 小用杈值i i 来表示。神经元i 通过某种运算给出所有输入的总效果，称为“净输入”或“激 活值”，以y i 来表示。计算挣输入的运算可以根据所求问题盼不同采用不同的方法，最常 见的为线性加权求和，解y l = t o i , j x j + i i ，其中i i 称为神经元i 的“偏执输入值”或“闲值”， 是神经元i 调整净输入大小的参数。最后将神经元的净输入作为函数f 酶输入值计算神经元 的输出值，函数f 称为“传输函数”或“输出函数”，最常见的函数为符号函数s g n ，即 f l ， y l 0 施= s g n ( y t ) = m y i = 0 t - 1 ，y l 0 目前用于解决调度问题的神经网络有h o p f i e l d 网络 2 2 1 、b p 网络渊和竞争网络渊。其 中，b p 鼹络用予调度阻题一般是通过学习采集到的一组数据，挖掘调度问题的规则，为后 面的调度问题提供指导。h o p f i e l d 网络和竞争网可以赢接用予求解调度优化问题。 1 9 8 2 年，美国加州理工学院物理学家 | o 两e l d 【2 5 】提出了一种h o p f i e l d 神经阙络( h o p f i e l d n e u r a ln e t w o r k ， i n m ，由于引入了“能量函数”的概念，使得网络稳定性研究有了明确的 判据。h n n 熬电子电路物理实现阳为神经计算规的 舞究奠定了基础，并将其应用于疆翦电 子计算机尚难解决的计算复杂度为n p 完全问题，例如著名的“巡回推销员问题”( 2 7 1 1 2 8 l ( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，取褥了很好懿效果。盈然h n n 的硬件电路网络筢 够瞬间输出所求问题的结果，但是h n n 容易陷入局部极小值点，为了避免这个缺点在随后 死年学者稍对h o p f i e l d 模型健输函数串辱l 入随机因子，提出了b o l t z m a n n 橇 2 9 1 、g a u s s i a n 机p 们、c a u e h y 机【3 1 】和c s a 模烈【3 2 1 ，大大提高了基于h o p f i e l d 模型的神经网络求解优化问 题的能力，其中目前文献中研究最多的为c s a 模型。 竞争网与h o p f i e l d 网络的主要区别在于它采用竞争学习算法：对于神经元i 的n 个输入 4 第l 章绪论 值 y l , y 2 ，矾) 中，根据具体问题的需要选取满足一定条件的1 个或k 个输入值( k n ) 作 为获胜者使用，忽略其它输入值。选取获胜者的规则可以根据所求阀题的不同丽有所变化， 最常见的规则是选取n 个输入值中的最大或最小值作为获胜者。 最近，s a a d a t m 秘t a r z j a n 等在f i n n 翻竞争嘲酶基础上提出一穗梅造优化嬲络模型 ( c o n s t r u c t i v e o p t i m i z e rn e u r a ln e t w o r k ，c 饼呵n ) 脚j 用于求解t s p 问题。c o n n 结构上 采用类似子h o p f i e l d 鼹绔漠型憋反馈式瓣终续构，在学习算法上采周类戳于k o h o n e n 窘组 织映射( k o h o n e n - t y p es e l f - o r g a n i z i n gm a p s ，k - s o m s ) 3 4 1 的竞争学习算法。由于采用竞争 学习鼙法阁，虽c 烈n 毒戳在优纯和构造扩震嚣种状态闷甥换，所以c o n n 熊够快速得到 高质量近似最优解。 神经网络算法通过将所求淘题魏数据j 稻计算分布戮网络中的神经元上，具有高速并行 和抗噪声数据干扰等特点，能够更好的满足实际应用系统中对于算法所要求的实时性和健 壮性要求，所以基予神经网络的调度算法已经成为调度算法研究的一个重要分支。 1 2 无等待流水调度问题 流水车阗调度是搬：n 个工件要在m 台帆器上进行加工，工件使用极器的顺序是摆丽 的，考虑怎样安排加i 顺序，使得按照该顺序加工，某一个或多个目标函数达到最优或近 织最优。如采蘩求每一个工件在第一台机器上嚣始加工惹，不麓断使耀枧器完成所有加工， 这就是无等待流水调度。无等待流水调度是最重要的一类调度问题，其中最常用的两个优 纯謇标力：最小纯最大完工露阀( m a k e s p a n ) 饔最小化慧完王跨阉( t o t a lf l o w - t i m e ) 。 t o t a lf l o w - t i m e 最小促使资源稳定有效地利用、任务的快速周转及在制品库存最小；而 m a k e s p a n 最小纯能减少总的黛产周转时间，这些都怒目前现代集成铡造系统c i m s 、计算 机系统和其它一些信息系统所关心的一些问题。 1 2 1 无等待流水调度问题简介 无等待流水调度作为最重娶静一类调度问题，广泛应用予化工阐、食品湖、药晶耠翅等 各种工业加工环境中。作为流水车间( f l o w - s h o p ) 调度问题中的一种，无等待流水车间 ( n o - w a i tf l o w - s h o p ) 调度问题般情况下满慰以下凡项假设条件： 一个工件不能同时在不同的机器上加工； 在加工过程中采取平行移动方式，即强上一道工序完工后，囊即送下道工序加工； 不允许中断，当一个工件在台机器上一旦开始加工，必须一直进行到完工，不 允许中途停下来，插入其它工件； 每道工序其在一台枫器上完成，每台枫器只完成一遂工序； 工件数、机器数、加工时间融知，且加工时间与加工顺序无关； 不允许加工王件在工序之阀等特，兔许貔器经工箨泰爨达对闲置； 工件加工技术上的约束事先给定； 一 每台机器同时只能加工一个工件。 5 东南大学硕士学位论文 设n 个工件为o l ，j 2 ，n ) ，一个可行调度序歹f j 为t t = h ，嘞，) ，m 为机 器数，为第i 个工件在第j 个机器上的加工时阀，t f t 为所有工件的t o t a lf l o w - t i m e ，m s 为 工作序列的m a k e s p a n 。由于存在无等待的限制，第i 个工件与随后的第j 个工件在第一台机 器上秀始加工的最小对闯差值d l j 0 。对于2 个工俘2 台枧器的n o - w a i tf l o w - s h o p 闻遂，当 t j l t i 2 时，加工情况如图i - 3 中a 所示，t j l t i 2 8 t j l t i 2 当t 扭 t | 2 时，总的加i 时间为： ”r = 2 t i x + t 1 2 + t j l + 白2 热工序列的m a k e s p a n ： m s = m a x ( l l 十f 1 2 ，t n + 勺1 + 勺2 ) 当t l t 对予待求酶阕惩，选择一静合适的表示方法，将神经网络的输出与阉题酶解对应 起来； c 麓构造棒经元网络酶裁量函数，使其最夸值对应于闳惩的最佳解； ( 3 ) 根据式2 5 求出神经元之间的连接权值矩阵和阈值向量i ； ( 4 ) 初始亿h o p f i e l d 神经网络参数，随机产生初始状态值y 或输出值x ，令h o p f i e l d 网络运行，最后稳定状态下的输出就是要求解问题的结果。 2 1 2 2 最小化m a k e s p a n 问题的能量函数 2 2 为了将以m a k e s p a n 为目标的调度问题映射到h n n 网络上，需要构造所求问题对应的 2 3能量嚼数，通过一种含适酶方法将神经元毽与调度序歹g 对应起来。设h n n 网络有1 1 2 个享枣 2 4 经元，每个神经元的输出值为逻辑值0 或l ，输出值x i 一1 袭示工件i 位于调度序列的第j 2 s个位嚣，剐对于一个惫含4 个芏律盼加工序列4 - 1 _ 2 3 酉跣霹一个包会1 6 个神经元 2 6 的h n n 神经元输出值x 表示： f 0 薹00 1 x - l o 0 00 1o l 【王00o j 2 7但是并不是矩阵x 的所有可能值都能给出对应的序列，例如： 2 8 罴魄，2 = x i 。3 = l 对，第1 个工捧应该在序列的第2 和第3 个位篷加工2 次，这与无等 2 9待流水调度问题要求每个工件1 次性完成加工相矛盾；当x 2 1 = x 3 1 = 1 时，要求在第2 个 3 0 和第3 个工锋同时歼始在筹台机器土麓王，这与一台撬器在某一黠刻只熊旋工一个工件 3 1相矛黯。为了保证m 斛对应的矩阵x 是一个满足无等待流水调度约束条件的可行序列， 3 2必须满足： 1 2 l 2 3 4 5 s 7 8 9 l 昱 n 心 b 搭 插 努 鸲 蟾 加 s 6 7 1 6 王7 1 8 1 9 第2 章基于h n n 的调度算法 ( 1 ) x 的每行有且仅有1 个元素为i ，其它都为0 ； ( 2 ) x 的每一列有且仅有1 个元素为l ，其它都为0 ； 其中约束条件( 1 ) 保证每个工件在序列中仅出现次，即一个工件开始加工后一次性 完成所有加工，霹以用以下约束条件表示： 孑 锄一l ；= o 约束条件( 2 ) 保证序列中一个位置仪安排一个工件，即不容许多个r 件同时开始加工， 可以用以下约束条件表示： m 1 ) 烫l 以m a k e s p a n 为鬻标丞数鲍调度阕题可表述为如下酶约束优纯阏题： 徽纨= 憨锄+ l 呶+ 奄蟊讯 ( 2 l 母 舭( 锄1 一o ( 2 7 ) ( 矿1 ) 一o ( z - 8 ) 其中c m 。x 表示n 个工件m 台机器对应加工序列的目标函数值m a k e s p a n ，d i i 表示两相邻 工箨在第一台机器上开始加工鹣最小时褥差，专稚表示z 俘i 在桃器j 上静加工瓣闻。如柒誊 l 经元值能够满足式( 2 7 ) 、( 2 8 ) ，则待加工工件与序列中的位置存在一一对应的关系，网 络盼神经元值确定了一个可行翱工序列。如果神经元值不能满足式( 2 7 ) 或式( 2 s ，剐 个加正工件被安排在加工序列的多个位置或加工序列中某个位置安排有多个工件，不满 足无等待流水调度约柬条件，随络酶神经元值确定了一个不可行加工茅魂。 为了简化阀题的表达，引入一个虚拟加工工件记为n + l ，该虚拟工件在所有机器上的加 c 孰积= zzz x , ，张，+ ，蠢睡 ( 2 。9 ) 翮用惩罚溺数法，将约束优纯闻题转换为无约束优纯闻题麓 善= 五( 薹薹薹藏j 锄+ 菇靶、+ 屯薯( 芝j = 1 麓一王) 2 + 屯薯( 薹鼍。一l 、) 2 善= 五藏j 锄嘏靶卜妒王卜t s 丢( 矿1 ) t = l ，= 1 l l c = lf = 1 ，j = l 、l = l 戆爨委数e 取最小僖时h n n 霹终襻经元输出僮x 确定7 对瘟最小化m a k e s p a n 蛾遂的 最优加工序列。然而，由于相邻工件在第一台机器上开始加工的最小时间差对应的距离矩 阵d 不一定炎对称阵，所以上箴的麓燕遗数对应的h o p f i e l d 蹒络不麓保证收敛。秀7 解决 n觚 8 9 如缝技终铒岱 1 东南大学硕士学位论文 对称性，考虑将目标函数c 毗x 的表达式变形： n + l 魂脚瓶 k 1 n ，i + l j = z k = l 2 能量函数变为： x l , j x k j + l d i k + k = l j = 2i = 1 n + l7 ln + l e = 2 1 ( m 锄砒+ 、l = 1j = zk = l 峨( 锄 j = l 、i = 1 n + 1n7 i + l = 丸o 一1 ) 2 n + 1 l l x i j d k ij 。 n + l n+lj=2i = 1 j 一，旎j d 艇、1 + a ：薯( 艺j = l 写“一1 、) 2 坼蛳妃) 怕( 锄一1 ) f = 1 “撕o + 1 d 诬+ x k , j 一1 x i j d k i ) + 3 1 n + 1n + 1n + 1 n + l 帆萎罗x k j _ i x i j d k tjrizl j = n + li = 1i = 1 ( 七=、 n + 1 n + 1 怕( m j = 1 t = l 3变形为 4或 f = n + l t l + 1 n + 1 n + 1 z t 一2 薹x t j + 1 ) t i + l n + 11n + 1 y y y z 二一二jz _ j ( 国+ 1 1 x i , j x k 1 d i k + 吩一1 1 x j x k ，t d k f ) x i j x k , j + i d i k n + ln + l n + l n + 1 占j+z,lxl,j础+九国-1,1xlixl,jxk i x l j x k ，l d k i i c f f 七+ 九乞乙艺2 国 ， j = n + li = ik = l1 = 1 + h t 2 1j 2 1 _ i c 2 1z 2 1 n + l n + l n + l n + l + 3 - 3 1 2 1j 2 1r 2 1f - 1 n + l n + 1 n + 1 n + l 恐棚 - ( 2 ；【2 + 2 a 3 ) n + 1 ，i + 1 m z 一2 屯 t l + 17 l + 1 n + l 锄+ 屯 i = 1 7 1 + 1 毋，z x t ，z k z 一2 a 。x t ，+ a s f = 1j = t 1 ) 1 ) 0 1 国+ l z d i k + a 1 国一l ，l d k i + a 2 盈七+ a 3 屯f ) ，i + 1 n + 1 x i , ， f = 1j = x + ( 如+ a 3 ) ( n + 1 ) 1 4 ( z 1 0 ) 七 d ， f x l一 ， k m一僦芝揣互譬气k n 他 叭妞 = 甜 叭池 1 2 眦 、l， 1+ l x 叭闩 ，_ m 吒 司 j ， “ 敏 扫m闩 砘 一 m m胁m 心 h = e m 第2 章基于h n n 的调度算法 1 其中 嘶= 皓。五黧 ( 2 1 1 ) 2 对比式2 1 0 与2 2 ，神经元之间的连接权值可由下式求得 o ) 0 ，埘= 一z ；【1 国+ 1 t d l k 一2 a 1 国一i ，l d k i 一2 a 2 盈 一2 如国1 ( 2 z 2 ) 3 神经元的阈值可由下式求得 = 2 a 2 + 2 2 3 ( z 1 3 ) 42 3 最小化t o t a lf l o w - t i m e 问题的能量函数 5 类似于求解最小化m a k e s p a n 问题，为了将以t o t a lf l o w - t i m e 为目标的调度问题映射到 6 m 州网络上，设m 州网络有n 2 个神经元，每个神经元的输出值为逻辑值0 或i ，输出值 7 x 的= 1 表示工件i 位于调度序列的第j 个位置，则以t o t a lf l o w - t i m e 为目标函数的调度问题 8 可表述为如下的约束优化问题： nn - 1nil r t t 砌丁刀= m 卅旎j x k , j d 七+ ( 2 - 1 4 ) 1 6 1 7 1 8 舭萎嬉矿1 ) _ 0 c z 均 ( 锄一1 ) = o ( 2 1 6 ) 其中t f t 表示n 个i 件m 台机器对应加工序列的t o t a lf l o w - t i m e ，d i l 表示两相邻工件 在第一台机器上开始加工的最小时间差，t i i 表示工件i 在机器j 上的加工时间。约束条件2 1 5 和2 1 6 保证了每个工件都位于序列的某一个位置，且加工序列的每一个位置有且仅有一个 i 件。无等待约束条件i 丰l d i i 的计算公式保证。 注意到1 1 叮表达式的最后一项为常数，是所有工件的总加工时间之和，所以在考虑优 化问题中仅需要考虑前面部分的优化。利用惩罚函数法，将约束优化问题转换为无约束优 化问题为 f = a 。【、t 善nn-1nj=lk = l c n 一。x “z k ，+ ，d 讹、+ a ：芝i = 1 ( 薹z “一1 、2 f = a 。( ( n d x “z k ，+ ，d 讹) + a z ( z “一1 ) l = l= 1 眠( 锄一1 ) 同样，由于相邻工件在第一台机器上开始加工的最小时间差对应的距离矩阵d 不一定 为对称阵，所以上式的能量函数对应的h o p f i e l d 网络不能保证收敛。为了解决收敛性，类 似于求解最小化m a k e s p a n 问题，最小化t o t a lf l o w - t i m e 问题采用如下能量函数： 1 5 9 n 控 坞 m 坫 东南大学硕士学位论文 f 一锄，t ( m 一力 国+ l l d 挑+ 一歹+ 1 ) a ，国一“故；+ 2 z s ；k + a 。吩。) t = l j 。l k = 1 1 = 1 一( 2 如+ 2 哟+ 魄+ 南) 魏 ( 2 。1 7 ) l = 1 j = l l 故对应的h o p f i e l d 阙络神经元之闻鳇连接投值可由下式求得 2 “，触2 2 ( n j ) ；h a j + 1 1 d 班一2 ( n 一，+ i ) l l a j 一1 1 d h 一2 a 2 8 i 缸一2 2 3 屯l ( 2 1 8 ) 3 ，h o p f i e l d 雕络神经元的阚傻可由下式求得 = 2 屯+ 2 毛( 2 1 9 ) 4 2 4c s a 算法数学模型 5 由予h n n 采用翦梯度下降算法容笏使网络陷入局部最小缀，大约在h o p f i e l d 和t a n k h 】 6 发表文章三年后，w i l s o n 和p a w l c y 明发表文章对h n n 模型用于解决优化问题提出严重质 7 疑。针对h n n 容易陷入局部最小值静问题，受模拟遐火法( s a ) 酶启发，通过向耨l 经隧 8 络的权值矩阵、阈值向量或传输函数加入随机因子，许多h n n 的改进模型被提出来，如 9 b o l t z m a n n 机瑟n ，c a u c h y 机p h 、g a u s s i a n 机p o 和c s a 3 2 双j 络模型，其中c s a 算法在解决 1 0 h n n 极小值问题方面性能最好。c s a 求解优化问题的数学学模型p 2 1 为： ， 计+ 1 = 肼+ 声秽叫埘似一j 0 ) 傅2 0 ) j # + 1 = ，”1 ) 2 再砑辆( 2 2 1 ) l l 1 2 终 1 4 1 5 l s 1 7 1 8 矿+ 1 = ( 1 一a ) z 露( 2 2 2 ) 其q 3 x i , y i ，i i , 分别表示享孛经元i 鲶输出、内部输入释阈蕴；￥，参为控翱网络学霹速度麓 参数，6 为控制神经元自反馈输入大小的退火参数，调整这三个参数可以影响i i ) 4 络收敛速度 戮及解盼质量；t 为控制传输藩数形状的参数；为隧时阕增大焉趋向子零的正数；铺l 茺 神经元j 到神经元i 的连接权，可由下式求得 吨，矽+ ，f = 一瓦o e ，“ f - 1 2 ，7 l ( 2 - 2 3 ) 狰， 其中e 是神经网络对应的能量函数。可以看出，c s a 神经网络模型是扩展的h n n 神 经阙终模型，随着鲤终隧运行z 耙一0 ，最终c s a 变为h n n 苁蠢按照h n n 的演化过程稳定 在某个近似最优解对应的稳定状态。因此，将h n n 算法改为c s a 算法时神经元之间的连 接权值矩阵帮阙僖向鬣不交，算法流程与h n n 算法类似。 1 92 5 改进的c s a 算法模型 c s a 通过弓l 入自反馈因子，使得神经元的值在开始的一段时间内能够在一个逐渐缩小 1 6 第2 章基于i - i n n 的调度算法 1 的范围内震荡，进入混沌状态，从而具有一定跳出局部极小点的能力。王立波船1 研究了神 2 经元的阈值大小对c s a 混沌现象的影响后指出：神经元取不同的阈值会引起对应的c s a 3 搜索范围的不同，从而对c s a 发现最优解的能力有较大影响。对于本文求解m a k e s p a n 问 4题和t o t a lf l o w - t i m e 问题而言，从式2 1 3 和式2 1 9 可以看出h n n 算法和c s a 算法中神 5 经元的阈值都为2 k + 2 b ，然而实验验证发现，当神经元的阈值取区间+ b ，3 k + 3 x 3 】 6 内的任意值时c s a 都能稳定收敛到某个近似最优解。为了扩大神经元的搜索范围，从而进 7 一步提高c s a 算法的优化能力，考虑采用阢+ b ，3 k + 3 b 】区间内的不同值作为神经元的 8 阈值，同时对该阈值增加一个随时间变化逐渐减小的随机变量，这样就得到一种可改变阈 9 值的c s a 算法，即v t c s a ( v a r i a b l et h r e s h o l dc h a o t i cs i m u l a t e da n n e a l i n g ) 算法，v t c s a 1 0 的数学模型如下： 、 硝+ 1 = 肼邯( 毗，秽+ 卟一j o ) ( z z 4 ) j 站+ 1 = 厂”1 ) 2 百獗啊( 2 2 5 ) z 七+ 1 = ( 1 8 ) z 七( 2 2 6 ) 胳+ 1 = , + z 1( z 2 7 ) 1 1 其中x “y t ，i i , 分别表示神经元i 的输出、净输入和阈值；y ，p 为控制网络学习速度的参 1 2 数，6 为控制神经元自反馈输入大小的退火参数，调整这三个参数可以影响网络收敛速度以 1 3 及解的质量：t 为控制传输函数形状的参数；z 血为随时间增大而趋向于零的正数；i i ( 为神经 1 4 元的阈值；i ：，为阈值的初始值；i ，j 为神经元j 到神经元i 的连接权，可由式2 2 3 求得。 1 52 6 变化阈值的c s a 算法描述 1 6v t c s a 与c s a 不同之处在于采用了动态变化的阈值从而扩大了算法的搜索空间，算 1 7 法实现考虑将区间【k + b ，3 x 2 + 3 x 3 】等分为1 0 段取1 0 个端点处的值作为1 0 个不同的初始 1 8 阈值，分别用这l o 个初始阈值对应的