（载运工具运用工程专业论文）不确定环境下柔性制造系统鲁棒调度研究.pdf

中文摘要 随着信息时代的来临，生产制造已经转向以多品种、中小批量为主 要模式。柔性制造系统是因此而发展起来的一种自动化生产方式。合理 的生产调度是确保柔性制造系统实现其经济效益的必要条件，而制造系 统自身存在的参数不确定性使得调度得到眵结果在实际运行当中的性能 指标值会大大下降，偏离原来的最优点。夕本文就柔性制造系统在系统运 行参数受到扰动情况下的调度问题进行了研究。 本文首先介绍了柔性制造系统的特征和生产计划和调度在系统中的 地位，主要的调度方法。介绍了调度模型的分类，并给出了当前处理不 确定因素的几种建模方法，详细的分析了不确定因素条件下调度的研究 现状。随后，阐述了柔性制造系统中存在的不确定因素及其对系统性能 评价指标的影响，以及国内外对此问题的研究现状，据此指出，找到一 种在系统参数变化的情况下仍然能够保持较优系统性能评价指标的调度 方法是十分必要的。并在此思想基础之上，利用m o n t ec a r l o 方法对不确 定参数进行随机抽样，建立了基于最优偏差思想的鲁棒调度的数学模型， 同时给出了一种基于遗传算法的鲁棒调度优化算法。 基于本文提出的鲁棒调度方法，选用典型算例对调度过程加以分析 并找到了加工时间在一定区间上分布情况下的鲁棒调度策略。利用先进 的离散事件仿真软件q u e s t 对鲁棒调度结果进行仿真运行，实验结果 表明，鲁棒调度方法得到的调度策略在总体性能上要好于一般的静态调 度和动态调度方法。 关键词：柔性制造系统，鲁棒调度，遗传算法，最优佬 ! ! ii ! 竺塑主堂垡堡苎 至堕塞! 堡! 墨丝型堕至竺! 堡塑垦! ! 生 a b s t r a c t w i t ht h ea d v e n to fi n f o r m a t i o ne p o c h ，t h em o s tm a n u f a c t u r i n gm o d e s t u mt om u l t i b r e e d m i d d l eo rs m a l lb a t c h f o rt h i sr e a s o n ，f m s ( f l e x i b l e m a n u f a c t u r i n gs y s t e m ) i sd e v e l o p e da sa na u t o m a t i cm a n u f a c t u r i n gp a t t e m - ar e a s o n a b l em a n u f a c t u r i n gs c h e d u l i n gi se s s e n t i a lf o rf m st or e a l i z ei t s e c o n o m i cb e n e f i t s w h i l em a n yu n c e r t a i n t i e sj nf m sw i l lc a u s eas c h e d u l e w h i c hi s o p t i m a lw i t hr e s p l e c tt o as t a t i cs c h e d u l i n gm o d e ly i e l d i n gq u i t ea p o o rp e r f o r m a n c e w h i c hi se v a l u a t e db yt h ea c t u a lp r o d u c t i o np a r a m e t e r s i n t h i st h e s i s ，t h es c h e d u l i n gp r o b l e mo ff m si nw h i c ha l lj o b s p r o c e s s i n gt i m e m a y b eu n c e r t a i ni sr e s e a r c h e d f i r s to fa l l ，t h ec h a r a c t e ro ff m s ，t h ei m p o r t a n c eo fm a n u f a c t u r i n g p l a n n i n ga n ds c h e d u l i n gi nt h es y s t e m ，t h ep r i m a r ys c h e d u l i n gm e t h o d sa r e i n t r o d u c e di nt h i st h e s i s m e a n w h i l ep r i m a r ys c h e d u l i n gm e t h o d sa r es o r t e d ； s o m em o d e l i n gm e t h o d sa n dp r e s e n tr e s e a r c h i n gs t a t u sd e a l i n gw i t h u n c e r t a i n t ya r eg i v e ni nd e t a i l s t h e ns o m eu n c e r t a i n t i e sa n dt h e i ri m p a c to n s y s t e m sp e r f o r m a n c ea r ee x p a t i a t e d ；t h en e c e s s i t yo ff i n d i n g ak i n do f s c h e d u l i n gm e t h o dw h i c hc a l l m a i n t a i nb e t t e rp e r f o r m a n c ew h e ns y s t e m s p a r a m e t e r sa r ed i s t u r b e d b a s e do nt h i sc o n c e p t ，am a t h e m a t i cm o d e lo f r o b u s ts c h e d u l i n gw h i c hc o n s i d e r e dw o r s t - c a s ea b s o l u t ed e v i a t i o nj ss e tu p b yu s i n gm o n t ec a r l om e t h o dr a n d o m l ys a m p l i n gu n c e r t a i np a r a m e t e r s ，a n d ag a - b a s e do p t i m a la l g o r i t h mi sg i v e n a c c o r d i n gt or o b u s ts c h e d u l i n gt h a ti sg i v e ni nt h i st h e s i s ，s o m et y p i c a l e x a m p l e sa r es e l e c t e dt oa n a l y z et h es c h e d u l i n gp r o c e d u r e ，a n dar o b u s t s c h e d u l i n gs t r a t e g yc o n s i d e r i n gt h ep r o c e s s i n gt i m ew i t hs o m ed i s t r i b u t i n g c o n d i t i o ni sf o u n do u t ；as i m u l a t i o nm o d e li ss e tu pa n dr u nb yu s i n gq u e s t ， w h i c hi sa na d v a n c e dd i s c r e t es i m u l a t i o ns o f t w a r e s i m u l a t i o nr e s u l t s i n d i c a t et h a tt h es y n t h e t i cp e r f o r m a n c eo f r o b u s ts c h e d u l i n gi sb e t t e rt h a nt h a t o fs t a t i ca n dd y n a m i cs c h e d u l i n g k e y w o r d ：f l e x i b l em a n u f a c t u r i n gs y s t e m ，r o b u s ts c h e d u l i n g ，g e n e t i c a l g o r i t h m ，o p t i m i z e i i 第一章绪论 1 1 柔性制造系统调度问题 制造业是国民经济的支柱产业，它对一个国家的经济地位和政治地 位具有至关重要的影响，因而在21 世纪的工业生产中具有决定性的地 位与作用。 随着世界进入信息时代，制造业面临着新的挑战，主要问题是：制 造业所处的环境是不断改变和难以预测的，本质上是一种湍流、混沌的 环境。用户对产品的需求千变万化，各不相同。产品被认为是在原始资 料上赋予顾客需求信息及相关制造知识的产物。由此可见，今后的产品 是按特定顾客的特殊需求设计与制造的。由于每一产品都不相同，其生 产加工过程也各不相同，因而企业面临着不断设计新产品、不断重构制 造系统的需求。为此，企业需要不断改变经营过程。在这种情况下，生 产模式已经转向以多品种、中小批量为主要模式口j 。 柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m s ，f m s ) 是为解决多 品种、中小批量生产而发展起来的一种自动化生产方式。目前，对f m s 还没有统一的定义，比较权威的定义如下： 美国制造工程师协会的计算机辅助系统和应用协会把f m s 定义为 “使用计算机控制、柔性工作站和集成物料运贮装置来控制并完成工件 族某工序或系列工序的一种集成制造系统”【2 】。 根据上述定义，不难看出f m s 的些共同特点，如表1 1 所示 表】f m s 的共同特点 硬件两台以上数控机床或加工中心及其它加工设备 f一套能自动装卸的运储系统包括刀具的运储和工件原材料的运储 一套计算机控制系统 软件l运行控制 质量保证 数据管理和通信网络 功能能自动完成多产品多工序的加工 物料系统可以实现工件的自动供给和装卸，以及自动传送、调运和 储存的功能 有刀具的自动补充，工件的自动识别，以及清洗和处理冷却液的功 能 有对系统的运行状况、加工状况，加工循环、工具状况等在线监控 和管理功能 国内外f m s 应用实践表明，作为多品种、中小批量的一种生产模 式，f m s 在提高生产率和产品质量、保证交货期、提高系统可靠性、 加强企业应变能力等方面已取得很大效益f 3 】。从宏观看，f m s 技术可以 进一步提高产品质量，提高设备利用率，使管理科学化以及提高企业的 竞争能力。 f m s 虽然可以取得很大效益，但是f m s 的效益和优点是潜在的。 单纯将f m s 的硬件设备组成一个系统，并不一定就能取得满意的效果， 在实际中，还必须以有效的系统运行管理措旋为保证。在车间生产过程 中，f m s 的生产调度在f m s 的运行管理中起着核心作用，是整个f m s 的大脑，是f m s 中最主要也是最重要的任务之一。f m s 调度是指在f m s 环境下，根据单元的实际运行状态，为完成单元生产计划而做出的具体 实施计划。其目标是通过对制造过程中物流的合理调度，缩短产品的制 造周期，减少在制品，降低库存，提高生产资源( 特别是主要设备) 的 利用率，从而提高f m s 的生产效益和效率。 具体的车间调度作业是对一个可用的加工机床集在时间上进行加 工任务集分配，以满足一个性能指标集。从数学规划的角度看，车间调 度问题可表达为在等式或不等式约束下，对目标函数的优化。典型的车 间调度问题包括个要完成的作业集，每个作业由一个操作集所组成， 各操作的加工需要占用机床或其它资源，并且必须按一些可行的工艺次 序进行b f l i ；每台机床可加工工件的若于操作，并且在不同的机床上能 加工的操作集可以不同。调度的目标是将作业合理地安排到各机床，并 合理安排作业的加工次序和加工开始时间，使约束条件被满足，同时优 化一些性能指标。 1 2 车间调度问题的分类 1 按生产过程可分为j o b s h o p 问题和f l o w s h o p 问题 在f l o w s h o p 系统中，每个工件以相同的顺序在所有机器上加工， 而在j o b s h o p 系统中，n i 某一个工件所需机器的集合一般是不同的， 加工顺序可以是任意的，但必须预先指定【4 l o 2 按作业加工特点可分为静态调度和动态调度 静态调度是指在生产加工尚未开始以前，根据系统的原始资料信 息，对生产过程进行详细规划；而动态调度是指在生产加工进行过程中， 由于加工状态和加工计划出现偏差而导致系统无法按计划运行下去而 采取的重新调度措施。一般来说，因为系统本身和环境都是变化而不能 精确把握的。因而f m s 更是很难按照理想的情况运行，经常会有各种 各样的突发事件，所以对于f m s 来说，研究其动态调度问题具有重要 的意义。同时不难看出，在偏差出现之前，系统还是需要按照静态调度 的规划运行，而且动态调度也是在静态调度的基础上进行的，鲁棒性好 的静态调度会在突发事件发生时减少动态调度的工作量。因此，在f m s 中，静态调度和动态调度的研究都是必要的，试图以静态调度取代动态 调度或动态调度取代静态调度，只利用一种调度方法来解决f m s 的调 度问题都是不合理的。 3 按调度性能指标可分为成本优化调度和时间优化调度【5 】 成本优化调度就是在系统运行期间尽量小的消耗成本，例如提高机 床利用率、减少中间库存等等，丽时间优化调度主要包括优化系统生产 周期、最小化系统运行总延迟、拖期最小化等等。 4 根据生产环境的特点，调度问题分为确定性调度和随机性调度问 确定性调度模型假定，在调度开始前，所有的任务的参数都可以精 确指定，允许任何调度决策的输出精确地确定。模型的目标就是优化系 统的性能使之产生最好的输出。而事实上在调度系统中，任务的各个参 ! 丝! = 兰兰型! ! ：堂些堡兰 ! ：堕塞堑兰! ! 苎墅坐望墨竺鱼堂堂堂! ! ! 兰l 数都不会是固定不变的，系统存在着大量的不确定因素，可以描警为篓 砸最从一定的统计规律或者分布在一定的区间内。目前处理不确定因素 的调度方法有动态调度方法和随机调度方法。 5 根据产生调度的方式可分为预测( p r e d i c t i v e ) 调度和反应( r e a c t i v e ) 调度 预测调度根据生产过程开始前系统给定的需求和约束来产生最优 调度。绝大部分调度都是用预测调度方法产生的。而反应调度是根据系 统参数发生的改变。动态地修改已经产生的调度来适应环境变化。 1 3 调度问题研究方法综述 1 3 1 确定条件下的调度模型 1 、线性规划模型：线性规划模型是最初使用的模型，问题的描述 比较简单，只能解决一些简单的问题，由于经过线性化处理，适用范围 较窄。 2 、非线性规划模型：同样只能解决一些较为简单的问题，但适用 范围较大。 3 、混合线性规划模型f 7 】：很多最优化模型中，目标函数和约束条 件中不仅有连续变量，而且有取值仅为整数的变量，即整数变量，这类 模型被称为混合整数线性规划模型。 4 、混合整数非线性规划模型：较混合整数线性规划模型而言，该 方法解的适用范围较大，很多非线性最优化问题不仅包括连续变量，而 且包括整数变量或离散变量。这类问题有广泛的应用，并被描述为混合 整数非线性规划问题。 5 、代数模型f 8 】：采用代数模型的方法来描述和求解问题，目前主 要用在理论分析方面，离散事件动态系统( d e d s ) 是一类典型的代数求 解方法。 ! ! 墨要兰兰塑! ：堂些堡兰 ! ：塑室兰：羔! 墨丝型丝墨竺篓竺! 苎! 鉴型壅 】3 2 不确定条件下的调度模型 1 、随机调度( s t o c h a s t i cs c h e d u l i n g ) 模型1 9 - 1 2 ：在处理任务加工时 间变化和机床故障等车间扰动情况下，随机调度模型从概率论的观点出 发，将任务属性参数视作独立的随机变量，并且这些变量都有已知的分 布函数，典型的假定是： ( 1 ) 机床的正常运行时间受到某种( 一般为指数) 分布的扰动： ( 2 ) 任务加工时间受到某种( 一般为指数、正态和均匀) 分布的扰动； ( 3 ) 机床故障发生和修理时间服从某种( 一般为指数和均匀) 分布： ( 4 ) 交货期延迟i a t ( i n t e m a la r r i v a lt i m e ) 从某种分布。 实际的参数值只有在调度决策制订后才能确定。因此，调度决策的 输出取决于不确定任务属性的特定实现，随机调度模型的目标一般是优 化系统性能的期望。 随机调度模型能在一定的条件下处理不确定因素对系统性能造成 的影响，在实际应用中也取得了较好的效果，但是随机调度所依赖的上 述假定并不总是能够满足，恰恰相反，实际的车间环境中，任务属性参 数的分布往往是不可知的或者是不精确的。另外随机调度模型要求待评 估性能指标的期望值作为目标评价函数，由于各个随机变量之间的关系 十分复杂，很难找到这些随机变量于待评估性能指标之间的函数关系， 也就难以计算其期望值，只能用近似的方法来解决。 2 、动态调度模型m 1 ：包括重调度方法1 1 4 - 1 5 1 和滚动调度方法【1 6 - 1 7 。 重调度依据系统的动态信息，针对当前的状态，对以后的生产活动作出 调度及协调，使系统能在动态环境下高效运行。通常重调度可以在线方 式进行，对生产进度的安排要比一次性的稳态调度方法更加及时、可靠。 滚动调度是借鉴连续系统中预测控制的基本原理，能跟踪系统的动 态变化。实际f m s 加工环境中充满了随机和不确定因素，一次性全局 最优的静态调度虽然可得到理想的最优结果，实际上并不能适应动态环 境。滚动调度通过在线优化每个滚动区间，使系统在此区间内达到最优。 滚动调度的主要思想是滚动优化。 ! ! i 里苎蔓竺主兰垡笙兰 ! ：塑塞堑兰! 墨丝型堕至竺竺堡型些! ! 盟 1 3 3 常用的调度方法 一、纯数学方法： 1 、运筹学方法：包括线性规划、非线性规划、动态规划方法。早 期的研究带有强烈的数学性质和控制目的，研究手段多采用一些基于数 学理论的方法和控制理论方法。这些方法对资源和加工工件之间的关系 进行数学建模，荐用数学理论中较成熟的方法进行求解，求得工件加工 和资源分配的最优策略。但这类方法的模型描述能力有限，建模时不得 不对真实环境进行大量的简化。并且，其最优解是时间随问题规模呈指 数倍增长的n p h a r d 型的。因此只能对小规模的系统求解，不适合真实 系统问题。 2 、分支定界法：分支定界法是以合理地列举最优化问题的一切 可能解的思想为依据的。恰当的限制条件在这里是很重要的。它基于逐 次划分解空间，力求构造出一个解是最优的证明。 二、基于离散事件动态系统( d e d s ) 的模型方法 由于制造系统是一类典型的离散事件动态系统( d i s c r e t ee v e n t d y n a m i cs y s t e m s ) ，因此可以用研究d e d s 模型方法去探讨车间调度问 题，诸如排队论、极大极小代数模型等。 车间调度中的排队论方法是一种随机优化方法，它将每个机床看成 一个服务台，将每个作业作为一个客户。文【1 9 】用带有限缓存的排队网 络来描述带有有限存储容量的f m s 。总的说来，排队网络模型由于从 随机统计的角度来描述f m s ，难以表述系统中存在的某些特性( 如很小 的缓存空间和服务时间非指数分布等) ，同时很难解决系统中可能有故 障发生等问题。 p e t r i 网作为一种图形建模工具可以形象地表示和分析f m s 中加工 过程的并发和分布本质，以及多项作业共享资源时的冲突现象，具有很 强的建模能力，对于描述系统的不确定性和随机性也具有一定的优越 性，其在自动制造领域的应用综述见文献【2 0 。文【2 1 】中使用赋时p e t r i 网为f m s 建模，通过优化变迁的发生序列来产生的搜索可标识集，从 而得到较优的调度结果。目前，p e t r i 网模型用于f m s 的调度还存在以 下的问题： ! ! i ! 苎兰丝 ! ：兰丝堕苎 ! ：塑塞兰苎! 蔓型坐兰墨竺童羔坐塑型些兰 1 、- 节点语义的单义性，使得所携带的系统信息量不够丰富。x 2 1 重用性差。p e t r i 网大多是基于f m s 中作业的加工流程建模，当 作业需求或工艺稍有变动，必须改模型结构。 3 ) 很难对复杂调度规则建模。 三、基于启发式规则的调度方法 调度规则因其易于实现、计算复杂度低等原因，能够用于动态实时 调度系统中，许多年来一直受到学者们的广泛研究，并不断涌现出许多 新调度规则。文【2 2 】中列举了常见的2 0 条规则，并针对一个实际的f m s ， 分析了这些规则对系统性能如作业的平均等待时间、机床的平均利用 率、作业总加工时间等的影响。表1 2 列举了部分常见的调度规则。 虽然启发式规则调度简单易行，但众多的研究表明，任何一条调度 规则都难以适合于动态多变的f m s 调度环境和调度任务。采用优先级 方法时，规则的优先级很难确定1 2 3 】。 四、仿真调度方法 由于制造系统的复杂性，很难用一个精确的解析模型来进行描述分 析。而通过对仿真模型的运行收集数据，就能对实际系统进行性能、状 念方面的分析，从而能对系统采用合适的控制调度方法。基于仿真方法 坐! 查星兰兰堡! ：兰竺堡兰 ! ：些塞堑堡! 耋丝! ! 垄墨竺鱼堡型! 堂一 虽然可以包含解析模型无法描述的因素，并且可以提供给使用者个调 度性能测试的机会，但其不可避免地存在以下问题f 4 】： 仿真的准确性很大程度受主观因素影响； 必须结合其它调度方法，否则无法很好地单独解决问题，缺乏理 论依据： 随着模型复杂度的增加，时间和费用也大量增加； 单从仿真结果分析，很难得出参数与性能之间的函数关系。 五、人工智能方法 l 、基于模拟退火算法的调度方法 模拟退火的思想最早由n m e t r o p o l i s 等人在1 9 5 3 年提出幽j 。模拟 退火算法是基于m o n t ec a r l o 迭代求解法的一种随机寻优算法，其出发 点是基于物理学中固体物质的退火过程与一般组合优化问题之间的相 似性。模拟退火法在某一初温下，经过不断的降温，在全局解空间中随 机寻找最优解，不但接受对目标函数有改善的状态，还以某种概率接受 使目标函数恶化的状态，即具有爬山功能，能够爬出局部最优解，从而 比较有效地进行全局搜索。文f 2 5 】利用模拟退火算法求解单机作业下任 务加工时间为模糊区间数的提前拖期调度问题。 2 、基于遗传算法的调度方法 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一 种自适应全局优化概率搜索算法。它最早是由美国密执安大学的 h o l l a n d 教授提出，起源于6 0 年代对自然和人工自适应系统的研究【2 “。 7 0 年代d ej o n g 基于遗传算法的思想在计算机上进行了大量的纯数值 函数优化计算实验唧。在一系列研究工作的基础上，8 0 年代o o l d b e r g 进行归纳总结，形成了遗传算法的基本框架【2 8 2 9 1 。遗传算法是一种并行 优化算法，通过群体间的相互作用，保存已搜索到的信息，这是基于单 次搜索过程的优化方法无法比拟的。文【3 0 3 3 利用遗传算法求解 f j o w - s h o p 问题，文 3 4 4 3 利用遗传算法求解j o b s h o p 调度问题，文 4 4 】 利用遗传算法求解f m s 调度问题。 3 、基于人工神经网络的调度方法 ! i i ! 苎兰生! ! ! 兰竺堡兰 ! ：塑塞兰：兰! 篷堡兰塑垒墨竺笪竺型堕盟 h o d f i e l d 神经网络模型的提出为求解各种有约束优化问题开辟了一 条新途径。用h o p f i e l d 网络解决t s p 问题就是其在组合优化问题中的 最成功的应用之一。f o o 等人提出了一种利用随机h o p f i e l d 网络来解决 j o bs h o p 调度问题的方法，另外为了解决大规模问题，他们又提出一种 改进的t a n k 和h o p f i e l d 网络的整数线性规划神经网络来解决j o b s h o p 调度问题。 4 、基于知识的f m s 智能调度方法 近年来，基于知识的智能调度吸引了大批专家和学者的注意。它能 根据系统当前的状态和给定的优化目标，对知识库进行有效的启发式搜 索和并行模糊推理机制，避开了繁琐的计算，并选择最优的调度策略， 为在线决策提供支持，可充分开发f m s 的能力和内在柔性i l ”。由此可 见，智能调度系统将会给f m s 调度问题的进一步发展提供可行的方向。 但是，由于人工智能( a r t i f i c i a li n t e l l i g e n c e ) 技术本身发展水平的限制， 由计算机实现的基于知识的f m s 智能调度系统大多是结构不良的，即 目标、任务范围、计算机允许的操作都不具有明确的含义，主要表现在 系统中的知识是不完备或不一致的l l ”。 1 4 不确定因素下调度的研究现状 柔性制造系统的调度中存在如下的不确定因素，但在实际调度过程 中没有考虑 4 5 - 1 7 】： 任务加工时间的不确定性 机床故障发生的不确定性 资源瓶颈的位置的动态性 生产批量的不确定性 制造资源可用性的不确定性 由上述分析可知，当前的柔性制造系统调度面i j 刍着大量的不确定因 素，而忽略这些不确定因素制定出来的调度策略往往运行在偏离理想点 较远的位置，极大的降低了系统的性能。目前的研究主要集中于处理加 工时问和机床故障的不确定。 这方面的研究热点之一是动念调度( d y n a m i cs c h e d u l i n g ) 方法，将 不确定条件下的调度问题转化成确定条件下的问题来解决，当系统受到 扰动时，根据系统当时状态，对系统进行重调度，这种方法能够及时的 反应系统的变化，有良好的敏捷性，但由于系统较复杂，动态重调度需 要消耗大量的计算时间，不能保证实时的调度决策，使得系统运行成本 大大提高，同时当系统参数变化较为频繁时，动态调度方法使得性能指 标变化频率和幅度也相应变大，这将造成系统运行的不稳定，这对于那 些要求系统稳定性的场合是不适宜的。 另外种方法是随机调度方法，它属于静态调度方法，中心思想是 将扰动的参数视作独立的随机变量。利用统计概率的方法处理扰动问 题其优化目标是期望系统性能。在这方面，g l a z e b r o o k l 4 ”，p i n e d o 和 r a m m o u z 4 9 1 ，a l l a h v e r d i 和m i t t e n t h a l l 5 0 j ，d u 和p i n e d o t ”j 等人做了大 量的研究，取得了一定的效果。但是，随机调度方法的优化目标是一个 期望值，其目的是希望系统性能在参数受到扰动后的平均值最小，在随 机调度的目标函数之中仍然没有考虑系统稳定性，这是它的一大缺陷： 另外，随机调度方法是假定这些随机变量的分布函数已知，同时因为调 度系统的性能评价指标往往是这些随机变量的函数，要想求它的期望值 就必须预先知道这个函数，然而实际环境当中这个函数是很难甚至是无 法得到的，因此随机调度处理的问题或者比较简单或者需要对优化目标 函数进行大量的简化，其效果往往不尽人意。 另一类方法是建立含有不确定因素的调度模型来求解，这方面的研 究相对较少，而且目前研究的也是比较简单的问题，例如j o a q u i n a c e r e d o 等在模型中加入描述不确定因素的变量，建立了线性规划模型， 变量在给定的范围内变化胪2 j ；c o t t 和m a c c h i e t t o ，i s h i i 和m u r a k i 利用“时 移法”以加工时间的变化对系统的影响作为目标函数，根据对未来过程 状态的预测信息动态地将产品的开始生产时间前移或后移【5 4 1 ，然而当系 统变得复杂后，我们很难精确得表达参数变化对系统的影响；n a v e e n k v e l a g a p u d i 等给出了用来描述系统调度品质的调度鲁棒性概念，研究 了制造系统的鲁棒性问题，给出了影响系统鲁棒性的因素【5 5 j ；j t t r g e n d o r a 等利用模糊集来表达参数不确定性和模糊性，将所有任务的平均 重要程度与所有约束的满足程度的加权平均作为优化目标【5 6 】，同样，系 统旦变得复杂了，各个约束之间的相互耦合关系将影响到它们的满足 程度的取值；e u i s e o kb y e o n ，s d a v i d 等人利用图分解理论来解决j o b 坐! 塞堑兰兰堡生堂竺堡苎 ! ：塑塞堑堡! 整丝型堕墨竺叁堡型些塑壅 s h o p 鲁棒调度问题的方法，在调度初期，建立调度问题的分离图 ( d i s j t i l l c t i v eg r a p h ) ，然后对图进行预处理，将一个j s p 问题分解成一 系列子问题，在整个调度期内利用动态调度方法分别解决这些子问题， 最终实现整个鲁棒调度 5 7 1 。图分解理论能直观地表达调度系统的结构和 运行过程，但是如何分解j s p 问题及不同的分解方案之间的优劣评价是 困难的；r s h a f a e i 和p b r u n n 等研究了大量的启发式调度规则的鲁棒性 问题，文中考虑了任务到达时间、交货期延迟和车间负载状态等因素对 用上述启发式规则产生的调度策略性能的影响，优化日标是系统运行成 本1 5 8 】：k e v i nj d o o l e y 和f a r z a dm a h m o o d i 利用t a g u c h i 试验仿真方法研 究了几种典型的启发式调度规则对系统性能的影响1 59 1 。但众多的研究表 明，虽然启发式规则调度简单易行，但是任何一条调度规则都难以适合 于动态多变的f m s 调度环境和调度任务，不能用来作为主要的调度方 法，应该寻找其它更为有效的调度方法来处理不确定环境。 从上面的文献综述中我们可以看出，动态调度和随机调度方法虽然 在解决不确定环境方面取得了一定的效果，但是它们的总体效能仍然不 能令人满意：对不确定环境的另外一些尝试所取得的成果，促使我们去 寻找一种更为适宜的调度方法来处理车间内的不确定环境。这种调度方 法应该能够恰当地表达不确定因素对系统性能的影响，尽可能地即保持 良好的系统性能评价指标值又使系统运行稳定，同时还能减少计算工作 量，降低运行成本。 要获得高质量的产品和好的经济效益，要求生产能够适应生产的快 速变化，处理好出现的不确定因素，只有这样才能保证生产计划的切实 执行。大约十年前，g r a v e s 认为，作为未来调度的研究方向，要想理解 调度的鲁棒性，就必须明确地考虑制造系统中的不确定信息6 3 】，鲁棒调 度方法正是从这个角度去处理调度问题的。 1 5 本论文的研究内容 本章的前面部分我们对柔性制造系统调度中存在的问题进行了回顾 和分析，对于不确定环境下的调度问题的求解仍然是当前人们研究的热 点，在本文中我们希望利用鲁棒调度的方法从另外一个角度来解决这个 问题。这篇论文的主要研究内容及实施步骤是： 不确定因素分析 对所研究的随机生产环境下的柔性制造系统中 存在的大量不确定因素进行系统的分析并归类然后找出对系统调度性 能影响较大的主要不确定因素，初步分析这些因素对系统性能的影响， 将其作为鲁棒调度系统建模的依据和处理对象。 建立鲁棒调度模型根据上述不确定因素度系统性能的影响方式及 其概率分布函数，我们在调度目标中明确地加入对这些不确定因素的描 述信息，建立这些因素存在条件下的鲁棒调度模型。考虑到实际的调度 环境中的不确定因素经常是同时存在的，本文将研究调度系统中，所有 任务的加工时间都发生某种程度的扰动的情况，建立多个扰动同时存在 的鲁棒调度模型。 优化计算建立了鲁棒调度模型以后，利用遗传算法寻找鲁棒最优 解。这部分的主要工作是对本文的调度问题确定遗传编码方法，选择合 适的适宜度函数和选择、交叉和变异算予，并最终编程实现。 仿真研究及鲁棒性评估利用遗传算法找到的鲁棒最优调度策略与 确定情况下的最优调度策略在不确定情况下进行仿真研究，主要利用离 散事件仿真软件q u e s t 建立鲁棒调度的仿真环境与模型，仿真得到的 数据利用m o n t ec a r l o 实验设计方法计算它们的期望值与方差，利用本 文中定义的鲁棒性综合评判指标进行性能评判。利用更接近于现实的环 境及大量的仿真数据验证本文提出的鲁棒调度策略的鲁棒性，鲁棒调度 的理论价值及其实际可行性。 注：本文受到国家自然科学基金项目：“自动化制造系统的稳健性优 化设计”( 5 0 1 7 5 0 0 1 ) 的支持。 1 6 论文安排 第一章：绪论。介绍了柔性制造系统的特征和生产计划和调度在系 统中的地位，主要的调度方法。介绍了调度模型的分类，并给出了当前 处理不确定因素的几种建模方法，详细的分析了不确定因素条件下调度 的研究现状。 第二章：生产调度中的不确定因素分析。根据国内外研究调度不确 ! ! 苎堑兰兰堕! ：堂丝丝兰 ：塑塞! ：堡i 墨丝生! 垄至竺堑堡型些型壅 定因素的相关文献的研究成果，总结了那些对系统性能的影响较大的不 确定因素，作为鲁棒调度的研究内容。 第三章：加工时间不确定情况下的鲁棒调度问题。利用实际存在的 任务加工时间的概率统计特征，加入调度模型中，建立鲁棒调度的数学 模型，并用遗传算法进行了优化计算。 第四章：仿真研究与鲁棒性评估。对得到的鲁棒调度策略利用 q u e s t 进行仿真试验，利用m o n t ec a r l o 实验方法对本文提出的鲁棒调 度策略的有效性和可行性进行了综合评判。 第五章：总结与展望。总结论文的工作，并且指出本论文研究工作 的不足之处，提出未来此领域的研究方向和研究内容。 第二章生产调度中的不确定因素分析 2 1 引言 f m s 可以模块化为由机床、装卸工饿、缓冲存贮区以及物料和刀具 传输系统等基本要素所构成。具体的f m s 的组成为： m 台机床。每台机床均能完成不同种加工工序 容量一定的公用存贮，它也可作为装卸工作站 每台机床拥有一定容量的缓冲站 具有几台运输设备的物料运输系统 中央刀库 每台机床有一定容量的局部刀库 具有几台刀具输送设备的刀具运输系统 该模型的运行假设为 个工件不能同时在两台机床上加工，或一台机床不能同时加 工两个工件 机床具有柔性，可完成多道工序的加工 每一工件以其自身特定的加工工艺路线接受加工 j u t 周期和运输时间是确定的，或是分布已知的随机数。 f m s 中的机床或设备因某种原因处于空闲状态势必造成资源浪费， 效率的降低，f m s 的集成生产控制的作用便是把这种浪费减少到最低 程度，达到以多品种、中小批量生产方式逼近大批量生产的效益。用调 度系统对f m s 进行生产的调度及控制，是f m s 设计和运作中一个必不 可少的组成部分。解决生产综合自动化问题的核心问题是解决不确定条 件下的生产自动化。一类典型的生产计划和调度信息流如图2 1 所示。 图中，需求分析模块调查市场物资价格、种类，人力资源等信息为 生产计划的制定做好准各：生产计划模块根据市场需求及订单决定产品 的批量和类型等计划信息：生产调度模块根据计划信息决定工序序列， 坐! 墨星兰坚堕上兰些堡兰 ! ：塑塞堑兰! 墨堡型丝至丝生型! i 翌堕 加工时间等调度信息；生产实施则根据生产调度信息进行实际的生产， 其中实际的加工时间，设备故障情况直接影响到调度结果的因素。 由图可见，当计划信息确定的时候，一个好的调度策略应该给出合 理的加工工序序列，加工时间和设备使用等调度信息。但实际的生产环 市场信息 图2 1 生产计划和调度信息沉 境中不可避免的存在不确定的因素，因此要想很好的实现上述目标，就 必须考虑实际生产时间，设备故障情况等实际的生产因素。计划信息要 综合市场信息和企业的生产能力而获得，要获得一个较好的调度策略， 就必须建立包括不确定因素的信息的模型，获得不确定性信息的主要途 径是以往记录数据的统计信息。很显然，如果某一调度决策对系统中出 现的不确定因素不敏感，那么这种调度方法就是鲁棒调度。 调度是计划过程的实际检验。调度的目标是在考虑实际生产中条件 变化的情况下对生产计划的实现。这些变化包括供求关系和质量的变 动，生产过程和用户需求的变化。调度通过评估生产失效和其它变化确 定生产计划的偏移，修改原来的调度实现计划目标。 2 2 生产调度中的不确定因素分析 2 2 1 不确定因素分类 随机环境下的生产系统是十分复杂的，难以避免的会存在很多的不 确定因素，而现存的调度方法却忽视了这类因素，这些不确定因素产生 的原因主要包括【5 】： 对未来生产活动的预测方法不完善； 生产计划是按照不准确的预测值制定的； 制定工艺规划、日程计划时都是按标准值来计算，与实际情况有 差别； 在计划实施过程中，可能出现随机扰动，如设备故障、操作者缺 勤等： 原材料或其它生产要素短缺； 操作错误出现不合格品等。 按照不确定因素的数学描述可分为以下三类： 1 不确定性服从一定的概率分布，如加工时间、任务到达时间间 隔的变化，在数学模型中引入了随机变量来描述 2 不确定性变量、处于某一区间，在数学模型中引入松弛变量来 描述 3 不确定性变量是一些离散的值，主要是设备可用性或者故障等 等 2 2 2 不确定因素分析 如前所述，柔性制造系统的调度中存在如下的不确定因素 任务加工时间得不确定性 机床故障发生的不确定性 资源瓶颈的位置的动态性 生产批量的不确定性 1 6 坐! 墨g 苎兰堕! ：兰些笙兰 ! ：堕塞兰：兰工墨丝型垄墨竺量生塑生! 型堕 制造资源可用性的不确定性 调度规则因其易于实现、计算复杂度低等原因仍然在调度领域广泛 的应用，k e v i nj d o o l e y 和f a r z a dm a h m o o d i 利用t a g u c h i 试验仿真方法 研究了几种典型的启发式调度规则对系统性能评价指标的影响【4 甜。 在这个实验中，考虑的调度规则由表2 1 ，表2 2 给出 表2 1 调度规则 1 2 t w k n o p 交货期分配过程中的总工作量 交货期分配过程中的工序数量 由调度规则和交货期分配规则相互组合，构成可控因素。 考虑的不确定因素包括：瓶颈资源( 存在，不存在) ，任务到达时 间间隔( 大、小) ，任务加工时间分布( 指数分布、e r l a n g 分布) 和车 间规模( 5 台机床、7 台机床) 。 考虑的评估准则包括：系统时间和交货期延迟。 实验中的符号定义如下： y ( p ，q ，r )第p 种可控因素，第g 种扰动因素实验状态下，第，次 实验的性能评价指标的平均值 s 2 ( p ，q ，)可控因素第p 种，相应扰动因素的第q 种实验状态下， 第，次实验的性能评价指标的偏差值 性能评价指标的平均值( v ( y ( p ，r ) ) 定义为所有y ( p ，q ，) 的平均值， 性能评价指标的偏差值( s2 ( p ，) ) 定义为所有s2 ( p ，q ，) 的平均值： 平均值的鲁棒性定义为平均值v ( y ( p ，r ) 的标准差，偏差的鲁棒性定义为 偏差s2 ( p ，r ) 的标准差。 仿真1 0 次后得到的结果如表2 3 所下 由上面的表可以看出，首先用e d d 和n o p 的组合降低了系统时间 和交货期延迟的平均值。关于性能评价指标的偏差的平均值，f i f o 规 则很好地降低了系统时间和延迟偏差值，而n o p 规则极大地降低了延 迟的偏差值。考察性能评价指标的平均和偏差的鲁棒性影响，我们可以 得出结论：对于性能指标的平均值( 系统时间和延迟) 来说，e d d 和 t w k 的组合是鲁棒的，对于性能指标偏差的鲁棒性来说，e d d 对系统 时间是鲁棒的，并且或者是( f i f o ，t w k ) 或者是( e d d , n o p ) 的组合 对延迟来说是鲁棒的。 r s h a f a e i 和e b r u n n 等研究了大量的启发式调度规则( 见表2 5 ) 的 鲁棒性问题，文中考虑了任务到达时间、交货期延迟和车间负载状态等 因素对用上述启发式规则产生的调度策略性能评价指标的影响，优化目 ! i 墨垂苎兰堕! 兰丝堡兰 ! ：堕壅兰：兰! 兰堂型兰墨竺! 坐塑鉴! ! 旦 标是系统运行成本。 表2 5j o bs h o p 调度规则列表 符号说明：t 为调度决策时间，i 是平均任务加工时间，识是任务f 的未完成工序集合，d d 任务f 的第个工序的交货期，a ( 丁) 是基于任务 调度决策时间丁的优先权顺序的临界比，c j 是任务f 的期望延迟成本。 不确定因素中分别考虑了加工时间扰动( 其扰动程度分为五个不同 的等级，等级越高表明扰动程度越大) ，机床故障( 假定故障发生时间 间隔服从指数分布) ，任务到达时间扰动( 假定服从泊松分布) ，车间负 载程度( 中等程度、重度) ，交货期松紧程度等。 仿真结果表明，车间扰动对不同调度规则的影响是不同的，即不同 的规则对扰动的敏感程度不同：车间负载程度对调度的鲁棒性有很大影 响，当车间负载增大时，调度的鲁棒性下降；同样的，当瓶颈资源存在 时，调度的鲁棒性也将明显下降，这就需要调整相应的生产计划了；当 ( 加工时间和机床故障等) 扰动程度增大时，调度的鲁棒性能也会下降。 从以上两个实验中我们可以得出如下结论 1 不同的调度策略对系统参数扰动有着不同的敏感程度，也就是 说