（系统工程专业论文）生产环境不确定条件下的生产调度优化.pdf

山东大学硕士学位论文 摘要 生产调度是企业生产运行的指挥中心，提高生产调度的质量和效率对于提高 企业的经济效益和社会效益会起到重要的作用因此，开展生产调度领域内研究 是非常必要的，这些研究也必将具有重要的理论意义和实际价值。 调度问题是为实现某一目的而对共同使用的资源实行时间分配的问题。被证 明是n p 难题后，对其的研究主要集中于确定型生产调度问题，即必须对真实环 境进行大量简化和假设，导致模型无法完整表达已知信息和模型失真。如何通过 数学方法来降低或者消除生产环境扰动对生产调度方案造成的影响是本文研究 工作的重点本文主要从两种思路来解决生产环境不确定问题。l 、在预调度建 模期间使用机会约束把不确定因素包含到模型中，在满足一定稳定度的前提下， 寻求最优调度方案；2 、当优化调度方案已经制定，使用优化后分析的方法得出 影响调度性能的关键参数，通过严格控制关键参数变化，来保证调度执行的稳定 性。 本文主要贡献主要包括以下内容： 首先，本文分析和讨论了生产环境中影响生产调度的各种不确定因素的性质 和分类，给出了不确定因素的基本测度，从不确定性表达入手讨论了基于不确定 规划生产调度模型中的机会约束及其等价类之间的转换关系，从而为降低模型复 杂度、提高模型求解效率，提供了理论依据和可行方法。 其次，本文通过统一集理论引出多重不确定的测度定义，并使用多重机会约 束来表达生产调度稳定度约束，建立基于稳定度的不确定生产环境下的生产调度 模型，该模型不仅可以保证了调度结果的质量，而且提高了调度方案可行性，具 有较高的应用价值。 再次，本文建立了生产环境不确定条件下生产调度区间规划模型，通过讨论 区间规划模型中各种约束性质的变化来分析模型中的决策参数与最优解之间的 函数关系，得出调度性能指标与决策参数之间的变化规律，为调度人员通过控制 关键参数保证调度稳定提供了理论指导 最后，本文论述了当前流程工业生产调度系统应用所需要的关键技术以及难 i l l 山东大学硕士学位论文 点，并以国家8 6 3 项耳( 2 0 0 1 a a 4 1 3 4 2 0 ) “复杂流程工业的实时优化调度与先进集 成控制技术”为实例，分别讨论了建模语言、方程模型库设计以及算法库设计的 具体方案，为生产调度系统在流程工业中的应用提供了框架。 关键词：生产调度；不确定性；机会约束；优化后分析 i v 山东大学硕士学位论文 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 gi st h eh e a d q u a r t e r so fp r o d u c t i o nr u n n i n gi ne n t e r p r i s e s t h e r e f o r e ，i t sn e c e s s a r yt oc a r r yo nr e s e a r c h e s o np r o d u c t i o ns c h e d u l i n gi nt h e p r o c e s se n t e r p r i s e ，w h i c hw i l lh a v ei m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a l v a l u e s s c h e d u l i n gi st i m ed i s t r i b u t i o nt os h a r e dr o s o u l c ei no r d e rt or e a l i z ec e r t a i n p u r p o s e s r e s e a r c ht op r o d u c t i o ns c h e d u l i n gm a i n l yf i x e do nd e t e r m i n i s t i cs c h e d u l i n g p r o b l e m sw h e ns c h e d u l i n gp r o b l e m sw e r ep r o v e dt ob en p hp r o b l e m s h o w e v e r , t h e r e a lw o r l dh a st ob el i m i t e d ，s i m p l i f i e da n da s s u m e d ；d e t e r m i n i s t i cs c h e d u l i n gh a s f i n i t em o d e ld e s c r i p t i o na b i l i t ya n dh a st og i v eu pl o t so fu s e f u li n f o r m a t i o n , w h i c h m a y l e a dt od i s t o r t i o no fm o d e l sa n du n f e a s i b l er e s u l t s s ot h ek e yt ot h i sp a p e ri s h o wt or e d u c eo ra v o i dt h ee f f e c t so fd i s t u r b sw h i c ha r eb r o u g h tb yu n c e r t a i n p r o d u c t i o ne n v i r o n m e n t h e r et h ep r o b l e mw a ss o l v e di nt w ow a y s 1 u n c e r t a i n i n f o r m a t i o nw a sa d d e dt ot h ep r e s c h e d u l i n gm o d e la sc h a n c ec o n s t r a i n t sb e f o r e o p t i m a ls c h e d u l i n gr e s u l tt h a tw a sr e s e a r c h e dw i t hs c h e d u l i n gs t a b i l i t ya b o v es o m e l e v e lw a sa t t a i n e d 2 ，k e yc o e f f i c i e n t sw h o s eb o u n d ss h o u l db el i m i t e ds t r i c t l yw e r e g o t t e nb yp o s t o p t i m a la n a l y s i si fs c h e d u l i n gw a sd e t e r m i n e d g o o dp e r f o r m a n c e w o u l db ek e p ti f k e yc o e f f i c i e n t sh a db e e nh a n d l e dp r o p e r l y t h em a i nc o n t r i b u t i o na n dr e s e a r c hw o r k sa r ea sf o l l o w ： f i r s t ，v a r i o u sf a c t o r sw h i c hi n f l u e n c et h ep e r f o r m a n c eo fp r o d u c t i o ns c h e d u l i n g u n d e ru n c e r t a i np r o d u c t i o nc i r c u m s t a n c e sw e r ea n a l y z e da n ds o r t e d a n dt h e nb a s i c m e a s u r e so fu n c e r t a i n t yw e r ed e f i n i t e d t h et r a n s f o r m sb e t w e e nc h a n c ec o n s t r a i n t s a n dt h e i re q u i v a l e n c es h a p e si nt h ep r o d u c t i o ns c h e d u l i n gm o d e lb a s e do nu n c e r t a i n p r o g r a m m i n gw e r es h o w na n dp r o v e d , a n di t s e t t l e st h et h e o r e t i c a lb a s e sf o r s i m p l i f y i n gt h ec o m p l i c a t e dm o d e l sa n dr a i s i n gs p e e do f i t sa l g o r i t h m s s e c o n d ，t h ed e f i n i t i o no fm u l t i - u n c e r t a i n t ym e a s u r ew a sp r e s e n t e df o l l o w i n ga s t h e o r y t h e nt h ep r o d u c t i o ns c h e d u l i n gm o d e lb a s e do np r o d u c t i o ns c h e d u l i n g s t a b i l i t yu n d e ru n c e r t a i np r o d u c t i o nc i r c u m s t a n c e sw a sb u i l tb yu s i n gm u l t i - u n c e r t a i n c h a n c ec o n s t r a i n t s i tn o to n l yg u a r a n t e e dt h e s t a b i l i t yb u ta l s oi m p r o v e dt h e p e r f o r m a n c eo f t h ep r o d u c t i o ns c h e d u l i n g t h i r d ，t h ei n s t a ln u m b e rc e e f f i c i e mp r o g r a m m i n gm o d e lo fp r o d u c t i o n v 山东大学硕士学位论文 s c h e d u l i n gw a se s t a b l i s h e di nt h et i l i r dc h a p t e r t h ef u n c u o nr e l m i o n s h i pb e t w e e nt h e o b j e c tv a l u ea n dd e c i s i o nc o e f f i c i e n t sw a sd i s c u s s e db yt h ea n a l y s i so fc h a n g i n go f c o n s t r a i n tp r o p e r t i e si nt h em o d e l t h e nt h er u l e sw h i c hw e r cn e e d e dt oa d j u s t p r o d u c t i o n t om a i n t a i ns c h e d u l i n gp e r f o r m a n c ew e r er e a c h e d f i n a l l y , s o m ec r i t i c a li s s u e si nt h ea p p l i c a t i o no fp r o d u c t i o ns c h e d u l i n gs y s t e m s i np r o c e s si n d u s t r yw e r el i s t e d t h en a t i o n a l 8 6 3 p r o j e c t ，r e a l - t i m ep r o d u c t i o np l a n s c h e d u l i n gs y s t e m 伽p r o c e s si n d u s t r yw a su s e d a sat y p i c a l e x a m p l et o d e m o n s t r a t et h ed e s i g no fe q u a t i o nd a t a b a s ea n da l g o r i t h m s ，w h i c hs u p p l i e da f r a m e w o r kf o rt h ea p p l i c a t i o n so f p r o d u c t i o ns c h e d u l i n gs y s t e m s k e yw o r d s ：p r o d u c t i o ns c h e d u l i n g ；u n c e r t a i n t y ；c h a n c ec o n s t r a i n t s ；p o s t o p t i m a l a n a l y s i s v i 山东大学硕士学位论文 缩略词说明 a sa l ls e t 统一集 c c pc h a n c ec o n s t r a i n e dp r o g r a m m i n g 机会约束规划 c i m sc o m p u t e r - i 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 pc o n s t r a i n tp r o g r a m m i n g 约束规划 d p d y n a m i cp r o g r a m m i n g 动态规划 e se x p e r ts y s t e m 专家系统 f c c pf u z z yc h a n c e - c o n s t r a i n e dp r o g r a m m i n g 模糊机会约束规划模型 f l pf u z z yc o e f f i c i e n tl m e a rp r o g r a m m i n g模糊线性规划 f m sf l e x i b l em a n u f a c t u r i n gs y s t e m 柔性制造系统 f mf u z z ym e a s u r e s 模糊测度 g ag e n e t i ca l g o r i t h m s 遗传算法 k ck e yc o n s t r a i n t 关键约束 l pl m e a rp l a n n i n g 线性规划 l sl o c a ls e a r c h 局部搜索 i n c p pi n t e r v a ln u m b e rc o e f f i c i e n tp r o g r a m m i n gp r o b l e m 区间系数规划问题 m i l pm i x e di n t e r m e d i a t el i n e a rp r o g r a m m i n g 混合整数线性规划 m i n l pm i x e di n t e r m e d i a t en o n - l i n e a rp r o g r a m m i n g 混合整数非线性规划 n nn e m a ln e t w o r k 神经网络 n pn o n d e t e r m i n i s f i cp o l y n o m i a l 非多项式确定 n p cn o n - p o l y n o m i a lc o m p l e t en p 完全 n p hn o n p o l y n o m i a lh a r dn p 难 ， n u d mn o n - u n i f o r md i s c r e t i z a t i o nt i m em o d e l 不均匀时间划分模型 o ro p e r a t i o nr e s e a r c h 运筹学 p a p o s t o p t i m a la n a l y s i s 优化后分析 p mp r o b a b i l i t ym e a r e s 概率测度 p sp r o d u c t i o ns c h e d u l i n g 生产调度 山东大学硕士学位论文 p s sp r o d u c t i o ns c h e d u l i n gs t a b i l i t y 生产调度稳定性 r ar e l a t i o na l g e b r a 关系代数 r s r o u g h s e t粗糙集 s as i m u l a t e da n n e a l i n g 模拟退火 s p as e tp a i r a n a l y s i s 集对分析 s q l s t r u c t u r e dq u e r yl a n g u a g e 结构化查询语言 s t ns t a t et a s kn e t w o r k 状态任务网 t st a b o os e a r c h 禁忌搜索 u d mu n i f o r md i s c r e t i z a t i o nt i m em o d e l 均匀时间划分模型 u i su n i f o r mi n t e r m e d i a t es t o r a g e 无限中间存贮 u pu n c e r t a i n p r o g r a m m i n g 不确定规划 v i i i 附件一： 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名： 墨玉j日期：纽七! 上：2 z 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丑姻 导师签 山东大学硕士学位论文 1 0 引言 第一章绪论 随着我国社会主义市场经济的逐步建立，我国的企业正面临越来越激烈的市 场竞争与前所未有的发展机遇l l 】生产规模越来越大，生产过程的复杂性越来越 高，因此企业对管理和生产过程的监控都提出了更高的要求。近几十年来，各类 生产过程都已经发生显著变化，其主要特征是生产规模的大型化和生产过程的连 续化。在激烈的市场竞争中，原来简单的、局部的、常规的控制和仅凭经验的管 理已经不能满足现在工业企业的生产要求，企业管理者和工程师们当前面临的最 大问题是：根据市场上原料供应和产品需求的变化进行经营决策和组织生产；在 生产计划改变的情况下对生产过程进行控制来最大限度地发挥生产的柔性；在生 产工业不做大的改变的前提下进行管理决策，最大化企业的综合经济效益。 针对以上问题，美国的约瑟夫哈林顿( j o s e p hh a r r i n g t o n ) 于1 9 7 3 年首次提出 了计算机集成制造( c i m ，c o m p u t e ri n t e g r a t i o nm a n u f a c t u r i n g ) 的概念。计算机集成 制造将数字计算机、控制系统以及其它技术系统集成后，使企业生产计算机化、 信息化、智能化。而计算机集成制造系统( c i m s ) 正是基于这样一种思想而构建的 先进制造系统。广义的c i m s 是在某种环境下提高企业总体效益的全局性的思想 哲理和方法，它要求以集成的方式组织企业的全部生产活动，从设计制造到销售 维护各阶段要尽可能的利用各种先进技术来提高生产效率、降低成本等，确保生 产系统全局和局部的柔性。 一般的c i m s 的结构可以分为五层，而生产计划与调度在整个框架中起桥梁 作用，连接管理层和控制层，是管控一体化的结合部分。它的上面是负责整个企 业经营战略的决策层，下面是生产过程的监督控制层。因此，生产计划和调度是 c i m s 的关键，无论在理论研究还是在应用系统开发都备受重视。从上面的分析 可以看出，工厂级的计划和调度在企业生产管理中起着承上启下的作用合理的 计划和调度不但能降低生产成本、节约能源、减少劳动力消耗、增强生产的柔性 山东大学硕士学位论文 与适应性，而且还能提高企业的服务水平，降低存储费用、提高企业的生产能力、 加深对过程机制及关键数据的理解。 信息控制 目标 决策层 l 决策信息卜_ 怪营决策| + 一利润最大l r i _ 一：二= = ： 管理层厦耍錾垂乎- 厘匣垂酬鑫喜薯薹l 调度层l 调度信息 生产调度 监控层l 工况信息卜+ l i i 盏控系统 控制层l 测量信息卜艟制系统 生产过程 1 1 生产调度问题定义及分类 图1 1 c i m s 结构图 优化调度 先进控制 操作优化 故障诊断 复杂控制 常规控制 生产调度就是在一定的时间内，进行可用共享资源的分配和加工任务的排 序，以满足某个或某些特定的生产指标【2 】。生产调度主要涉及加工作业的具体安 排和资源的详细分配，它是一个n p 完全问题( n o n - p o l y n o m i a lc o m p l e t e ) 3 1 0 其 中，共享的生产资源包括：原料、加工设备、存贮设备、运输设备、人力、资金 和能源等；加工任务就是在指定时间内生产特定的产品，这些产品既可是用户订 购的产品，又可是根据市场需求计划生产的产品；生产指标制定的目的是为了尽 可能获得最大的经济效益和较好的社会效益，所以生产指标一般定为成本最低、 库存费用最少( 减少流动资金占用) 、生产周期最短、生产切换最少、设备利用率 最高、三废最少等1 4 1 生产调度问题的分类方法很多，主要有以下几种【5 1 ： ( 1 ) 根据加工系统的复杂度，生产调度可以分为单机调度、j o b - s h o p 调度、 f l o w - s h o p 调度、o p e n - s h o p 调度、多机器并行加工( km a c h i n ei np a r a l l e l ) 调度 等几个基本类型6 7 1 单机调度是指所有的操作任务都在一台机器上完成，需要 2 山东大学硕士学位论文 对任务进行优化排队；j o b - s h o p 调度是最一般的调度类型，它是指由”个不同 的机器加工一个有特定加工路线( 顺序) 的工件，不同工件的工序问没有顺序约束， 工序加工不能中断；f l o w - s h o p 调度假设所有工件都在同样的设备上加工t 并有 一致的加工操作和加工顺序；多机器并行加工调度是指多台机器并行加工工件， 而且并行加工的机器和工件都是类似的 ( 2 ) 根据优化准则，可以分为基于代价和性能的调度两大类。代价包括为了 实现调度方案所消耗的各种费用和所造成的损失，例如运行费用、运输费用、存 储费用和延期交货损失等。性能主要包括设备利用率、最大完成时间、拖延加工 任务的百分比等。虽然在理论分析上，大部分只注意调度的性能，但在实际生产 中，通常要综合考虑代价和性能两方面因素。 ( 3 ) 根据生产环境的特点，可将调度分为确定性调度和不确定性调度。前者是 指加工时间和其他参数是已知的、确定的量；而后者的加工时间和有关参数是不 确定变量。 “) 根据加工任务或被加工工件的特征，可将调度分为静态调度和动态调 度。静态调度是指所有待安排加工的工件均处于待加工状态，因而进行一次调度 后，各作业的加工被确定，在以后的加工过程中就不再改变；动态调度是指作业 依次进入待加工状态，各种作业不断进入系统接受加工，同时完成加工的作业又 不断离开，还要考虑作业环境中不断出现的不可预测的动态扰动，如作业的加工 超时、设备的损坏等。实际的生产调度问题往往是由j o b - s h o p 和f l o w - s h o p 型 等基本调度类型组合而成，基于代价且是随机性的、动态的。 ( 5 ) 生产过程一般按照其输出的产品是呈现连续的产品流、离散的批量、离 散的数量三种情况，分为离散生产过程，间歇生产过程和连续生产过程。在离散 生产过程中，产品通常是分批( 原料相同、加工工序相同的一组产品) 制造的，一 定数量的产品作为一个工件组，并且在各个工作台之间传输，而且，每个工件部 有独立的个性，机械加工是典型的生产过程；间歇生产过程又称为批处理过程， 是由一个或者多个按一定顺序执行的操作步( 或者操作阶段) 组成，这些操作步是 离散的，而每步中的过程是连续的，间歇生产过程一般包括若干通用设备，多个 产品在有限个设备上生产；在连续生产过程中，原料经由不同的专用设备加工转 变为产品，每个设备都是在稳定的工作状态下，完成一项规定的生产操作，一个 连续生产过程输出的产品是连续的产品流相应地，生产调度问题可以分为面向 山东大学硕士学位论文 机加工等离散操作的车| 日j 调度问题，和面向流程工业生产调度的1 1 日j 歇生产调度或 者成为批处理调度问题。 本文主要讨论不确定生产环境下的流程工业静态生产调度的建模问题。 1 2 生产调度模型优化方法与技术 在对调度问题进行研究的方法上，最初是集中在整数规划、仿真和简单的规 则上，这些方法不是调度结果不理想就是难以解决复杂的问题。随着各种新的相 关学科与优化技术的建立与发展，在调度领域也出现了许多新的优化方法，比如 神经网络( n i 0 、模拟退火法( s a ) 、遗传算法( g a ) 、禁忌搜索法口s ) 等，使得调度 问题的研究方法向多元化方向发展。由于生产调度的复杂性，从现有的文献来看， 生产调度建模理论研究可分为以下几种类型1 5 l ： ( 1 ) 数学规划方法 数学规划方法是根据生产过程的特点将生产调度问题抽象成为数学规划模 型，常见的生产调度数学规划模型包括：线形规划( l p ) 、混合整数线性规划 ( m i l p ) 、混合整数非线性规划( m i n l p ) 、动态规划( d p ) 等。 数学规划方法属于精确调度方法，其中以m i l p 模型最有研究价值1 6 1 。当决 策变量中至少有部分变量为整数时，线性规划就成为混合整数线性规划( m i l p ) m i l p 的形成一是由于设备、人员的分配是以整数计的；其次，是由于分段设计 时各阶段的资源可用性问题，部分决策变量为整数0 或l 【7 t 引。典型应用有： c o x h e a d 9 1 使用几个经典的m i l p 模型对炼油厂的调度优化进行建模；a d e l m a n 掣1 0 1 人采用整数规划技术来分配电缆生产厂里的光纤；吴建型i l 】提出一种可以 大大减少决策变量的多产品间歇生产调度的m i l p 模型等。混合整数线性规划常 用的求解方法有b e n d e r s 分解法【1 2 l 、分枝定界法【1 3 1 、割平面法【1 4 1 、l a g r a n g i a n 松 弛法和启发式方法1 7 b 肄。 数学规划方法的优点是得到的调度方案全局性比较好，无论任务排序还是任 务分配都可以保证全局最优性但是，数学规划方法是一种严格的数学方法，它 需要对调度问题进行精确的建模，任何参数变化都可能严重影响原最优解的最优 性【1 6 1 因此，本文的第二章主要讨论生产调度m i l p 模型的优化后分析此外， 如果了解参数变化的部分信息，在建模过程中我们就可以把这种不确定信息以机 4 山东大学硕士学位论文 会约束的形式作为模型的约束条件，这样不仅可以得到最优调度，还能保证调度 的稳定度水平，详细讨论请见第三章。 ( 2 ) 启发式搜索方法 启发式问题求解方法是在工程实践中常用的方法之一，它主要依靠任务无关 信息来简化搜索过程，在很多情况下，问题求解可视为系统化地构造或查找解答 的过程。启发式求解方法虽然不能得到一个最优解，但却大大减少了较大规模问 题求解所花费的时间，因此尤其适用于动态过程问题的求解。 s a d e h 等人【1 力介绍了一种变量和实值化顺序启发式规则。该规则通过选择 变量的实例化顺序和最先可能的取值来减小搜索空间，从而加快约束满意问题的 求解速度；t a d e i 等人【1 提出了一种针对食品工业生产计划和调度的分区算法 ( p a r t i t i o n i n ga l g o 删瑚) 和本地搜索( i o c a ir e 靶a r c h ) 技术等等。陈伟等f j 3 j 则介绍了利 用j o h n s o n 算法和r a e s 算法这两种启发式算法求解间歇式化工过程调度问题的 方法。 启发式搜索的优点是利用了面向特定问题的经验知识，因而可以产生较好的 解决方案，求解时间也可以接受。启发式搜索方法的缺点是用来评估解决方案的 质量手段还比较少，如何提高搜索效率并减少内存使用以解决规模较大的问题， 还需要进一步探索。 ( 3 ) 系统仿真方法 系统仿真方法是解决生产调度问题的重要手段，它不单纯追求系统的数学模 型，它侧重于对系统中运行的逻辑关系进行描述，而且与数学规划采用全局的而 且经常是简化的视图相比，系统仿真方法为所有分配、排序和时问选择等决策的 结果提供局部的分析，能够对一个给定的调度用很低的代价进行详细的和快速的 分析，通过分析能够对各种调度方案进行比较和评价，从而选择效果最优的调度 方法和系统动态参数 p e t r i 网作为一种重要的系统仿真方法，为离散事件系统的模型化、性能分 析和设计提供了一个统一的环境“9 1 ，已经引起人们的关注在c i m s 的研究中， 已广泛运用p e t r i 网进行离散事件系统的建模和分析。传统的离散p e t r i 网侧重于 离散制造系统的仿真分析，不适应于石油、化工等流程工业环境下的连续动态系 统和混合动态系统的建模，而连续p e t r i 网和混合p e t r it 2 0 概念的提出和发展为 流程工业环境下的系统方法提供新的理论依据。 山东大学硕士学位论文 系统仿真方法经常与其他方法结合起来使用，因为纯系统仿真方法有以下局 限性：系统仿真方法只适用实验室内产生的理想状态，无法真正描述实际状况1 5 l ； 系统仿真方法的计算费用较高，每次设计都需要投入大量人力物力：仿真的准确 性难以控制，主要依赖于人员的判断和技巧 ( 4 ) 人工智能方法 人工智能研究主要是如何用机器模拟人类的智能活动的某些方面，延伸人脑 功能的问题。人工智能在生产调度中的应用主要表现为两方面： 一方面是利用人工智能技术结合人类调度专家的经验，对生产调度问题进行 建模并求解，例如专家系统s ) 、约束规划( c p ) 等。 专家系统是一个( 或一组) 能在某个特定领域内，以人类专家水平去解决该领 域内困难问题的计算机程序。该方法主要用来求解大规模优化问题。对经常使用 的带有普遍性的优化问题，能节约大量的计算资源，缺点是专家系统构建工作量 巨大。约束规划是一种应用限制变量选取顺序和变量赋值顺序来减少搜索空附大 小的方法，它可以用来实旌柔性的和有效的调度系统，它不局限于一定的约束集 合，但是带来的直接后果是高昂的计算费用，而且由于包含多种约束，求解难度 较大。 另一方面是利用传统数学规划方法建模，用人工智能的方法求解，又称为计 算智能，例如人工神经网络( a n n ) 、遗传算法( g a ) 、模拟退火算法( s a ) 等。 自从h o p f i e l d 提出的具有联想记忆功能的反馈互连网络( h o p f i e l d 网络模型) 成功解决了旅行商问题，神经网络的研究又掀起了研究热潮。a n n 模型可能用 来逼近一类复杂的非线性动态过程，并模仿人的学习、联想记忆等行为，表示定 型、模糊、非良结构的知识和经验规则。在各种不确定条件下实现控制、优化、 决策等功能。g a 是由密歇根大学h o l l a n d 等创立的，发展成为一种普适性优化 算法其优点是适用范围广，算法鲁棒性强，但是它的普适性，导致算法对于确 定的问题时的效率低下当前出现多种改进遗传算法，例如自适应遗传算法，它 把算法参数也作为一种基因( g e n e ) ，参与遗传操作，通过交叉和变异来优化算法 性能s a 将组合优化问题与统计学中的热平衡问题类比，通过模拟退火过程中 温度下降过程来确定寻优路径通过模拟退火算法，可以跳出局部解。到达全局 最优解。它的缺点是求解时间太长。 6 山东大学硕士学位论文 1 3 不确定条件下生产调度模型研究现状 目前不确定条件下的生产调度模型研究主要集中于以下三个方面：第一，假 设不确定因素完全服从概率分布，使用随机数学处理不确定参数【2 l ，2 2 1 。第二，假 设不确定因素是模糊的，使用模糊数学处理不确定参数 2 3 1 。第三，假设只知道不 确定因素的区间信息，建立生产调度模型的区间规划【卅。 ( 1 ) 不确定因素服从随机分布时的调度模型 r a i ne j ( c ，毛d ，口) f j 一 譬( c ，x ，d ，口) 0 。h ( c ，x , d ，刃= 0 c c ，工x ，d d ，0 e o 其中，c 是决策系数，可以是产品f 的单位成本系数，也可以是产品i 的加工 时间；x 是决策变量，可以是第f 种产品的加工量，或者在某工序中的加工时间； d 为离散变量，用于表示可能引起生产停顿的不确定因素；0 为离散变量，用于 表示连续状态的不确定因素，例如生产比例的微量变化等。 目标函数，可以是销售量，产品生产量，利润等。由于模型中约束存在随机 变量，因此使用目标函数的期望值最为最终的目标。 ( 2 ) 不确定因素服从隶属函数分布时的调度模型 r a i n j ( c , x , d ，一) ” 一， 趾弘x ，d ，曼) 0 h ( c ，x ，d ，一) = 0 c c ，x x ，d d ，0 o 有些不确定参数的分布无法通过试验的方法得到，这样只能依赖于建模人员 的经验知识给出不确定参数的可能性分布或者可信性分布等等。此时，不确定参 数可用模糊变量代替，使用模糊数学知识来求解模糊调度模型。 ( 3 ) 只知道不确定因素区间信息时的调度模型 m i n j ( c ，x ，d ，0 ) c j ， s(c，薯d，0v- 豇讹x ，d ，口) ：0 c c ，x x ，d d ，0 0 当只能够知道不确定参数的区间或者不确定参数的变化范围比较小时，不确 7 山东大学硕士学位论文 定参数可以使用区间表示口 o l , e “】，这样调度模型成为区间规划模型。 1 4 论文的主要内容 从上一节可以看出如何处理生产调度模型中不确定性将直接影响到调度的 质量，甚至影响调度的可行性，因此研究怎样使用已有的数学工具来降低不确定 性对生产调度的影响是十分有意义的问题，这也是本文的主要研究内容。 本文的安排如下： 第一章绪论本章给出了生产调度的定义及其分类，概述了一般生产调度问 题的建模方法，并分析了不确定条件下生产调度问题建模的现状及其难点。 第二章基于不确定规划的生产调度优化建模与分析本章从实际生产环境中 的不确定因素的分类入手，研究了各种典型不确定因素产生的原因，并使用机会 约束来描述这些不确定性，给出了各种机会约束之间的等价关系。从统一集理论 角度提出了多重不确定的，并提出基于稳定度的建模方法。 第三章生产调度的区间规划模型及优化后分析本章根据参数不确定一般优 化模型的结构提出了生产调度模型的区间规划模型，讨论了模型中约束性质及其 变化的分析步骤，并根据约束性质的变化情况论述了决策参数与模型最优解之间 的函数关系，为提高调度质量以及控制调度参数提供了理论指导。 第四章流程工业生产调度系统的应用及关键技术本章主要讨论了目前常见 的建模语言及其发展，并以国家8 6 3 项目“流程工业实时计划与调度系统”为例阐 述了生产管理软件实现的关键技术。 1 5 结束语 调度的复杂性、调度领域知识的多样性和生产环境的动态性决定了调度问题 的解决单纯依靠精确的数学方法是难以完成的，必须把描述和处理不确定性各种 数学知识有机地结合起来去研究调度数学建模问题。 山东大学硕士学位论文 第二章基于不确定规划的生产调度优化建模与分析 2 o 引言 由于调度主要涉及一定时间内共享资源的可用性和设备分配等问题，因此生 产调度大都形成混合整数线性规划模型( m i l p ) 瞄】或混合整数非线性规划模型 ( m i n l p ) 【2 6 】。但是在工程领域，存在很多不确定因素，例如设备损坏、急件加工 等，这将会直接影响确定条件下调度模型的准确性，使原模型的解可能不再是最 优解，甚至不是可行解。这些不确定因素的存在严重影响到调度的稳定性和传统 调度模型在实际中的应用，所以生产调度的建模问题迫切需要站在不确定条件下 重新考虑。本章2 1 节分析了生产过程中出现的各种不确定因素，2 2 节给出了 生产过程中各种不确定信息的表达方式及它们之间的转化关系，并讨论了多重不 确定性下机会约束的表达方式1 2 ”。 在一个调度方案确定以前，人们总是希望了解这个方案能否顺利执行或者说 它的抗干扰能力有多大，这主要是由于生产过程中存在着许多不确定因素，例如 加工时间的变化，产品需求量的变化，交货期的改变及设备故障等。这些不确定 因素的存在使得原来的优化调度不可能一直顺利执行，而引起再调度问题，即改 变原来的生产安排，这是决策者不希望的。另一方面，即使必须进行再调度，决 策者也希望新的调度不要偏离原来的调度太远，尤其是当生产过程中出现的干扰 不是太大，例如小的加工时间变化，短时间的原料供应变化和产品需求时i 日j 或需 求量的变化等，决策者希望小改或不改变原有的调度，只牺牲一点性能指标，以 保持生产的稳定性【拥此时我们可以说在这些不确定性因素的干扰下，生产调度 仍然是稳定的，这种稳定性取决于调度方案的初始柔性1 2 9 】本章的2 3 节讨论了 基于这种稳定性意义的生产调度模型，该模型使用带有稳定性机会约束的两阶段 随机规划模型不仅保证了调度方案的初始柔性，而且允许调度方案在一定风险下 获得更好的性能，更加贴近实际生产状况 最后，针对2 3 节所建立的调度模型，本章的2 4 节给出了求解不确定模型 9 山东大学硕士学位论文 的一种随机搜索算法，2 5 节进行了实例仿真。 2 1 生产过程中不确定因素分析 实际生产系统存在各种各样的不确定因素，可以把不确定性分为系统固有的 不确定性、生产过程产生的不确定性、外部环境的不确定性和离散不确定性】。 ( 1 ) 系统固有不确定性 系统固有不确定性主要包括各种动力学、热力学和传热、传质常数等。这些 常数在不同的生产环境下有可能不一样，但是在调度层次上对它们精度要求不 高，所以可以忽略其不确定性，使用近似值或者数学期望值来代替精确值，来降 低模型的复杂程度，提高求解速度。 ( 2 ) 生产过程中产生的不确定性 生产过程中产生的不确定性主要包括生产过程中各种流体介质的流速、温 度、压力等的变化和设备的处理能力这种不确定性大都能通过检测手段得到它 们重复出现的规律，可以根据它们的统计数据确定它们的概率分布。 ( 3 ) 外部环境的不确定性 外部环境的不确定性主要来自于外部影响，产品需求量、产品价格、能源和 原材料的供应以及其它外部因素的变化。这种参数不确定性的预测不仅需要依靠 实际生产过程中的统计数据，还需要调度人员的经验知识。实际生产过程中，这 种不确定性经常出现，并且它是影响调度稳定性，导致重调度的重要原因，调度 模型必须考虑这种不确定带来的影响。 ( 4 ) 离散不确定性 离散不确定性主要包括设备故障、仪器仪表失效，人工误操作等。由于这类 不确定性的发生会对生产组织造成严重影响，因此根据z a d e h 可能度概率的兼 容性原型3 0 l ，用机会约束尽可能的降低这种不确定发生的可能性。但是，包含这 种约束的模型，在求解时会变得相当困难由于它常常导致非正常生产状态，所 以这里不讨论 2 2 生产调度的机会约束规划模型 机会约束规划( c h 卸c ec o n s t r a i n e dp r o g r a m m i n g ) i 妇c h a r n e s 和c o o p e r l 3 1 1 提 山东大学硕士学位论文 出，主要针对约束条件中包含随机变量，且必须在观测到随机变量的实现之曲做 出的决策的情况，机会主要表示满足概率测度约束 p r g ( x ，参) ) 口 本节把“机会”的意义扩展开来，不仅可以表示约束满足概率测度约束，还 可以表示约束满足可能性测度约束 p o s g ( x ，善) ) 在调度模型中，使用机会约束来表达发生在实际环境中影响调度模型的不确 定因素被允许的概率和程度。 前一节分析了生产环境中可能存在的各种不确定因素及其分类，本节主要讨 论这些不确定因素在调度模型中的表达形式及它们之间的关系。 2 2 1