（计算机应用技术专业论文）基于自适应差分进化算法的生产调度方法研究与实现.pdf

d i 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：1 瓦犯丧 日期：加净厂月w 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密留，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“、”) 作者签名：1 及似兹 日期：如毋j 月那日 导师签名乏少万厶，日期：锄哆年厂月儿日 浙江工业大学硕士学位论文 基于自适应差分进化算法的生产调度方法研究与实现 摘要 生产调度问题通常具有强约束、n p h a r d 、多目标、随机不确定等特征，是非常复杂的 问题。调度理论和高效算法的研究一直是学术界和工业界的热点课题。差分进化算法 ( d i f f e r e n t i a le v o l u t i o n , d e ) 作为一种新兴的群体智能优化算法，因其具有较强的全局寻优能 力和较快的寻优速率，逐渐成为研究的热点。本文围绕着d e 在生产调度中的应用展开了 相关的研究。论文的主要工作归纳如下： 1 针对基本d e 易陷入局部收敛这一缺陷，提出了一种改进的d e ( s e l f - a d a p t i v e d i f f e r e n t i a le v o l u t i o n ，s d d 。在s d e 中，首先，对算法参数进行混沌优化，并根据种群个 体适应度的优劣自适应地调整个体的缩放因子和交叉概率，有效地平衡了算法的局部与全 局搜索能力；其次，通过改进d e 的交叉和选择操作，增加了种群的多样性，提高算法的 全局收敛能力。 2 针对置换f l o ws h o p 和j o bs h o p 调度问题，探讨了s d e 在p f s p 和j s p 求解中的 应用。建立了以最小化m a k e s p a n 为目标的p f s p 和j s p 模型，并采用l o v 规则实现从d e 个体到加工排序的映射。通过对典型算例的仿真计算和分析比较，验证了s d e 在求解p f s p 和j s p 中的可行性和有效性。 3 针对带有限中间存储的流程工业生产调度问题，采用基于统一时间离散化的时间 表示方法，建立了以产值最大为目标，包含生产工艺、物料平衡、设备生产能力、贮槽容 量和供求等多种约束的车间调度模型，给出了求解该模型的s d e 。并结合具体的工程实际， 将其应用于隔膜烧碱车间生产调度问题的建模和求解中。通过计算分析了时间段长度大小 和贮槽初始容量对调度结果的影响。计算结果验证了该调度模型和调度算法的可行性和有 效性。 4 在上述理论工作的基础上，结合企业实际生产情况，将理论应用于工程，设计并 实现了化工企业车间智能调度系统。 浙江工业大学硕士学位论文 最后，对论文的研究工作进行总结，展望了差分进化算法和生产调度理论研究和应用 的前景。 关键词：差分进化，生产调度，置换f l o ws h o p 调度，j o bs h o p 调度，流程工业 浙江工业大学硕士学位论文 r e s e a r c ha n di m p l e m e n to fp r o d u c t s c h e d u l i n gm e t h o db a s e do na d a p t i v e d i f f e r e n t i a le v o l u t i o n 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 gp r o b l e mi sav e r yc o m p l e xi s s u e ，o f t e n 晰t 1 1t h ec h a r a c t e r i s t i c so f s t r o n gc o n s t r a i n t ，n p - h a r d ，m u l t i - o b j e c t i v ea n du r i c 眦t h es t u d yo ns c h e d u l i n gt h e o r ya n d e f f i c i e n ta l g o r i t h m sh a sb e e nah o tt o p i cb o 也i na c a d e m i ca n de n g i n e e r i n gf i e l d s a san e w p o p u l a t i o n - b a s e di n t e l l i g e n to p t i m i z a t i o na l g o r i t h m , b e c a u s eo fi t sg o o dg l o b a ls e a r c ha n dq u i c k c o n v e r g e n c ea b i l i t y , d i f f e r e n t i a le v o l u t i o n h a sg r a d u a l l yb e c o m ea r e s e a r c hh o t s p o t t h i s p a p e rf o c u s e so l lt h ed e sa p p l i c a t i o nt op r o d u c t i o ns c h e d u l i n gp r o b l e m s m a i nw o r k so ft h i s p a p e r 羽f es u m m a r i z e d 勰f o l l o w s 1 s i n c et h eb a s i cd ei sv u l n e r a b l et ob et r a p p e di nal o c a lo p t i m u m ，as e l f - a d a p t i v ed e ( s d e ) i sp r o p o s e d f i r s t l y , f o rt h es a k eo fb a l a n c i n gt h eg l o b a ls e a r c ha b i l i t ya n dl o c a ls e a r c h a b i l i t yo fd e ，c h a o st h e o r yi su s e dt oo p t i m i z et h ep a r a m e t e r sa n das e l f - a d a p t i v ep a r a m e t e r s e t t i n gs t r a t e g ya c c o r d i n gt oi n d i v i d u a l sf i t n e s si sa d o p t e d s c c o n d l y t oi n c r e a s et h ed i v e r s i t yo f p o p u l a t i o na n de n h a n c eg l o b a lc o n v e r g e n c ea b i l i t yo fa l g o r i t h m , t h ec r o s s o v e ra n ds e l e c t i o n o p e r a t o ro fd ea r em o d i f i e d 2 f o rp e r m u t a t i o nf l o ws h o pa n dj o bs h o ps c h e d u l i n gp r o b l e m s ，s d ei su s e dt os o l v i n g t h ep f s pa n dj s pw i 廿lt h em a k e s p a nc r i t e r i o n 1 f 1 1 el o vr u l eh a sb e e na d o p t e dt oc o n v e r td e s i n d i v i d u a lt oj o bp e r m u t a t i o n s i m u l a t i o n sa n dc o m p a r i s o n sb a s e do nb e n c h m a r k sd e m o n s t r a t e t h ee f f e c t i v e n e s sa n de f f i c i e n c yo ft h es d e 3 a st op r o d u c t i o ns c h e d u l i n gi np r o c e s si n d u s t r i e sw i t hf i n i t ei n t e r m e d i a t es t o r a g e ，a m o d e lf o rt h i sp r o b l e mi sf o r m u l a t e d 1 1 1 em o d e lt a k e ss e v e r a lc o n s t r a i n t si n t oc o n s i d e r a t i o n ， s u c ha sp r o d u c t i o np r o c e s s ，m a t e r i a lb a l a n c e ，e q u i p m e n tc a p a c i t y , r e s e r v o i rr e s e r v e sa n ds oo n t h eu n i f 0 1 t 1 1t i m ed i s c r e t i z a t i o nm o d e li su s e dt o e x p r e s st h et i m e t h e n , ad ea l g o r i t h m p r o p o s e dt os o l v et h i sc o n s t r a i n e do p t i m i z a t i o np r o b l e m s a tl a s t ，a c c o r d i n gt ot h ee n g i n e e r i n g p r a c t i c e ，t h em o d e la n da l g o r i t h ma r eu s e dt os o l v ed i a p h r a g mc a u s t i cs o d ap l a n tp r o d u c t i o n s c h e d u l i n gp r o b l e ma n da l la n a l y s i so ft h ea f f e c t sb yt i m ep e r i o dl e n g t ha n di n i t i a lr e s e r v e so n i i i 浙江工业大学硕士学位论文 t h es c h e d u l er e s u l ta r ep r e s e n t e d t h er e s u l t ss h o wt h e f e a s i b i l i t ya n de f f e c t i v e n e s so ft h e p r o p o s e dm o d e la n da l g o r i t h m 4 b a s e do nt h ea c a d e m i cr e s e a r c ha b o v e ，c o m b i n e dw i t ht h er e a lc o n d i t i o no f e n t e r p r i s e s ，a c h e m i c a lp l a n ts c h e d u l i n gs y s t e mi sd e v e l o p e d f i n a l l y , as u m m a r y i sm a d ea n ds o m ef u t u r ew o r k sa r ep r e s e n t e d k e yw o r d s ：d i f f e r e n t i a le v o l u t i o n , p r o d u c t i o ns c h e d u l i n g , p e r m u t a t i o nf l o ws h o p s c h e d u l e ，j o bs h o ps c h e d u l e ，p r o c e s si n d u s t r y 浙江工业大学硕士学位论文 摘要 第1 章绪论 1 1 1 2 1 3 1 4 第2 章 2 1 2 2 2 3 2 4 2 5 第3 章 3 1 3 2 3 3 目录 选题目的及意义l 生产调度问题2 1 2 1生产调度问题描述2 1 2 2 生产调度问题的分类3 l 。2 3 生产调度问题的研究现状与方法4 1 2 4 存在的不足与发展方向。8 差分进化算法的研究和应用现状9 1 3 1d e 的研究现状9 1 3 2 d e 的应用现状l o 论文的章节安排1 l 自适应差分进化算法 1 3 ：；i 言1 3 基本差分进化算法1 3 2 2 1算法流程1 3 2 2 2 差分进化算法的参数一16 自适应差分进化算法1 7 2 3 1 自适应的参数调整策略一1 7 2 3 2 改进的交叉和选择操作l8 2 3 3 s d e 的算法流程19 2 3 4 算法复杂度分析2 0 仿真结果与分析2 1 2 4 1 测试函数。2 1 2 4 2 实验设置2 2 2 4 3 d e 参数对性能影响的分析2 2 2 4 4 s d e 与d e 的性能比较2 4 d 、l ! i ；2 6 基于s d e 的置换f l o ws h o p 调度方法研究2 8 引言2 8 问题描述与模型2 8 置换f l o ws h o p 调度的s d e 2 9 3 3 1编码设计2 9 3 3 2 初始化操作3 0 3 3 3进化操作31 浙江工业大学硕士学位论文 3 4 3 5 第4 章 4 1 4 2 4 3 4 4 4 5 第5 章 5 1 5 2 5 3 5 4 5 5 5 6 5 7 第6 章 6 1 6 2 6 3 3 3 4适应度函数3l 仿真与分析。3 l 3 4 1 实验设置3 2 3 4 2结果与分析3 2 ，j 、结3 5 基于s d e 的j o bs h o p 调度方法研究。3 6 弓i 言3 6 问题描述与模型3 6 j o bs h o p 调度的s d e 3 8 4 3 1 编码设计。3 8 4 3 2适应度函数3 9 仿真与分析4 0 4 4 1实验设j 4 0 4 4 2 结果与分析4 l d 、结4 3 基于s d e 的有限中间存储的流程工业生产调度研究。4 5 弓i 言4 5 问题描述4 6 带有限中间存储的流程工业调度模型4 7 5 3 1基于统一时闻离散化表示的时间划分4 7 5 3 2相关的变量定义。4 7 5 3 3 约束条件4 9 5 3 4目标函数。5 0 求解带有限中间存储的流程工业生产调度的s d e 5 0 5 4 1 编码设计与初始化5 0 5 4 2 非法个体的判断与修正5 l 5 4 3适应度函数5 2 5 4 4进化操作5 3 调度实例5 4 仿真计算与结果分析。5 5 5 6 1 时间长度二的影响分析5 5 5 6 2贮槽初始储量对调度结果的影响5 8 d 、结5 9 化工企业车间智能调度系统。6 0 弓l 言。6 0 系统总体设计6 0 6 2 1 需求分析6 0 6 2 2 数据库设计6 l 6 2 3系统框架6 2 系统和用户信息管理6 4 6 3 1用户登录。6 4 6 3 2用户注册6 4 6 3 3角色管理6 5 浙江工业大学硕士学位论文 6 4 6 5 6 6 第7 章 7 1 7 2 参考文献 致谢 基础信息管理模块6 6 6 4 1 设备信息管理6 6 6 4 2 产品需求管理6 7 车间智能调度模块6 8 6 5 1 日调度优化6 8 6 5 2 调度结果。6 9 叫、l 宥7 l 总结与展望 论文研究工作总结7 2 展望7 3 m 攻读学位期间参加的科研项目和成果 7 5 8 0 8 1 浙江工业大学硕士学位论文 第1 章绪论 1 1 选题目的及意义 如何将有限的资源通过合理的分配，使之得到充分的利用，一直是人类社会面临的一 个基本问题。这个问题贯穿于整个人类社会的发展进程中，体现在人类社会生活的各个方 面。特别是社会生产力快速发展、资源日益匮乏的今天，这个问题显得更加突出，引起人 们的广泛关注和研究。在制造生产领域，随着经济全球化的发展，市场竞争变得越来越激 烈，过去大批量、少品种的生产模式正在逐渐地被多品种、多元化、小批量、高柔性的生 产模式所替代，企业的生产复杂性也变得越来越高。因此，企业的管理和对生产过程的监 控变得更加复杂，单纯地靠原来简单的、常规的计划以及仅凭经验的排产，已经不能满足 现代生产的需要。如何提高企业对市场上原料供应和产品需求变化的应变能力，以及如何 降低生产过程受生产计划变化的影响，提高企业的综合经济效益，是当前企业管理者所面 临的一个具有挑战性的问题【1 1 。 随着计算机技术、信号处理技术、通讯技术、网络技术和自动控制技术的发展，在生 产控制中实现集控制、优化、调度、管理、经营于一体的综合自动化的新模式已成为可能。 e r p m e s p c s 是当前一种既简单又合理的模式。e r p 层强调的是企业的计划性。它以生 产能力、客户订单和市场需求为计划源头，力求充分利用企业内部的各种资源、降低库存、 提高企业的整体运作效率。p c s 则强调对设备的控制。通过控制优化，减少人为因素的影 响，提高产品的质量与系统的运行效率。而m e s 层是衔接e r p 和p c s 的枢纽，一方面，。 m e s 可以对来自e r p 软件的生产管理信息进行细化、分解，将来自计划层操作指令传递 给底层控制层；另一方面，m e s 可以采集设备、仪表的状态数据，以实时监控底层设备的 运行状态，再经过分析、计算与处理，从而方便、可靠地将控制系统与信息系统整合在一 起，并将生产状况及时反馈给计划层。由此，m e s 是整个生产控制实现综合自动化的关键。 而在m e s 诸多功能当中，生产调度是其中的主要功能之一，它是连接计划和生产的 关键活动，起着承上启下的作用。生产调度既是制约企业发展的瓶颈，也是提高企业竞争 力的关键所在。但是，目前在我国制造行业如纺织、汽车、机械、电子和化工行业中，缺 乏合理有效的生产调度系统的支撑，往往只能依靠技术工人的经验进行手工排产。由于这 浙江工业大学硕士学位论文 种排产方式的调度效率低、效果差、应变慢，严重地影响了企业生产周期的缩短、机器的 利用率的提高以及生产成本的降低，进而制约了企业生产管理水平和制造自动化水平的提 高，导致企业在激烈的市场竞争中处于不利的地位。因此，对生产调度方法进行研究和应 用有助于提高制造企业的市场竞争力。 除了具有较高的实际应用价值，对生产调度方法进行研究还具有重要的理论意义和学 术价值。生产调度问题是一类复杂的组合优化问题，已经被证明是n p 完全问题【2 】。自从 2 0 世纪5 0 年代，j o h n s o n 提出两台机器下的作业排序问题的求解算法【3 】开始，生产调度问 题受到了很多学者的关注和研究，给出了各种调度算法进行求解，如基于数学规划和基于 启发式方法的调度算法，取得了一定成果，但是调度效果还不能令人十分满意。近十几年 来，以遗传算法为代表的智能优化算法，因其算法本身具有较好的并行性，且不需要有很 多的问题领域相关的专业知识或启发式信息【4 1 ，并能在用户可接受的时间内获得用户较为 满意的调度结果，因而被广泛地应用于生产调度问题的求解中。 差分进化算法p e ) 是新近提出来的一种智能优化算法，因其具有较强的全局收敛能力 和鲁棒性，近年来，受到了广泛的关注和研究。目前已被广泛应用在参数估计、组合优化 等问题上，但其在生产调度问题中的应用研究却相对来说比较少。因此，d e 作为一种有 效和简单的并行搜索算法，对其进行理论研究和应用研究具有重要的理论和工程价值。 1 2生产调度问题 1 2 1 生产调度问题描述 生产调度问题一般可以描述为：针对某项可以分解的工作，在满足一定的约束条件( 如 工序约束，机器约束，资源约束等) 的前提下，通过某种方法安排其组成部分所占用的资 源、加工时间及先后顺序，以获得某种或多项生产指标的最优化，如产品制造时间、制造 成本或者总拖期时间等嗍【5 嗣。简单的说生产调度问题就是按时间分配资源来完成任务的问 题。在理论研究中，生产调度问题通常被看作是排序问题或资源分配问题。 由上面的描述可以看出，生产调度问题主要有以下几个部分( 要素) 组成【6 j ： 1 ) 调度对象：主要是指任务、设备( 加工设备、存贮设备、运输设备) 、原料、人力 等。任务是指被加工或处理的对象，往往是需要经过几个操作后才能完成。 2 ) 约束条件：一个可行的调度往往需要满足一些约束，包括工艺约束、产品的投产 期、加工时间、设备的加工能力、设备的可用性、批量的大小等一些必需满足的条件，也 包括一些达到一定的满意度即可的条件，如生产成本等。 浙江工业大学硕士学位论文 3 ) 调度的性能指标：这是衡量一个调度结果好坏的准则之一。常用的性能指标有：a ) 反映调度性能的指标，包括最大生产率、最短的生产周期以及最高的设备利用率等；b ) 反 映调度成本的指标，包括利润最大、成本最低和耗能最低等；c ) 反映客户满意度的指标， 包括最短延迟，以及最小提前或拖期惩罚等。在传统的调度中，一般以平均流通时间最小、 制造周期最短、满足交货期为调度目标，而在实际生产中，由于提前完成的产品必须保存 到交货期，而拖期产品必须交付违约金，因此，在实际调度中更加重视提前或者拖后惩罚 调度。 生产调度问题具有以下特点 z l 8 1 ： 1 ) 复杂性：由于生产因素的多样性和复杂性，在调度时往往需要考虑车间中工件的 工序约束、机器加工时间、准备时间等因素，使得其计算量随着问题规模的增大而急剧增 大。另外，调度问题是在等式或不等式的约束下优化某个或某些性能指标，其计算量往往 是非常大的。业已证明，调度问题是一类n p 问题【9 】【l o 】i l l 】。 2 ) 动态随机性：由于实际的生产中有很多随机和不确定性的因素，如工件到达时间 的不确定性，设备故障等，因而，调度应该能根据实际的生产情况进行动态的调整。 3 ) 多目标性：调度的性能指标往往综合考虑多个指标，甚至其中有些是相互冲突的。 1 2 2 生产调度问题的分类 由于大部分的调度问题都具有n p 难的复杂性，因而，将调度问题进行分类，有助于 对调度问题进行系统的研究。调度问题源于实际的生产制造领域，如化工、制药、半导体、 纺织等。但是，由于各个领域之间的生产制造或多或少地存在一些差异和不同，有些甚至 截然相反，从而导致在不同领域，甚至是不同企业的生产调度问题都存在较大的差异。因 此，研究调度问题的着眼点不同，对调度问题就会有不同的分类方式。 最常见的是根据车间环境来进行分类。可以分为【1 2 】【1 3 】：单机调度( s i n g l em a c h i n e ) 、并 行机调度( p a r a l l e lm a c h i n e s ) 、流水车间调度( f l o ws h o p ) 、柔性流水车间调度( f l e x i b l ef l o w s h o p ) 、作业车间调度( j o bs h o p ) d ：a 及开放车间调度( o p e ns h o p ) 等。单机调度问题是所有加 工任务只在一台机器上完成；而并行机调度是指有多台加工功能相同的机器，每个工件只 需在其中某一台上加工一次即可完成。f l o ws h o p 则是指有多个具有不同功能的加工机器， 每个任务均需经过相同的机器顺序在这些机器上加工完成。如果其中某个工序存在多台机 器可以加工，也就是说某个工序可以选择不同的机器进行加工，则是柔性流水车间。如果 每一个工件都有其特有的机器加工顺序，则是j o bs h o p 。如果工件在这些机器上的加工次 序是任意的，则是o p e ns h o p 。 浙江工业大学硕士学位论文 根据调度模型信息是否已知，又可将调度问题分为静态调度( 信息已知) 和动态调 度( 信息未知) 。静态调度是指在执行调度前，所有的任务的都处于待加工状态，在执行 调度后，各作业的加工被确定并在以后的加工过程中不能作任何的改变。反之，在执行调 度后，根据加工时出现的各种动态扰动，如新的任务的加入、任务的撤销、新机器的投入、 设备的损坏等，对调度进行动态的调整，获得更好的调度效果，这就是动态调度。 根据生产环境的特点，可以划分为确定性调度( 信息确定) 和不确定性调度( 信息不 确定) 。前者是指加工时间和其他的相关信息是已知确定的量；而后者的加工时间或相关 的信息在调度时是不确定的。 此外，常见的分类还有： 根据过程对象的时间尺度的不同，可以将调度问题分为离散过程调度、间歇过程调度、 连续过程调度和混杂系统调度。 根据相邻机器之间缓存不同可以分为：无等待甜o - w a i o 调度问题( 没有缓存，且工件 在完成上一道工序后，立即进行下一道工序的加工) 、阻塞( b l o 调度问题【1 4 1 ( 没有中 间缓存，工件在完成一道工序后可以停留在这台机器上，直到下游机器可用) 、有限缓存 ( f i n i t ei n t e r m e d i a t es t o r a g e ，f i s ) 调度问题和无限缓存( u n l i m i t e di n t c r m e a i a t es t o r a g e ，u i s ) 调 度问题。 1 2 3 生产调度问题的研究现状与方法 由于大部分调度问题都具有n p 难的特性，很难在多项式时间内找到最优的调度方案， 因此，优化调度算法一直以来是调度理论研究的核心。从调度问题提出至今的几十年里， 国内外的学者提出了一大批调度方法。从最初的整数规划、动态规划、分枝定界等运筹学 方法，到六十年代后期、七十年代的启发式方法，包括优先权分派规则( p r i o r i t yd i s p a t c h r u l e s ，p d r s ) 和瓶颈转移法( s h i f t i n gb o t t l e n e c kp r o c e d u r e ，s b p ) 等方法。到了八十年代，随 着机械制造、自动化技术、计算机科学、系统工程以及应用数学的发展，调度成为了一种 跨学科的研究领域，不断的有新的研究工具被应用到调度研究中，比较有代表性的有：以 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 为代表的基于群体智能的优化算法，以及以多智能体技术 ( m u l t i - a g e n t ss y s t e m s ，m a s ) 为代表的人工智能的调度方法。 通过对大量文献的分析，综合起来，目前已有的调度算法大致可以分为精确算法和启 发式算法( 近似优化算法) 两类【l5 1 。精确算法主要是指数学规划方法，包含分枝定界法 ( b r a n c h - a n d - b o u n d ，b & b ) 和动态规划法等方法。精确算法的主要优点是在理论上能得到 精确的最优解。但是由于其计算规模随着问题规模的增大而急剧地增大，因而一般适用于 浙江工业大学硕士学位论文 规模比较小的调度问题，难以在实际的企业生产中得到广泛的应用。而这方面，启发式算 法显示出相对较大的优越性。由于大部分调度问题都是n p h a r d 问题，并不能在多项式时 间内求得问题的最优解，故退而求其次，提出了很多启发式算法，如基于规则的方法、基 于人工神经网络的方法、局部搜索算法以及基于群体智能的优化算法。这些启发式算法能 在可以接受的时间内，求得问题的次优解，且这些次优解的质量能较好的满足实际生产调 度问题的要求。下面对以下几种算法进行简单的分析阐述，并重点阐述了与本文研究密切 相关的智能搜索方法。 ( 1 ) 基于运筹学的方法 基于运筹学方法是通过将待优化的问题简化为数学规划模型，采用基于枚举思想的分 枝定界法或动态规划法进行求解u 6 1 。这类方法属于精确算法。c r o c e 等【l 刀给出了一个能求 得中等规模的调度问题最优解的分枝定界算法，并用来求解两机f l o ws h o p 调度问题。 c a r l i e r 等【1 8 】提出了两种用于求解置换f l o ws h o p 调度问题( p e r m u t a t i o nf l o ws h o pp r o b l e m ， p f s p ) 的分枝定界法，并对这两种算法进行实验分析比较。 ( 2 ) 基于规则的方法 调度规则也称为调度规划、分派规则( d i s p a t c h i n gr u l e s ) 、优先级规贝i j ( p r i o r i t yr u l e s ) 或启发式规则，其本质是指根据一定的规则和策略，从尚未调度的工序选择一个操作作为 下一步操作的调度方法。基于调度规则的方法是经典的调度算法之一。由于这些规则是有 经验的决策管理人员和工程技术人员总结出来的一套行之有效的经验法则，既有有关专业 领域的知识，又有关于待求解问题的信息，较好地反映了原问题的自然结构，符合人们利 用经验处理问题的方法，因而，具有直观、简单实用、求解时间较少、易于实现并能用于 动态实时调度中等优点，在实际生产中获得了广泛的应用。 n e h 是在生产调度领域中应用最广泛的启发式规则之一。n e h 规则可以分为两个阶 段，首先，将所有工件按其总加工时间非增的顺序排列：然后，再将工件插入到已有的部 分加工顺序中，从而获得整个加工顺序【1 9 1 。文献【1 9 】和【2 0 】对n e h 进行改进，并将改进的 n e h 规则应用到置换流水车间调度问题中。j i n g 等【2 1 】提出并改进了几种启发式规则，并将 这些规则应用于两机可重入的f l o ws h o p 调度问题中。 但是，由于单个调度规则的有效性较低、适用性较窄，因而在实际应用中，往往需要 将调度规则进行适当的组合。 ( 3 ) 仿真调度法 基于仿真的方法利用离散仿真模型模拟实际生产过程，描述和定量评估复杂的制造系 浙江工业大学硕士学位论文 统，通过测试和分析各种调度方法，为实际调度采用合适的调度算法提供依据，进而调整 调度规则。但由于应用仿真进行生产调度的费用较高，且仿真的准确性受程序员判断能力 和技能的影响较大，并且每一次仿真只是对实际加工过程的一次抽样，很难从特殊的实验 中提炼出一般的规律，因此即使高精度的仿真模型也不能保证得到最优甚至较优的调度方 案。 ( 4 ) 智能优化算法 智能优化算法【5 1 是一类模仿自然界中某些演化机制的算法。主要有人工神经网络、模 拟退火法、禁忌搜索法，以及一类基于群体智能的优化算法，如遗传算法、蚁群算法、粒 子群算法等。 ( a ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，删 a n n 是一种模拟人脑神经系统的结构和功能，运用大量的处理单元，经广泛互连而组 成的网络系统。它不需要对过程模型有精确的了解，而是利用过程输入和输出数据训练网 络的连接权值，使网络能准确地反应实际的过程特性，在此基础上实施优化计算1 4 】。王万 良等 2 2 l z 3 1 对车间调度问题的换位矩阵表示法进行了改进，给出了新的车间调度问题的 h o p f i e l d 神经网络计算能量函数表达式，进而提出了改进的h o p f i e l d 神经网络车间调度方 法。徐新黎等 2 4 1 给出包含作业车间调度问题的所有约束条件的新的计算能量函数表达式， 并将离散h o p f i e l d 神经网络方法与混沌动力学相结合，提出一种改进的暂态混沌神经网络 作业车间调度方法。并在文献 2 5 1 中结合实际的生产约束，将上述方法应用于企业实际的 生产调度中。 人工神经网络的训练对其效率有很大的影响，并且当问题规模较大时，存在计算速度 慢、结构参数较难确定的缺点。 ( b ) 模拟退火法( s i m u l a t e da n n e a l i n g ，s a ) s a 是一种随机的局部搜索方法【2 6 1 ，它将组合优化问题与统计物理学的热平衡问题进 行类比，模拟热金属能量达到热平衡状态的过程。h i s a o 等【2 刀提出了基于最优前进策略和 基于首次前进策略的两种改进的s a 对f l o ws h o p 排序问题进行求解，实验结果表明，这 两个改进的s a 的性能要优于禁忌搜索算法。s e y e d 等【2 8 l 将s a 与作业的问题信息相结合， 求解f l o ws h o p 调度问题。吴大为等1 2 9 1 提出了一种求解作业车间调度问题的并行的s a ， 并用马尔科夫链分析了算法的全局收敛性。文献 3 0 1 和【3 1 】分别将s a 应用到j o bs h o p 和 o p e ns h o p 调度问题中。 由于模拟退火法能以一定概率接受差的能量值，因而有可能跳出局部极小，但它的收 浙江工业大学硕士学位论文 敛速度较慢，很难用于实时动态调度环境。 ( c ) 禁忌搜索算法( t a b us e a r c h , t s ) t s 是一种具有记忆功能的全局逐步优化算法，是对人类思维过程本身的一种模拟，它 通过设置禁忌表的方式，通过对一些局部最优解的禁忌( 或者说是记忆) 达到接纳一部分 较差解，避免算法陷入局部最优，引导搜索朝着全局最优解的方向进行。目前，t s 已被广 泛地应用于生产调度问题中。j o h a n n 等【3 刁将t s 应用到具有多目的机器的j o bs h o p 调度问 题中。文献 3 3 1 利用个体密集度和多样性指导t s 的搜索方向，并将改进的t s 应用到p f s p 中。b u r a k 等【3 4 】通过三种不同的交换机制产生个体的领域个体，并将t s 应用到f s p 中。 ( d ) 基于群体智能的算法 在最近一二十年里，基于某些自然规律的群体智能优化算法正在被逐步地应用于生产 调度领域，并取得了一定的成果，成为了国内外学者研究的热点之一。这些算法主要有遗 传算法( g e n e t i ca l g o r i t h m ，g a ) 、粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n , p s o ) 和蚁群算法 ( a n tc o l o n yo p t i m i z a t i o n , a c o ) 等。 g a 是由h o l l a n d 教授于上世纪7 0 年代提出的一种借鉴生物界自然选择和进化机制而 发展起来的