(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf_第1页
(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf_第2页
(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf_第3页
(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf_第4页
(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf_第5页
已阅读5页,还剩79页未读, 继续免费阅读

(控制理论与控制工程专业论文)基于遗传算法的车间调度方法及其应用.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

、 摘要 r ( 计算机集成制造系统( c i m s ) 能显著提高企业的综合经济效益。因而是当前国 内、外各大中型企业研究与实施的热点。生产计划与调度系统作为实施c i m s 工 程中的一个重要组成部分,是c i m s 功能结构模型中不可缺少的一个层次。调度 问题是组合优化问题,属于n p 问题,近几年各种智能计算方法逐渐被引入到调 度问题中,如遗传算法、模拟退火算法等。 遗传算法作为一种非确定性的拟生态随机优化算法在过去2 0 年中得到了广泛 的应用,出于其具有不依赖于问题模型的特性、全局最优性、隐含并行性等特点, 正越来越激起人们研究与应用的兴趣o j 本文应用遗传算法求解复杂的车间调度问 题,主要在以下几个方面作了一些研究工作: ( 1 ) 为了克服遗传算法容易出现提早收敛的缺陷,提出了一种改进的遗传算 法,并将其应用于流水车问调度问题。 ( 2 ) 针对混合流水车间调度问题,提出了一种基于遗传算法的求解方法,给出 了染色体的编码方法和相应的遗传算子,这种编码方法使得遗传算法的操作大大 简化。 ( 3 ) 针对实际生产调度问题存在大量的不确定性因素,研究了模糊流水车间调 度问题,并对嵌入邻域搜索的混合遗传算法进行了仿真,与其它算法得到的结果 进行了比较分析。 ( 4 ) 描述了机器调度问题中的提前拖期调度问题,1 - 1 对并行多机调度问题的 复杂性,将其分解为两个子问题,基于这个分解的思想,提出了一种基于遗传算 法的解决策略,对各种不同规模的问题进了仿真。 关键词:生产调7 机器调度,靠水车7 作业车彬7 遗传算癌,7 模糊逻辑y 提前拖期 a b s t r a c t c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m ( c i m s ) c a ng r e a t l yp r o m o t e t h e s y n t h e s i z e de c o n o m i cp r o f i to f t h ee n t e r p r i s e ,t h u si th a sb e c o m et h eh o t s p o to ft h e r e s e a r c ha n da p p l i c a t i o no f a l lk i n d so f e n t e r p r i s e s a sa ni m p o r t a n tp a r to f c i m s ,t h e p r o d u c t i o np l a n n i n g a n ds c h e d u l i n g s y s t e m i sa n o b l i g a t o r yl a y e r i nt h ec i m s f u n c t i o ns t r u c t u r em o d e l s c h e d u l i n gp r o b l e mi sc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m , w h i c hb e l o n g st on pp r o b l e m m a n yi n t e l l i g e n t c o m p u t a t i o n m e t h o d ss u c ha s s i m u l a t e da l g o r i t h m ( s a ) ,g e n e t i ca l g o r i t h m ( g a ) ,a r ei n t r o d u c e di n t os c h e d u l i n g p r o b l e m i nr e c e n t y e a r s a sa nu n c e r t a i ns t o c h a s t i co p t i m a la l g o r i t h m ,g ai sa p p l i e di nk i n d so ff i e l d si n t h ep a s t2 0y e a r s a n db e c a u s eo fi t si n d e p e n d e n c e ,g l o b a lo p t i m i z a t i o na n di m p l i c i t p a r a l l e l i s m ,g a i sd e v e l o p e da n d a p p l i e db y m o r ea n dm o r e p e o p l e i nt h i sp a p e r , g a i s a p p l i e d t os o l v e c o m p l e xs h o p f l o o r s c h e d u l i n gp r o b l e m i h a v em a d es o m e r e s e a r c hi nt h ef o l l o w i n ga s p e c t s : ( 1 ) i no r d e rt oo v e r c o m et h ew e a k n e s so fp r e m a t u r ec o n v e r g e n c ea p p e a r i n gi n g a ,a ni m p r o v e dg e n e t i ca l g o r i t h mi sp r o p o s e da n da p p l i e di nt h ef l o ws h o p s c h e d u l i n gp r o b l e m ( 2 ) t ot h eh y b r i df l o ws h o ps c h e d u l i n gp r o b l e m ,as o l u t i o nm e t h o d b a s e do ng a i s p r o p o s e d t h ee n c o d i n gm e t h o do fc h r o m o s o m ea n dt h ec o r r e s p o n d i n g o p e r a t o r sa r eg i v e n t h ee n c o d i n gm e t h o dg r e a t l ys i m p l i f i e st h eo p e r a t o r si n g a ( 3 ) s i n c e t h e r ea r e m a n y u n c e r t a i nf a c t o r s c o n s i s t i n g i nt h er e a l p r o d u c t s c h e d u l i n gp r o b l e m 。t h ef u z z y f l o w s h o p i sd i s c u s s e d ,t h e h y b r i d g a c o m b i n i n gn e i g h b o rs e a r c hi ss i m u l a t e d ,a n dt h er e s u l t i sc o m p a r e dw i t ht h e r e s u l t sg o tb yo t h e ra l g o r i t h m s ( 4 ) t h em a c h i n es c h e d u l i n gp r o b l e mw i t he a r l i n e s s a n dt a r d i n e s sp e n a l t i e si s d e s c r i b e d i d e n t i c a l p a r a l l e l m a c h i n e s c h e d u l i n gp r o b l e m i ss o l v e d b y s e p a r a t i n gi t i n t ot w os u b p r o b l e m sf o rt h ec o m p l e x i t y , t h e nas o l u t i o nb a s e d o ng ai sp r o p o s e d k e y w o r d s :p r o d u c t i o ns c h e d u l i n g ,m a c h i n es c h e d u l i n g ,f l o ws h o p ,j o bs h o p ,g a , f u z z yl o g i c ,e a r l i n e s s t a r d i n e s s 浙江工业大学硕士学位论文 第一章绪论 第一章绪论 1 1 引言 随着科学技术的发展,生产规模越来越大,复杂性越来越高,市场竞争也越 来越激烈,因此对企业的管理和对生产过程的监控都提出了更高的要求。近几十 年来,各类生产过程都已经发生了显著的变化,其主要特征是生产规模的大型化 和生成过程的连续化。在激烈的市场竞争中,为了保证生产的高效稳定运行,以 获得最大的经济效益,原来简单的、局部的、常规的控制和仅凭经验的管理已经 不能满足现代生产的要求了,企业管理者和控制工程师们面临的问题是:如何根 据市场上原料供应和产品需求的变化进行经营决策和组织生产;如何在生产计划 改变的情况下对生产过程进行控制,以便最大限度地发挥生产的柔性;如何在生 产工艺不作大的改变的前提下进行管理、决策,使企业产生最大的综合经济效益。 为了解决上述问题,1 9 7 3 年h a r r i n g t o n 博士提出了计算机集成制造c i m 的概念, c i m 是一种组织、管理与运行企业生产的新哲理,它借助计算机软件、硬件,综 合运用现代管理技术、制造技术、信息技术、自动化技术、系统工程技术,将企 业生产过程中有关人、技术、经营管理三要素及其信息流与物质流有机地集成并 优化运行,以实现产品的高质、低耗,从而使企业赢得市场竞争。计算机集成制 造系统( c i m s ) 是基于c i m 哲理而组成的实际系统。在这种自动化程度较高的系 统中,使生产过程合理、高效运行的调度问题变得非常复杂,需要建立有效的计 算机调度控制策略,因此调度问题的研究具有重要的现实意义。由于大量的调度 问题都是n p 完全问题,目前尚无有效的求解策略,因此调度问题的研究也具有 重要的理论意义。 1 2 生产调度问题 生产调度问题一般可以描述为:针对某项可以分解的工作,在一定的约束条 件下,如何安排其组成部分( 操作) 所占用的资源、加工时问及先后顺序,以获得 产品制造时间或者成本等最优。 影响调度问题的因素很多,正常情况下有:产品的投产期,交货期( 完成期) , 生产能力,加工顺序,加工设备和原料的可用性,批量大小,加工路径,成本限 制等,这些郝是所谓的约束条件。有些约束条件是必须要满足的,如交货期,生 产能力等,而有些达到一定的满意度即可,女n _ - l - 产成本等,这些约束在进行调度 时可以作为确定性因素考虑。而对于设备故障,原料供应变化。生产任务变化等 非正常情况,都是事先不能预见的,在进行调度时大都作为非确定性因素考虑。 生产调皮中涉及的工厂资源包括:原料、l 殳备( 加工、存储、运输) 、人力、 浙江工业犬学硕士学位论文 第一章绪论 资金、能源等。资源的详细分配受到产一讯的生产工艺的限制。 生产调度的性能指标可以是成本最低、库存费用最少、生产周期最短、生产 切换最少、设备利用率最高、三废最少等。实际生产调度的性能指标大致可以归 结为三类: 1 最大能力指标,包括最大生产率、最短的生产周期等,它们都可以归结 为在固定或者无限的产品需求下,最大化生产能力以提高经济效益。在假定存在 连续固定需求的自u 提下,工厂通过库存满足产品的需求,因此,调度问题的主要 目标是提高生产设备的利用率、缩短产品的生产周期,使工厂生产能力最大。 2 成本指标,包括最大利润、最小的运行费用、最小投资、最大收益等, 其中收益指产品销售收入,运行费用包括库存成本,生产成本和缺货损失。 3 客户满意度指标,包括最短的延迟,最小的提前或者拖期惩罚等。 在传统的调度中,一般以平均流通l l , f _ f n l 最小、制造周期最短、满足交货期为 调度目标,而在实际生产中,由于提前完成的产品必须保存到交货期,而提前产 ;钆必须交付违约金,因此,在实际调度巾更加重视提前或者拖期惩罚调度。 调度问题也是一个优化问题。优化问题可以自然地分为两类:一类是连续变 量的问题;另一类是离散变量的问题,称为组合优化问题。对于连续变量的优化 问题,一般是求一组实数或者一个函数:而在组合优化问题中,是从一个无限集 或者可数无限集中寻找一个对象,它可以是一个整数、集合、排列或者一个图。 生产过程一般按照其输出的产品是呈现连续的产品流、离散的批量、离散的 数量三种情况,分为连续生产过程、问隙生产过程和离散生产过程。 在离散生产过程中,产品通常是分t t l :( 原料相同、加工工序相同的一组产品) 制造的,一定数量的产品作为一个3 7 f - l :组,1 :且在各个2 e 1 - 台之问传输,而且, 每个3 _ f l :_ i i l l 有独立的个性。机械期1 3 2 是兆型f f j _ i i 产过程。 在连续生产过程巾,原料经山不i z l f ( , j 专用设备加工转变为产品。每个砹备都 是在稳定的工作状态,完成一项规定的生产操作,一个连续生产过程输出的产品 足连续的产一w 一流。 间隙生产过程又称为批处理( b a t c hp r o c e s s ) ,是由一个或者多个按一定顺序执 行的操作步( 或者操作阶段) 组成。这些操作步是离敞的,而每步中的过程是连续 的。间隙生产过程一般包括若干个通用设备,多个产品在有限个设备上生产。 相应地,生产调度问题可以分为面向机加工等离散操作的车间调度问题,和 面向流程工业生产过程的间隙生产调度或者称为批处理凋度问题。 m a c c a r t h y l e la l ( 1 9 9 3 ) ,陈荣秋( 1 9 8 7 ) 采用a b c d 体制对生产调度问题进 行了分类,其中a 、b 、c 、d 的含义为:a 是工件数量,b 是机器数,c 为工艺 和管理约束决定的加工模式,d 为优化指标。常见的加工模式有 浙江工业大学硕士学位论文 第一章绪论 | | j f o f ,p e r m k p a r a l l e l ,k p a r a l l e l 单机 单件加工( j o bs h o p ) 流水线加工 丌放式加工 序排列流水线d n i ( p e r m u t a t i o nf l o w s h o p l k 个机器并行加工( k - m a c h i n ei np a r a l l e l ) 每道工序有个机器并行的单件加工 优化指标d 的形式多种多样,大体上可以分成三类: ( 1 )以有效利用资源为目标,如c 。( 最大完工时问) ( 2 ) 以刑需求的快速反应为目的的指标,如c ( 平均完工时问) 、f ( 平均流程时 问) 、( 平均等待时间) : ( 3 )以遵守交货期为目的的指标,如一。( 最长延误时问) 、r ( 延误交货工件 数) ; 其中,如果目标函数是完成时间的非减函数,则称为正则指标,如m a k e s p a n , 否则称为非正则指标,如提前拖期数,随着准时制( j i t ) 生产的兴起,目标函数为 非正则的情况逐渐得到重视:另外根据调度环境的不同,可分为静态调度和动态 调度:根据系统信息是否完全,可分为确定性凋度和随机调度。 1 3 车间调度问题 1 3 1 车间调度问题描述 车问调度问题一般可以描述为:”个: 作在m 台机器上加工,一个工件分为k 道工序,每道工序可以在若干台机器上加工。每一台机器在每个时刻只能加工某 个工件的某道工序,只能在上道工序加工完成后才能开始下一道工序的加工,前 者称为占用约束,后者称为顺序约束。 车间调度问题的决策内容包括分配决策( m - f - b 的加工顺序) 并n m j 间决策( m l - i = 各工序的加工时间) 以及路径决策( 工件工序的加工设备的分配) 。 车间调度问题的特点是多个m f - b 在有限的机器上加工,每台机器在切换不同 工件生产时需要一定的准备时间。切换加工次数增加有利于减少工件的库存,但 导致生产率下降。因此,需要在库存成本稿i 工件切换加工频率之间取得平衡。生 产的柔性体现在设备使用和设备安排两个方面,设备使用的柔性是指设备可用于 多个零件的多个工序的加工;设备安排的柔性是指工件的设备加工路径不是固定 和预先确定的,具有可选的路径,可以通过将若干设备组作为一条或者多条生产 线加工一种工件,使得该工件生产率最大。 车间调度问题的另一类研究集中于柔性制造系统( f m s ) ,f m s 由一系列n c 浙江工业大学硕士学位论文第一幸绪论 是固定和预先确定的。具有可选的路径,可以通过将若干设备组作为一条或者 多条生产线加工一种工件,使得该工件生产率最大。 车间调度问题的另一类研究集中于柔性制造系统( f m s ) ,f m s 由一系列n c 数控设备组成,n c 能够单独加工多个工件,在选择了待加工工件后,所需刀具 必须分配到该设备的工具集中。f m s 问题包括:工件选择分配、设备分组、生 产率确定和设备负荷、工具分配等问题,它的约束包括设备工具集的容量限制、 设备可用时间和设备负荷等( 方剑等,1 9 9 7 ) 。 1 3 2 车间调度问题的特点 f 1 ) 复杂性:车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。 每个工件又要考虑它的加工时间、安装时间和操作顺序等因素,因而相当复杂。 调度问题是在等式或不等式约束下求指标的优化,在计算量上往往是n p 一完全 问题,随着问题规模的增大,其计算量急剧增加,使得一些常规的方法无能为 力,对于这一点q a r e ym e ta 1 ( 1 9 8 8 ) 等给出了明确的证明。即使对于单台机床 加工问题,如果有胛个工件而每个工件只考虑加工时间以及与操作序列有关的 安装时间,则这个问题就和以个城市的t s p 问题等价。对于一般加工系统,问 题更复杂。 ( 2 ) 随机性;车间调度中有很多随机和不确定因素,如工件到达时间的不确 定性,实际工件的j m i 时间也有一定的随机性。而且系统中常有突发偶然事件, 如机器出故障、作业交货期的改变等。 ( 3 ) 约束性:车间调度问题中资源的数量、缓存的容量、工件到期时间以及 工件的操作顺序等都是约束。此外还有一些人为的因素,如要求各机器上的负 荷要平衡等。 ( 4 ) 多目标:调度的目标很多,而且这些目标之间往往是有冲突的。k i r a n a s e ta i ( 1 9 8 4 ) 将调度目标分为三类:基于作业交货期的目标、基于作业完成时间 的目标和基于生产成本的目标,并列举了几十种调度目标。 1 3 3 车间调度问题的优化方法 虽然对车间调度问题的研究已经有几十年的历史,提出了一大批调度方法, 但至今尚未形成一套系统的理论与方法,已有方法可归结为优化调度方法和启 发式方法两大类。 优化调度方法通过精确求解解析模型获得最优解,或通过近似求解获得次 优解。优化方法从全局的角度出发,在所有的装置、操作任务和感兴趣的时间 段内进行搜索,能够得到优化解。优化方法建立在数学规划基础上,尽管数学 规划方法比较成熟,但只能有效地解决小规模优化问题,对于复杂的大规模生 产调度问题。随着装置数和任务数的增加,感兴趣时间段的增长,其解析模型 4 浙江工业大学硕士学位论文 第一章绪论 的状况进行凋度,保证了局部最优,但难以保证全局最优。 启发式方法与优化方法比较,各有利弊。事实上,两类方法有很大程度的互 补性,将两类方法有机结合的研究,会成为今后研究的热点。 ( 1 ) 数学规划方法 从数学规划的角度,车问调度问题可以归结为在等式约束或者不等式约束 下,对一个或者多个目标函数的优化,可以表示为m i l p 或者m i n l p 优化模型, 采用各种数学规划方法求解,数学规划方法往往采用基于枚举思想的分枝定界法 或动态规划算法进行求解。s a r i ns c e la 1 ( 1 9 8 8 ) ,p o t t sc n e ta 1 ( 1 9 8 5 ) 提出了 改进的分枝定界法,其不同点主要在于分析舰则、定界机制和上界的产生三方面 的差异。这类方法虽然从理论上能求得最优解,但由于其计算复杂性和搜索效率 低下,难以解决大规模的调度问题。 拉氏松弛法由于其在可行的时间里能对复杂的规划问题提供好的次优解,并 能对解的次优性进行定量评估,近年来已成为解决复杂车间调度问题的一种重要 方法。l u he b e ta 1 ( 1 9 9 0 ) 用拉氏松弛法解决了单机调度和多台并行机调度问题。 h o i t o m td j e ta 1 ( 1 9 9 0 ) 通过引入更多的拉氏乘子松弛了操作之间的顺序约束, 将这种方法用于一般的j o bs h o p 调度问题,熊锐等( 1 9 9 6 ) 用这种方法求解了集成 车间计划与调度问题。 采用数学规划的方法,表达清晰,易于在计算机上求解,但生产环境具有很 多不确定的因素,存在建模不确定性和求解空间太大,造成计算困难,特别是不 能反映特定调度领域的自然结构,所以很难应用经验知识去处理调度问题。 ( 2 ) 基于规则的调度方法 调度规则因其易于实现、计算复杂度低等原因,能够用于动态实时调度系统 中,许多年来一直受到学者们的广泛研究,并不断涌现出许多新调度规则。 p a n w a l k a rs e ta 1 ( 1 9 7 7 ) 总结了1 1 3 条规则,并将它们分为了三类:简单规则、复 合规则、启发式规则。m o n t a z e r im e ta l ( 1 9 9 0 ) 列举了常见的2 0 条规则,并针对 一个实际的f m s ,分析了这些规则对系统性能如作业的平均等待时间、机床的平 均利用率、作业总加工时间等的影响。随着计算机运算速度的飞速提高,人们希 望寻找新的近似调度方法,以合理的额外计算时问代价,换得比单纯启发式规则 所得到的调度更好的调度,a d a m s j e la t ( 1 9 8 8 ) 提出了移动瓶颈方法。c h a n gyl e l 以( 1 9 9 6 ) 使厢线性舰划模型对4 2 条规则进行了评估,结果显示最短处理时间( s p t ) 规则 性能最好,而最长处n u , j 间( l p t ) 最差。 启发式规则具有全局敏感性,利用不同的规则可产生不同的调度方案,而且 规则在不同的场合所起的作用也不同,调度系统的性能取决于规则的选择。因此, 规则的选择成为基于规则调度方法的主要障碍。d o r n d o r f u e l a l ( 1 9 9 5 ) 提出了用 浙江工业大学硕士学位论文第一章绪论 遗传算法选择规则的方法,g r a b o tb e la l ( 1 9 9 4 ) 、万国华( 2 0 0 1 ) 用模糊逻辑方法控 制规则的选择,表现出与人工智能结合的趋势。 ( 3 ) 基于知识的调度方法 近年来受实际需要的推动,基于知识的智能调度系统和方法的研究取得了很 大的进展。基于知识的调度方法是用专家系统自动产生调度或辅助人去调度。它 是将传统的调度方法与基于知识的调度评价相结合的方法。 在八十年代后期,几位学者先后丌展了基于调度系统处于不同的状态,采用 不同的调度规则策略的动态调度方法的研究,其共同特点是:在支持某些活动发 生的资源条件具备时( 称为决策点) ,根据系统当时所处的属性状态,决定采取何 种规则( 策略) ,确定或选择活动发生的顺序和时问,即所谓的状态指导的智能调 度方法。d o u b l g e r iz e la 1 ( 1 9 9 3 ) 以- - 个柔性p c b ( e i 琊4 电路板) 安装系统为实例, 提出了基于知识的调度方法k b s ( k n o w l e d g e - b a s e ds c h e d u l i n g ) 。s a r i n s c e t a 1 ( 1 9 9 0 ) 用黑板模型来组织和维护动态数据库。在规划层用数学规划求解,在调 度控制层用基于知识的调度方法。 尽管基于知识的调度方法可以较快地解决问题,但是知识库的建立是一个 “瓶颈”问题,对于具体问题有很大的针对性,需要丰富的调度经验和知识,因 此,张纪会( 1 9 9 9 ) 等提出了一种结合遗传算法和机器学习获取动态调度知识方法。 ( 4 】仿真调度方法 由于制造系统的复杂性,很难用个精确的解析模型来进行描述分析。而通 过对仿真模型的运行收集数据,就能对实际系统进行性能、状态方面的分析,从 而能对系统采用合适的控制调度方法。k i r a na s e la l ( 1 9 8 4 ) 回顾和总结了在动 态环境下基于纯仿真模型的j o bs h o p 训度问题的研究状况。w us yd e t 口,( 1 9 8 9 ) 提出了基于纯仿真模型的调度方法,即在一个较短的时间段内用仿真来 评价一个分派规则集,选取最小代价的规则,以适应系统状态的变化。l e u n gl c e la 1 ( 1 9 9 3 ) 运用纯仿真模型,同时解决f m s 中作业调度和搬运小车及刀具的资 源分配问题。 基于纯仿真法虽然可以包含解析模型无法描述的因素,并且可以提供给使用 者一个调度性能测试的机会,但其不可避免地存在以下问题:a ) 缺乏理论意义; b ) 应用仿真进行生产调度的费用很高;c ) 仿真的准确性很大程度受编程人员的判 断和技巧的限制。 由于制造系统是一类典型的离散事件系统,因此可以用研究离散事件系统解 析模型和方法去探讨车间调度问题,诸如排队论、极大极小代数模型、p e t r i 网等。 车间调度中的排队论方法是一种随机优化方法,它将每个机床看成一个服务 台,将每个作业作为一个客户。j i a n gc q e ta 1 ( 1 9 9 1 ) 用带有有限缓存的排队网 6 浙江工业大学硕士学位论文第一章 绪论 络来描述带有有限存储容量的f m s ;刘瑞华等( 19 9 4 ) 针对f m s 中一类特殊的 d e d s :f o r k j o i n 排队网络,利用了极大代数方法对其进行建模,并进行了系统 的稳定性分析。总的浇来,排队网络模型山于从随机统计的角度来描述f m s ,难 以表述系统中存在的某些特性( 如有限的缓存空问等) ,同时产生的输出是基于系 统稳态操作的平均量,因此其很难得到比较具体的细节。 p e t r i 网作为一种图形建模工具,为离散事件系统的模型化、性能分析和设计 提供了一个统的环境,对于描述系统的不确定性和随机性也具有一定的优越 性,其在自动制造领域的综述文献见d s o u z ak a e t 以( 1 9 9 4 ) 一文。l e ed ye t d ,( 1 9 9 4 ) 用赋时p e t r i 网为f m s 建模,通过优化变迁的发生序列来产生搜索可标 识集,从而得到较优的调度结果。 虽然p e t r i 网建模较为直观,但p e t r i 网模型用于车间调度还存在以下的问题: 1 ) 节点语义的单义性,使得所携带的系统信息量不够丰富:2 ) 重用性差,p e t r i 网 都是基于f m s 中作业的加工流程建模,当作业需求或工艺稍有变动,必须改变 模型结构;3 ) 很难对高级的调度规则建模。 ( 5 ) 启发式图搜索法 主要有宽度优先、深度优先、b e a m 搜索及a 或者a + 算法等。b a l a se ( 1 9 6 9 ) 将调度排序问题用一个连接图来表示,通过首先构造一个可行解,采用基于隐枚 举的搜索方法不断提高解的次优性;c h a n gy l e ta l ( 1 9 8 9 ) 采用b e a m 搜索法来 识别瓶颈机器,进行调度。a n u pk s e ta l ( 1 9 9 6 ) 争t 对基于树搜索的最好优先的爿 算法需要大量内存的问题,提出了一个图搜索法,并对两种方法作了比较。 对于此类方法如何提高搜索效率、减少内存使用,以能解决比较大的规模的 问题,还需要进一步探索。 f 6 1 局部搜索方法 近年来各利局部搜索算法在车问调度叫_ l 得到了广泛的应用,这些局部算法在 优化机制方面存在一定的差异,但优化流程却具有较大的相似性,均是一利一邻 域搜索”框架。算法从一个( 一组) 初始解出发,在算法参数的控制下通过邻域函 数产生若干邻域解,按接受准则( 确定性、概率性或混沌方式) 更新当前状态,然 后按参数修改准则调节控制参数,如此重复以上搜索过程直至算法终止准则满 足,最终得到问题的优化解。 由于这些算法高效的优化性能、无需问题的特殊信息等优点,受到各领域广 泛的关注和应用。特别是最近发展起来的基于生物学、物理学和人工智能的一些 具有全局优化性能且通用性强的局部搜索算法。研究较多的有模拟退火( s a ) 遗 传算法( g a ) 、禁忌搜索( t s ) 、进化规划( e p ) 、进化策略( e s ) 和混沌搜索( c s ) 等。 1 贪婪随机自适应搜索方法( g r e e d y r a n d o m i z e da d a p t i v es e a r c hp r o c e d u r e s ) 浙江工业大学硕士学位论文第一章绪论 这种方法是一种基于问题空删的方法,r e s e n d em g c ( 1 9 9 7 ) 将g r a s p 应用 于j o bs h o p 渊度。算法包含构造和邻域搜索两个阶段。构造阶段利用贪婪函数将 部分调度的所有下次可调度的工序进行排序,从中选择一定数量的最好工序进入 受限候选列表r c l ( r e s t r i c t e dc a n d i d a t el i s t ) q - i ,然后从r c l r p 随机选择一个工序,重 复进行,一直到构成一个完整的调度;在邻域搜索阶段用邻域中更好的解不断地 代替当前的解,一直到不能发现更好的解为止;然后返回,重新进行构造和搜索。 算法般以进行一定迭代次数为终止条件。 尽管g r a s p 算法具有跳出局部最优解的能力,但足收敛过程非常慢,算法的 每次迭代都足相互独立的,为l l l :;b i n a t os e la l ( 2 0 0 0 ) :h :算法中引入了记忆功能, 使得每次迭代都能利用上一次的信息,从而加快收敛进程。g l o v e rf ( 1 9 8 6 ) t i j 究 发现部分调度v 和部分调度v + l 两者的较好解非常棚似,因此b i n t os e ta 1 ( 2 0 0 0 ) 应用p o p ( p r o x i m a t eo p t i m a l i t yp r i n c i p l e ) 策略对部分调度进行定期的邻域搜索,而 不像般的g r a s p 只对完整调度进行邻域搜索。 2 阈值( t h r e s h o l d ) 算法 局部迭代搜索算法中最常用的方法是阈值算法。假如邻域解和当前解的差在 一个给定闽值内,即f ( x ) 一f ( x ) l ,那么它选择这个新的结构。闽值算法最 简单的例子是将设为0 ,即只有好结构才被接受。a a r t se hl e ta l ( 1 9 9 4 ) 将闽 值设为一个较高的非负值,然后逐渐地减小为0 ,最后将这种方法运用于解决 1 0 x1 0 的j o bs h o p b 题。以上这两种方法只要一搜索到局部最优解算法就停止执 行了,显然不能用于解决较复杂的多峰问题,为此a a r t se h le ta 1 f 】9 9 4 ) 进一 步改进了阔值算法,提出了多点丌始迭代改进算法( m s i m ) ,他的方法是,首先构 造多个搜索点,只要算法- - i l k 敛到局部最优点就从另外一个点重新开始搜索,一 直到满足迭代结束条件为止,然后从所有的局部最优点中选择一个最好的点作为 问题的解。庞哈利等( 2 0 0 0 ) 等提出了一种根据搜索进展自适应设定闽值和邻域搜 索次数的改进的算法,对无优先级双目标流水车问问题进行求解,并与现有启发 式算法进行了比较,结果表明这种算法可以求得更稳定、高质量的解。 3 模拟退火法( s i m u l a t e da n n e a l i n g ) 模拟退火算法( s a ) 将组合优化问题与统计力学中的热平衡问题类比,它模仿 了晶体结晶的冷却过程,在较高温度瓦下,系统状态为s ,能量( 即目标函数) 为e , 选择s 的一个领域s7 ,如果e ( s ) e ( s ) ,则接受s 为下一状态,否则以概 p ( 邓( m ( ”i 率接受s 。经过一定次数( 称为m a r k o v 镪长) 的搜索,认为系统在此 温度下达到平衡,则降低温度l 再进行搜索,直到满足结束条件。 m 澎等( 1 9 9 4 ) 为f l o ws h o p 问题构造了一类模拟退火法。模拟退火法的改进算 法有加温退火法、有心 五的模拟退火法等。h i s a ol e t a l ( 1 9 9 5 ) 提出一种改进的模 浙江工业大学硕士学位论文第一章 绪论 拟退火法,用来解决具有最t j 、m a k e s p a n 指标的f l o ws h o p 排序问题,并与禁忌搜 索法等进行了比较。 模拟退火法也可与其他方法相结合进行求解,如m i t t e n t h a lj e t a l ( 1 9 9 3 ) 先用 贪心法搜索,将得到的作业序列作为初始解,再用模拟退火法求解单机调度问题。 k o l o n k om ( 1 9 9 8 ) 经过研究表明对于作业车问调度模拟退火算法的执行过程不是 个收敛的过程,基于这个结果他提出了结合遗传算法的混合算法。 由于模拟退火法能以一定的概率接受差的能量值,因而有可能跳出局部极 小,但它的收敛速度较慢,很难用于实时动态调度环境。 4 禁忌搜索法( t a b us e a r c h ) 对于复杂的组合优化问题,禁忌搜索也是一种通过邻域搜索以获取最优解的 方法,g l o v e r e ( 1 9 8 6 ) 叙述了它的基本原理。它从一个可行解s 出发,产生s 的s 领域,如果厂为目标函数,选取所有领域中使f ( s ) 为最优的状态作为下一个状 态,并把这一移动的反向移动存入一个称为禁忌移动( t a b um o v e ) 的表中。列在表 中的移动在以后若干步内不允许再产生,这样可避免搜索退回去。每搜索一次, 更新一次禁忌移动表。由于禁忌移动表的限制,有可能跳出局部极小。 t a i l l a r de ( 1 9 9 0 ) 提出了解决f l o ws h o p 调度问题的禁忌搜索算法,l a g u n ae t a l ( 1 9 9 1 ,1 9 9 3 ) 最早将禁忌搜索策略应用予j o bs h o p 调度中:为了更有效地搜索解 空间,m a n u e ll e la ( 1 9 9 3 ) z j l k t 插入移动和移动相结合的机制提高了搜索效 率。 b a r n e sj w ( 1 9 9 3 ) 指出将禁忌搜索法和其它优化方法组合成混合搜索算法效 果比较好,李大卫等( 1 9 9 7 ) 等将禁忌搜索方法作为遗传算法的变异算子,改进的 遗传算法提高了遗传算法的爬山能力,t h o m s e ns ( 1 9 9 7 ) 通1 过分枝定界方法促使禁 忌搜索趋于多样化,获得了较好的结果。 5 遗传算法 遗传算法是一种新的并行优化搜索方法。它是一种模仿生物群体进化过程的 种优化算法,给定一组初始解作为一个群体,通过选择、交叉和变异等遗传操 作来搜索最优解。 李国富f 1 9 9 8 ) 用遗传算法对j o bs h o p 零件排序问题进行优化搜索,并在算法中 引进了一些新的思想,以有利于降低利群的规模,提高计算速度,改善优化结果。 关于遗传算法在车间作业中的应用详见c h e n g r e ta 1 ( 1 9 9 6 ) 。 遗传算法的最大优点是通过群体间的相互作用,保持已经搜索到的信息,这 是基于单次搜索过程的优化方法所无法比拟的。但是,对于某些问题遗传算法也 存在着计算速度较慢的问题。这时通常将遗传算法和其他优化方法结合使用,有 浙江工业大学硕士学位论文第一章 绪论 利于改善搜索效率。h o l s a p p l ec w e ta 1 ( 1 9 9 3 y 1 遗传算法与图搜索法相结合, 利用遗传算法进行知识的推理、启发,再用过滤束搜索法进行优化搜索,以得到 商质量的f m s 静态调度。方剑等( 1 9 9 7 ) 提出了一种将遗传算法和分派规则相结合 的调度算法,用遗传算法决定各工件的每个操作应分配到哪台机器上加工,而对 每台机器则运用分派舰则来决定相应工件在此机器上加工的次序和丌始加工时 间。 ( 7 ) 神经网络优化 神经网络( n n s ) 是一利模拟人脑神经系统的结构和功能,运用大量的处理部件 经广泛互连而组成的网络系统。h o p f i e l d 应用神经网络方法求解旅行商问题获得 成功,从而为组合优化问题求解丌辟了新的途径。c h e u n gj y ( 1 9 9 4 ) 描述了一些 主要的用于求解调度问题的神经网络结构:搜索网络( h o p f i e l d 网络) ,纠错网络( 多 层感知器) ,随机网络( b o l t z m a n 机) ,竞争网络和自组织网络。然而,对于求解j o b s h o p 调度问题来说,上述的神经网络模型归纳起来主要还是两种。 一种是h o p f i e l d 神经网络模型。f o o yse ta t ( 19 8 8 ) 首先提出用h o p f i e l d 网 络求解j o bs h o p 调度问题,同时为避免网络陷入局部极小,又提出了一种随机 h o p f i e l d 网络。为了改进早期的方法,f o oy s e ta 1 ( 1 9 8 8 ) 等后来又提出一种整 数线性规划神经网络( i l p n n ) 来解决j o bs h o p 调度问题。z h o ud n e la l ( 1 9 9 1 ) 针对i l p n n 系统的局限性,又提出一种线性规划神经网络( l p n n ) 结构。在最近 研究基于神经网络的j o bs h o p 调度工作中,s u nk t e ta ( 1 9 9 3 ) 等提出了约束神 经网络方法,s a b u n c u o g l u i e ta l ( 1 9 9 6 ) 用种3 维结构的神经网络求解j o bs h o p 调度问题,还有王秀宏( 2 0 0 1 ) 等提出一种瞬态混沌神经网络方法来求解j o bs h o p 调度问题,其利用神经元的自抑制反馈产生混沌动态,同时利用一时变参数控制 混沌行为,使网络在经过一个短暂的倍周期倒分叉后逐渐趋于一般的h n n ,从 而收敛到一个最优或近似最优的稳定平衡点。 除了h o 明e j d 神经网络模型,另外b p 神经网络模型也用来求解j o bs h o p 调 度问题。r e m u sw ( 1 9 9 0 ) 是最早研究用b p 神经网络求解j o bs h o p 调度问题的人 之一,他通过比较线性衰减规则改进了几个b p 网络模型。c h r y s s o l o u r i sg e t a l ( 1 9 8 8 ) 等使b p 神经网络方法在每个作业车间中心都要求确定资源数量的制造 系统设计中得到了应用。另外融合了专家系统的混合b p 神经网络模型是最常用 的求解j o bs h o p 调度问题的b p 网络结构,其中最早的例子之一是r a b e l ol ,c e l 。f ( 1 9 8 9 ) 提出的混合模型,d a g l ic h e ta t ( 1 9 9 5 ) 提出了结合遗传算法的b p 神经 网络f g n s ) 模型。近来,j a i n as e l a l ( 1 9 9 8 ) 提出的改进的b p 神经网络模型克服 了传统的b p 网络模型在处理包含复杂的输入输出映射的问题时会训练不成功并 收敛于局部极小解的不足。 浙江工业大学硕士学位论文 第一章绪论 1 3 4 车间调度问题的调度策赂 山于一般的车间调度问题的复杂性,各种不同的具体问题往往有很多不同的 解决方法,因此需要从策略上去考虑调度问题,形成各种研究方法策略以指导调 度的研究。目前调度的策略有并行或分布策略、分解与成组策略、人机交互策略、 动念重调度策略、多目标优化策略等等。 ( i ) 并行和分前i 策略 山于一般调度问题很复杂,旦问题规模加大就更难求解,因此不少研究者 提出- j 1 :7 7 或分解的策略来解决调度问题。姜作廉等( 1 9 9 4 ) 使用组合优化的分级决 策方法和b a r 相结合,在并行机系统上,构造了并行算法m b a b ,解决了规模 较大的流水车间调度问题;康一梅等( 1 9 9 7 ) 提出用m i m d 并行机实现j o bs h o d 实时 周度的并行算法。 多智能体系统的研究是目前分布式人工智能领域的研究热点。大量的研究表 明多智能体系统特别适用于解决复杂问题,尤其是那些经典方法无法解决的单元 问有大量交互作用的问题。由于调度问题的复杂性和并发性等特点,最近多智能 体已在在调度上得到了较多的应用。k a phk e t a l ( 1 9 9 6 ) 将每个代理对应为一个 d r l z q ,心,采用封f 件驱动的动态调度,研究了代理之间的调度策略共享及如何协 调各个代理的行为以完成个全局调度目标。李飒等( 2 0 0 0 ) 管1 。对随机性j o bs h

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论