（化学工程专业论文）基于遗传算法的间歇化工过程调度及其在线调整研究.pdf

基于遗传算法韵间歇化工过程调度及其在线调整研究 摘要 间歇化工过程调度是一类十分复杂的组合优化问题。由于过程内外众多不确 定性因素对过程运作有很大影响，不确定性调度研究受到学术界和工业界的关 注。在线调整是处理不确定性因素的主要方法之一，本文以间歇化工过程调度及 其在线调整为研究对象，进行了以下研究工作： l 、提出了一种基于遗传算法的内外圈法求解调度问题。 内外圈法将调度问题分解为调度次序问题和时间表问题，缩小了求解范围， 简化了原问题的求解。该方法与遗传算法契合紧密，外潮问题由遗传操作完成搜 索；内圈问题作为遗传算法的评价函数。将内外圈算法用于求解间歇化工过程调 度问题，获得满意结果。 2 、研究了设置异步平行单元和多功能单元的间歇化工过程的调度问题。 探讨了设置异步平行单元过程调度的计算方法：考察了在不同间歇级上设置 异步平行单元对过程的改进。提出了虚拟周期概念用于处理多功能单元的调度问 题，基于虚拟周期求解了含有多功能单元过程的调度问题。 3 、间歇化工过程调度的在线调整研究。 考察了订单变化和设备故障两类不确定性因素的在线调整问题。分别探讨了 订单变化和设各故障对过程调度的影响。考察了在市场变化和设备故障的在线调 整中各种因素对调整方案和目标函数的影响，并分析原因，揭示产生影响的本质。 通过一个中药厂生产中的应用实例，验证了本文提出的调度及其在线调整方法的 有效性。 关键词：间歇化工过程调度在线调整遗传算法 s t u d yo nb a t c hc h e mic a lp r o c e s s e s s c h e d u l i n ga n do n - l l n em o d l f i c a t l o nb a s e do n g e n e t i ca l g o r l t h m s a b s t r a c t t h es c h e d u l i n go fb a t c hp r o c e s si sac o m p l i c a t e dc o m b i n a t i o no p t i m i z a t i o n p r o b l e m t h es t u d i e so fu n c e r t a i n t ys c h c d u l i n gr e c e i v e dg r e a ta t t e n t i o nf r o mb o t ht h e a c a d e m i aa n dt h ei n d u s t r yb o c a u s eo ft h ef a t e f u li n f l u e n c eo fu n c e r t a i n t yf a c t o r so n s c h e d u l i n g t h eo n - l i n em o d i f i c a t i o ni s o n eo ft h em a i nm e a n sd e a l i n gw i t h u n c e r t a i n t i e s t h ei n v e s t i g a t i o no fs c h e d u l i n go fb a t c hc h e m i c a lp r o c e s s e sa n dt h e o n - l i n em o d i f i c a t i o na r ep r e s e n t e di nt h i sp a p e r a n dt h ep r i m a r yc o n t e n t sa r e 船 f o l l o w s ： 1 a ni n n e r o u t e rl 0 0 pm e t h o db a s e do ng e n e t i ca l g o r i t h m s ( g a ) w a s p m p o s e df o rs c h e d u l i n g t h es c h e d u l i n gw a sd i v m e di n t ot w op a r t s ：p r o c e s s i n gs e q u e n c ea n dp m c e s s i n g t i m e t a b l e t h u st h es o l u t i o ns p a c es i n - i n k e da n dt h ep r o b l e m sa l es i m p l i f i e d ，t h i s m e t h o dh a sag o o dc o m p a t i b i l i t yw i t hg a g ao p t i o n sw e r eu s e df o rs e a r c h i n gi nt h e o u t e rl o o p a n dt h ei n n e rl o o pc a nb er e g a r d e da st h ee v a l u a t i n gf u n c t i o no fg a t h e s c h e d u l i n go fb a t c hc h e m i c a lp r o c e s s e sw a ss o l v e db yt h ep m p o s e dm e t h o d ，a n dt h e r e s u l t sw e r es a t i s f y i n g 2 t h e s c h e d u l i n g o fp r o c e s s e sw i t hp a r a l l e lu n i t so u to fp h a s ea n d m u l t i f u n c t i o n a lu n i t sw e r ei n v e s t i g a t e d f i r s t ，t h es o l v i n gm e t h o do fs c h e d u l i n go fp r o c e s s e sw i t hp a r a l l e lu n i t so u to f p h a s ew a sd i s c u s s e d t h e nt h ei n f l u e n c eo fp a r a l l e lu n i t ss e t t i n go nd i f f e r e n tb a t c h s t a g ew a sa n a l y z e d v i r t u a lp e r i o dw a sp r o p o s e df o rt h es c h e d u l i n go fp r o c e s s e sw i t h m u l t i f o n e t i o n a lu n i t s c a s es t u d i e sp r o v e dt h ef e a s i b i l i t yo f t h i sm e t h o d i i 3 r e s e a r c ho f o n l i n em o d i f i c a t i o no f b a t c hc h e m i c a lp r o c e s s e ss c h e d u l i n g t h eo n l i n em o d i f i c a t i o nd e a l i n gw i t ht w ol d n d so fu n c e r t a i n t i e sw h i c hi n c l u d e o r d e rc h a n g i n ga n de q u i p m e n tf a i l u r e ( u n i tf a i l u r e ) ，t h ei n f l u e n c eo fo r d e rc h a n g i n g a n du n i tf a i l u r eo ns c h e d u l i n gw a si n v e s t i g a t e d t h em e a s r r ea n dt h eo b j e c t i v e f u n c t i o no fo n - l i n em o d i f y i n gw f f f ei n f l u e n c e db ym a n yf a c t o r s t h ec a u s ea n d e s s c l l c eo ft h ei n f l u e n c ew e r ea n a l y z e d t h ev a l i d i t yo fs c h e d u l i n ga n dm o d i f i c a t i o n t h a tp r o p o s e di nt h i sp a p e rw a sp r o v e db yc a s es t u d yo fac h i n e s ep h a r m a c e u t i c a l f a c t o r y k e yw o r d s ：b a t c hc h e m i c a lp r o c e s s e s ，s c h e d u l i n g ，o n l i n em o d i f i c a t i o n , g e n e t i ca l g o r i t h m i l l 青岛科技大学研究生学位论文 第三章： 第四章： 主要符号说明： 多产品厂 c | t ，或c m n 俐：第f 个被处理的产品第j 个工序的结束时间 z 加工序列 船： 加工序列中第f 个加工的产品 啊或t 捌： 第i 个加工的产品第，个工序的加工时间 b ，：第i 个虚拟产品的产量 n ：第i 个虚拟产品的价格 疗：第i 个虚拟产品的成品存储成本 y ；： f d ： t d ： 多目的厂 x i ： g t ( m ，砂： m s ( m ，砂： p s ( p d ) = p 扯 砀： 异步平行单元 m c ( i j ) ： m x ( x u ) = t j ) t 印( x i j ) ： m t l q ) ： 多功能单元 a ： p ： p 阢 口： 第i 个虚拟产品的交货拖延惩罚 第i 个虚拟产品的完工时间 第f 个虚拟产品韵交货时间 加工序列中第f 个加工工序的产品号 设备m 第g 个加工任务的完工时间 设备m 第g 个加工任务处理的产品 产品p 第，道工序使用的设备号 产品p 第，道工序的完工时间 产品p 第，道工序的加工时间 m 产品第，个平行任务所选设备号 崩的第，道工序使用的平行单元 m 的第_ ，道非平行任务工序的加工时间 m 的第_ ，道平行任务工序的加工时间 平行单元q 的上次加工任务的完工时间 产品数 产量 产品的价值系数 原材料数目 i v 青岛科技大学研究生学位论文 第五章 第六章 ： v r j j v ： & ： 0 ： 原材料用量 原材料价值系数 工序数 一个虚拟周期内工序的操作次数( 各个虚拟周期不同) 每次操作的处理量 操作费用系数 储罐数目 一个虚拟周期内储罐存储的时间段数，( 每两次储量变 化之间的时间为一个时间段) 不同时间段内的存储量 时间段的长度 存储费用系数 虚拟周期数 总完工时间 订单更改时间 设备，的空闲时间 产品数 产品i 的订单数量 产品i 的销售价格 产品i 的原材料价格 产品i 分配的批次数 产品i 的第j 批次的批量 产品f 的交货时间 产品i 的，批次的完工时间 产品i 的存储费用 产品i 的交货拖延惩罚 设备故障发生时间 产品i 的斜度顺序指标 产品i 第j 道工序的加工时间 v 胁胍m巴仇弧眈 趴l | i l | ；触 舶脚斯舭 童璺型垫查兰婴壅圭堂堡笙苎 一 1 。1 前言 第一章绪论 1 1 1 间歇化工过程 间歇化工过程又称批处理化工过程，指的是以分批方式组织生产的化工过 程。它通常有多个间歇设备单元( 如反应器、加热釜等) 和半连续单元( 如泵、 换热器等) 组成，典型的间歇化工过程如图1 - 1 所示j 。习惯上把间歇化工过程 称为间歇厂( b a t c hp l a n t ) 以与连续化工过程和间歇单元操作( 如间歇蒸馏) 相 区别。 图卜1 典型的间歇化工过程 f i g u r e1 - 1ar e p r e s e n t a t i v eb a t c hp m c e 站 间歇化工厂可以按产品生产工艺的相似程度分成三类：单产品厂、多产品 ( m u l t i p r o d u c t ) 厂和多目的( m u l t i p u r p o s e ) 厂。单产品厂生产比较简单。这里不作 讨论；在多产品厂中所有产品的处理步骤都相同，如图1 - 2 所示，类似于流水作 业( f l o w - s h o p ) ；而在多目的厂中，产品可以有各不相同的处理步骤，如图1 3 所示，类似于工件作、a k ( j o b s h o p ) 。 间歇化工过程投资少、上马快，柔性好，易放大，易改造更新；特别适用于 批量小、产值高、品种多、市场变化快、上市快的产品的生产，在特种化学品、 生物化学品及按客户订单定制的非大批量产品生产领域有非常大的优势。随着生 产力水平和人民生活水平的提高，生产出高质量、高功能、多品种、系列化的精 细化工产品以满足生产和生活高档化的需要成为当前化工生产的主要任务1 2 】。当 前化工工业产品个性化日益加强，上市周期变短，产品种类迅速增加，市场变化 加快；间歇化工过程在化工生产中的应用日益广泛。新世纪，间歇过程的应用将 上升 3 1 。 奄 电一 。j n b 一 引脚n一 青岛科技大学研究生学位论文 p | o d u c t b a a b c p r o d u c ta p r o d u c t b p m d u c t c v 1 v - 2 v - 3v - - 4 图1 - 2 多产品厂示例 f i g u r e1 - 2a ne x a m p l eo f m u l t i p r o d u c tp l a n t p r o d u c t c 图1 - 3 多日的厂示侧 f i g u r e1 - 3a ne x a m p l eo f m u l t i p u r p o s ep l a n t 1 1 2 间歇化工过程调度 a 在间歇化工生产过程中，由于多种产品共享时间和有限资源( 如原材料、加工 设备、公用工程等) ，如何有效地安排生产过程，妥善地根据市场需求或生产任务 分配设备及时间，以提高设备利用率、缩短设备闲置时间，提高间歇过程的生产 效率和经济效益成了间歇过程综合优化中的重要问题，这就是问歇过程调度问题 的研究内容。 间歇过程调度又称间歇过程时间表问题或间歇过程的生产计划问题。其定义 为：在一定的设备( 反应器、分离装置、中间储罐等) 和其它限制条件下，确定 各产品在不同设备上的加工次序和时间以使某一个或多个经济或技术指标达到 最优【4 】。r e k l a t i c s 【5 】认为生产计划问题有两种研究方法，单层次方法和多层次方法。 在单层次方法中，伺时考虑总体生产计划及详细的调度。在多层次方法中，问题 被分为高层( 长期或中期) 计划子问题和低层( 短期) 排序调度子问题；不过短期与中 期调度之间的区别并不是很明显【6 1 。本文中着重研究短期调度子问题。 调度的目标一般包括两类，一类是基于经济指标的，另一类是基于间歇过程性 能指标的。 基于经济的调度目标主要有： 总体生产费用最小，包括可变生产费用，库存保持费用及产品更换费用等： 生产利润最大，生产利润等于产品总价值减去总体生产费用。 基于性能的调度目标主要有： 2 青岛科技大学研究生学位论文 生产所有产品所需要的总时间即总完工时间最小，它可使过程的资源利用 率与生产率最大；所有产品的平均流时间( f l o w t i m e ，即产品完全通过生产过 程所需要的时间) 最小；平均延迟时间( t a r d i n e s s ) 最小，延迟时间等于产品的生 产完成时间与交货期之差，只取正值；最大延迟对闯最小等。 1 1 3 间歇过程调度问题中的几个重要概念 1 批次( b a t c h ) 问歇过程操作中每隔一定的时间投入的一定量的物料或得到的一定量的产 品。 2 批量( b a t c hs i z e ) 每一批加工物料的数量。 3 间歇级( b a t c hs t a g e ) 间歇过程中加工设备根据产品的加工任务所分成的一系列生产级。 4 中间储罐 间歇操作的一个特点是可以根据生产需要设置能够暂时存储中间产品的储 罐。中间储罐的设置方式决定了中间产品在设备间的转移方式，通常也可根据这 个转移方式给间歇过程分类。间歇过程中间储罐可分为无限中间储罐( u n l i m i t e d i n t e r m e d i a t es t o r a g e ，u i s ) 、无中间储罐( n oi n t e r m e d i a t es t o r a g e ，n i s ) 、零等待( z e r o w a i t ，z w ) 、有限中间储罐( 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 ) 和混合中间储罐( m i x e d i n t e r m e d i a t es t o r a g e , m i s ) 五种形式， 需要注意的是，中间储罐的存储能力是用其数目来衡量的，而不是其容积， 这是因为通常认为每个储罐都有足够大的容积以临时容纳任何一批产品。假设有 n 个产品需要加工，对于u i s 方式，在任意两个生产阶段之间都有n 1 个储罐； 若储罐数目c r n 1 ，则为f i s 方式。对于n i s 和z w 两种方式，虽然都没有中间储 罐，但是z w 方式要求产品在上一阶段的生产完成之后立即转入下一设备阶段开 始生产，而m s 方式则允许物料在设备中等待。如果各个产品在不同的加工阶段 使用了以上两种或多种中间存储形式则称为混合中间储罐( m i s ) 。 5 甘特图( g a n t tc h a r t ) 甘特图又称条线图，可以直观、简捷地表达调度的时间分配情形。在g a n t t 图中，横坐标表示时间，纵坐标表示间歇级，它可以清楚地表达同一批次的产品 在不同间歇级所占用的时间，以及任意间歇级上不同批次产品的时间分配。如图 1 4 所示。 青岛科技大学研究生学位论文 图1 4 甘特图示例 f i g u r e1 - 4a ne x a m p l eo f g a n t tc h a r t 6 。覆盖操作( o v e r l a p p e do p e r a t i o n ) 和非覆盖操作( n o n o v e r l a p p e do p e r a t i o n ) 这是间歇过程两种生产组织形式，在覆盖操作中上一批物料加工完毕。设备 腾空并清洗后立即加入下一批物料进行加工；而在非覆盖操作中需要上一批物料 的所有工序全部加工完毕离开生产线后再加入下一批物料。 7 批量限制级( b a t c hs i z el i m i t i n gs t a g e ) 和时间限制级( t i m el i m i t i n gs t a g e ) 批量限制级指闻歇过程中限制过程最大批量的间歇级，该间歇级的批量等于 过程的最大批量。时间限制级指因加工时间相对较长而限制整个过程总生产时间 的间歇级。 8 平行单元( p a r a l l e lu l i i t ) 平行单元是为了增大过程的生产能力在一些间歇级上设置的多台机器。可分 为同步平行单元和异步平行单元。同步平行单元( p a r a l l e lu n i ti np h a s e ) 一般添 加在批量限制级上，物料从上一间歇级同步进入平行单元加工，相当于增加批量 大小。异步平行单元( p a r a l l e l u n i t o u t o f p h a s e ) 一般设置在时间限制级上，物料 在不同的时间进入平行单元进行加工，相当于在该间歇级批量不变的情况下，缩 短了加工时间。 1 1 4 间歇化工过程不确定性调度 在实际生产过程中，会存在各种各样的不确定因素，如产品的产量、原材料 的价格和供应量、劳动力因素、每一道生产工序中产品的处理量、处理时间、中 间存储单元的存储量、中间产品的稳定存放时间等都可能发生变化；生产中原材 料或能源的暂时短缺也是不确定因素；另外，生产过程中往往会发生一些事先无 法预料的突发事件，如生产设备的损坏、仪器仪表的故障、操作工的误操作等，这 些不确定的因素往往会导致生产调度方案无法按预定的目标正常执行【7 j 。 不确定性鼠索主要有以下几种： 4 青岛科技大学研究生学位论文 系统固有的不确定性。这类不确定性参数主要包括各种动力学、热力学常数 和传热、传质系数等。 生产过程中产生的不确定性。这类不确定性主要包括生产过程中各种流体介 质的流速、温度、压力等的变化和设备的处理能力变化。 外部环境的不确定性。在市场经济体制的条件下，企业的生产不再是独立的 行为。而是受外部环境的影响，产品的需求量、产品的价格、能源、原材料的供 应以及其它外部环境因素构成不确定因素。这类不确定性往往影响生产计划和生 产调度方案的正常执行。 离散不确定性。这方面的不确定性主要是设备的故障，仪器、仪表的失效，人 工误操作等，或者是关键操作人员的短缺等。这类不确定性对企业组织正常生产 会造成很大困难。 由于间歇过程的生产是一个非稳态过程，增加了过程本身不确定因素发生的 机会，也为处理不确定性因素增加了难度。在调度中主要处理外部不确定性和离 散不确定性。由于不确定性因素的出现，预先给出的最优调度在实际执行时很可 能沦为次优解，甚至变为不可行解。所以，如何处理不确定性因素成为间歇化工 过程调度的一个研究重点，这就是间歇过程不确定性调度阀题。 综上所述，间歇化工过程在在新世纪将有长足的发展，而调度对间歇过程经 济效益和技术指标的提高意义重大。由于实际生产过程中的大量不确定性因素的 存在，预先给出的调度在实际执行可能沦为次优解或者不可行解。所以间歇过程 不确定性调度研究具有重要的学术意义和现实意义。 1 2 间歇化工过程调度研究进展 1 2 1 调度的研究方法 间歇过程调度建模方法根据时间表达方式可以分为两种：离散时间表达 ( d i s c r e t e t i m er e p r e s e n t a t i o n ) 、连续时间表达( c o n t i n u o u s t i m er e p r e s e n t a t i o n ) 。 1 2 1 1 离散时间表达的间歇过程调度 此方法最早由b o w m a n ( 1 9 5 9 ) 8 1 和m a n n e ( 1 9 6 0 ) 9 1 提出。这种方法将整个调 度的时间分解为一系列等长的时间间隔( t i m ei n t e r v a l s ) ，而调度中的所有事件( 例 如工序的开工、完工) 都发生在这些时间间隔的边界。这种方法的特点是为共享 资源的相互竞争的操作提供了一个参照系，将调度中的各种各样的约束在各个小 时间段内直接地描述出来。 k o n d i l i ( 1 9 9 3 ) 1 0 l ，s h a h ( 1 9 9 3 ) t 1 1 1 ，d e d o p o u l o s ( 1 9 9 5 ) 1 如，z e n t n e r ( 1 9 9 4 ) t 1 3 1 ， 青岛科技大学研究生学位论文 b a s s e t t ( 1 9 9 6 ) 【1 4 1 ，e l k a m e l ( 1 9 9 7 ) t 1 5 1 等人对该方法作了进一步的研究。 这种离散时间表达的建模方法有两个显著的缺点： ( 1 ) 由于时间本身的连续性和调度中概念的离数性之间的矛盾，使得该方 法只能是真实过程的近似逼近，因而解的最优性也不能保证。 ( 2 ) 为了达到满意的逼近效果，不可避免地要尽量缩短时间间隔的长度， 随之而来是调度问题变量数的急剧增加。这对调度问题的求解是一个很大的负 担，甚至由于规模过大而难以求解。所以该方法不适合求解较大规模的问题。 1 2 1 2 连续时间表达的调度问题 鉴于离散时间表达的局限性，近十几年来连续时间表达的方法受到关注。连 续时间表达的调度模型允许调度中的事件在任意时刻发生，而不像在离散时间中 那样只能在时间间隔的端点发生。在建模时，该方法去掉了离散方法中不必要的 变量，所以其规模一般较小。但是由于事件发生时间的多样性，连续时间表达的 数学模型在结构上比离散时间表达的模型要复杂。图1 5 给出了离散时间表达方 法和连续时间表达方法时间划分的对比。 h 斗十h _ 十刊斗+ h 叶十八，h 斗巾h 呻十h 叶+ 卅+ 斗_ 卜 i2 $ ，。y - - - - r * l i ih 1 n m 图l 一5 离散和连续时问袁速j 埘 f i g u r e1 - 5d i s c r e t ea n dc o n t i n u o u sr e p r e s e n t a t i o n so f t i n = 1 e 在连续时间表达的调度建模方法中又将间歇化工过程分为顺序过程 ( s e q u e n t i a l p r o c e s s e s ) 和网络结构过程( n e t w o r k - r e p r e s e n t e d p r o c e s s e s ) 。顺序过 程是面向订单或者面向批次的，产品的所有原料同步进入生产线，在加工过程中 没有物料的合并和分割；所以顺序过程不必明确地表达物料平衡。而网络结构过 程则必须考虑物料平衡约束。 1 、顺序过程( s e q u e n t i a lp r o c e s s e s ) 调度 最早的顺序过程连续时间表达的模型是基于时间槽( t i m es 1 0 t s ) 概念的。此 方法将每个设备在整个过程的运行情形分为若干个时间槽来考察。 青岛科技大学研究生学位论文 以下是个带平行单元的多阶段流水作业问题的连续时间模型： 是一个逻辑变量，表示订单( f ) 的( ，) 工序在时间槽( 七) 内是否在设 备( ，) 上操作；7 h ，z 知是实数变量分别表示：订单( f ) 的( ，) 工序的开始时 间和完工时间。7 奴表示设备) 的时间槽( 七) 的开始时间。则设备的分配约束 可表示为： = l ，v i e l ，f 厶 ( 1 - 1 ) j 自l | i n j i 、t e x l ，w ，k c k i ( 1 2 ) te ) il h h n l i l 对批次完工时间和开工时间约束可以表示为： m ( 1 一h 知) 岛一t s j d f ( 1 一h 知) ，v f e ，j n j d ，k e k ，z n 工： ( 1 - 3 ) 死岛乃刖+ 1 ) ，v i e ，厶一 罨 ( 1 - 4 ) 该方法引入了一个四维变量陟，所以问题规模也较大；而且时间槽的数目 是预先给定的，所以不能保证结果的最优性。p i n t o ( 1 9 9 8 ) 17 1 ，k a r i m i ( 1 9 9 7 ) 1 1 8 】， l a m b a ( 2 0 0 2 ) 1 9 1 1 2 0 1 ，b o k ( 1 9 9 8 ) t 2 1 1 ，m o o n ( 1 9 9 9 ) 2 2 1 等对该方法作了研究。 鉴于该类间歇过程的面向订单的特征，可以直接定义连续性变量来表达过程 的时间分配而不需要依赖于时间槽。这种方法已经用于许多过程的连续时间调度 模型。m & a d e z ( 2 0 0 0 ，2 0 0 1 ) 2 3 ，m o o n ( 1 9 9 6 ) t 2 鄂，h l l i ( 2 0 0 1 ) 2 6 ，o r p u n ( 2 0 0 1 ) 2 7 1 ， l e o ( 2 0 0 2 ) 2 8 】等都做了相关研究。这种直接用连续变量来表达的数学模型比基于 时间稽的数学模型更准确结果也较好。但是模型的复杂性增加了。 顺序过程的连续时间模型可以用来解决很多调度问题，并且可以考察如下因 素：不同的中间存储策略、依赖于次序的物料转移、间歇或连续过程、交货日期 在过程完成之前、可再生的资源约束、以及不同的目标函数：如最小完工提前， 总完工时间( m a k e s p a n ) 最小等。 2 、网络结构过程( n e t w o r k - r e p r e s e n t e dp r o c e s s e s ) 在网络结构的间歇过程中允许物流的合并与分割，所以需要特别注意物料平 衡。这类过程的连续时间调度模型有两类建模方法。第一类方法对所有的加工任 务和设备单元统一定义事件或时间槽，称之为基于全局事件的调度模型( g l o b a l e v e n tb a s e dm o d e l s ) 。第二种方法基于设备单元来定义事件，是一个更严格也更 一般的表达方法，称之为基于特定单元事件的模型( u n i t - s p e c i f i ce v e n tb a s e d m o d e l s ) 。 以上两种方法一般都是使用状态一任务网络( s t a t e t a s k n e t w o r k ，s t n ) 或者 资源一任务网络( r e s o u r c e t a s k n e t w o r k ，r t n ) 来建模。这两种方法将实际过程 青岛科技大学研究生学位论文 表示为直观的图形。在图中，用不同的元素代表过程中的各种生产要素。 k o n d i l i ( 1 9 9 3 ) i 加】提出用s t n 来表达过程。在s t n 图中包含两类节点，用圆 表示状态节点，代表原材料、中间产品和成品；用长方形来表示任务节点，表示 生产操作。图1 - 6 是文献1 2 9 】中一个经典的状态任务网络的例子，在该间歇过程中， 包括三个反应和一个分离过程。物料c 与物料b 发生反应1 产生的中间产品进入 储罐b c ，然后在与物料a 发生反应2 得到产品p 1 和中间产品，中间产品经过储 罐a b 后与c 发生反应3 ，反应后的物料经过分离得到产品p 2 和中间产品a b 。 而在r t n 中将加工设备、储罐、原材料的转移和使用统一表示为资源。 k 图i - 6 状态任务网络的例子删 f i g u r e1 - 6 a ne x a m p l eo f s i n 基于全局事件的连续时间调度模型用连续时阃变量来对事件计时或者表示 各个不同时间槽豹长度，然后用一系列逻辑变量来表达重要的状态变化。z h a n g 0 9 9 5 ) 圳最早提出了基于s t n 网络和r t n 网络的连续时间调度模型。模型的主 要变量如下： 疋：连续变量，表示事件( 七) 的发生时间； 阡k ：逻辑变量，表示单元u ) 上的( f ) 任务是否在时间靠开始； 冯融t ：逻辑变量，如果任务( f ) 在时间及开始，且在时间聂结束。 0 = 写( 互 五h ( 1 - 5 ) h 表示时间上限。约束( 1 - 6 ) 用来保证单元( ，) 上的( f ) 任务在( 七) 时刻 开始，并在其后的时刻结束。任务的持续时间则由约束( 1 - 7 ) 表示。 = ，v i e j ，j 以，k k ( i - 6 ) l t = 艺鼍肿( 瓦一正) v i ，j 以，七k t c a s t r o ( 2 0 0 1 ) p l 】提出了一种基于r t n 网络的间歇过程短期调度的m i l p 连续 时间模型。m a j o z i ( 2 0 0 1 ) 3 2 】基于一种状态顺序网络( s t a t es e q u e t l c en e t w o r k ) 提 出了间歇越程短期调度的连续时间m i l p 模型。b u r k a r d ( 2 0 0 2 ) ：二】和w a n g ( 2 0 0 2 ) 3 4 】 青岛科技大学研究生学位论文 也对基于全局事件的调度模型做了研究。 这种基于全局事件的模型，有一个主要难题就是如何选择事件点( e v e n t s p o i n t ) 的数目。较少的事件点会得不到最优解或者得到不可行解；而增加事件点 的数目又会增加变量数目从而扩大问题规模。 基于特定单元事件的模型与基于全局事件的模型的主要区别是针对每一个 单元定义事件点，即设备单元上发生事件时才有该单元的操作信息。而基于全局 事件的模型在每一个事件点上都要记录所有单元的操作信息。显然基于特定单元 事件的模型参数数目要少很多。 i e r a p e t r i m u ( 1 9 9 8 11 3 5 等提出的这种新的调度模型中，其事件点的定义为：事 件点是设备单元的时间轴上的一系列时刻点，这些点将设备的时间轴分割为多个 时间段：而在每一个时刻点发生一次操作状态的变化，如任务的开始或者结束。 显然这种方法也面临着如何确定事件点的数目问题。事件点数目的确定只艟 通过逐步增加数目，直到增加数目对过程的解改进效果不明显。由于这种方法对 事件点的使用效率高，而且过程中的事件点数目较少，所以能够更快的找到适当 的数目。l i n ( 2 0 0 2 ) 3 6 】研究表明该方法可以用于中等规模的中短期工业调度问题。 1 2 2 不确定性调度研究 根据对不确定性因素处理思路的不同，不确定性调度可以分为随机调度和反 应型调度。 1 2 2 1 随机调度( s t o c h a s t i cs c h e d u l i n g ) 在产生调度时即考虑不确定性因素，其目的是在考虑不确定性因素的情形下 产生可行的最优调度。s a n m a r t i ( 1 9 9 5 ) i ”针对多目的厂设备故障的不确定性，对生 产调度的每一步骤进行不确定性分析，实现了设备维修0 讧a i n t e n a n c e ) 与生产的集 成。b a s s e t t ( 1 9 9 7 ) 弘】提出了个柔性调度的框架，在此框架中考虑了如下的不确 定性因素：操作时间波动，设备可用不可用，过程产量、需求及人员变化。他们 利用m o n t ec a r l o 抽样来产生随机事件，并对每个事件产生一个调度；其缺点是 产生的应对方法都是预先设定的。h o n k o m p ( 1 9 9 9 ) 1 3 9 】利用随机仿真模型捕捉参数 的变化，然后用确定性模型对调度的预测结果进行比较，并选出鲁棒性高的调度 策略。 随机调度先预测出所有可能出现的情形，然后根据一定的规则给出该情形下 的目标函数的期望值以得到目标函数的最大期望值。此方法要对可能的情形给出 一个离散的概率分布，或这将连续的分布函数进行离散化。这样产生调度时就隐 含了不确定性因素，但是由于不确定性因素增加时，其可能的情形数目是以指数 青岛科技大学研究生学位论文 规律增长的，所以显著扩大了问题的规模，另外此方法没有得到严格证明，不能 保证得到最优解，其应对策略一般源于个人经验，规则难以统一。 此外还有人尝试将随机型模型转换成确定性等价类( d e t e r m i n i s t i c e q u i v a l e n t ) 。此方法巧妙地绕过离散化和随机取样的要求，避免了问题规模的不 必要的扩大，展现了其能够处理具有大量非确定性因素问题的能力。 o r v u n a l t i n e l ( 1 9 9 6 ) t 4 0 】考虑间歇过程操作时间的不确定性，并利用机会约束来 计算特定情形下破坏约束的风险( 例如统一分配函数u n i f o r md i s 舡i b u t i o n f r i c t i o n s ) 。 b a l a s u b r a m a n i a n ( 2 0 0 2 ) d l l 提出一种用于多级流水作业问题的多阶段m i l p 模 型可以处理操作时间的不确定性问题。最近l i n ( 2 0 0 4 ) t 4 2 】提出了一般间歇厂不确定 型调度的新的鲁棒优化模型，用连续时间m i l p 表述。其下层模型是基于鲁棒优 化策略的，将其用于m i l p 问题产生“鲁棒”解，在某种意义上预防了不等式约 束中的系数和当前参数的不确定性。此方法可以用来在加工时间，产品需求和原 材料价格不确定时产生可信赖的调度方案，。 考虑不确定性因素( 用随机变量表达) ，使确定性调度的m i l p 和m i n l p 模 型中增加一类随机变量，使问题的建模和求解更加复杂。本来可以用标准数学规 划方法求解的调度问题转变成需要特殊技术的随机问题。 1 2 2 2 反应型调度( r e a c t i v es c h e d u l i n g ) 反应型调度也称为动态调度( d y n a m i cs c h e d u l i n g ) ，一般首先由确定性调度产 生一个原始调度，根据过程的实时状况，对原有调度进行调整，以使生产约束得 到满足，生产代价最小【1 6 】。c o t t ( 1 9 8 9 ) 1 4 3 】曾在问歇过程大型计算机辅助生产管理 系统中使用反应型调度处理加工时间变化的问题。反应型调度包含了重调度 ( r e s c h e d u l i n g ) 与在线调整( o n 1 i n em o d i f i c a t i o n ) 两个方面。其任务是指根据来自设 备的反馈信息和实际的系统状态数据，决定下一步执行哪个操作，它的目标是在 整个过程遇到扰动和故障时，根据系统监控到的实时情况修改原定的生产顺序和 调度系统的所有资源，使批处理系统持续地、优化地运行】。 当生产条件及参数变化时，要求反应型调度能快速地对变化做出反应。所以 完全重调度的方法一般是不合适的，因为重调度要花费较大的代价和相当的时 间，难以满足调度的实时性；而且重调度安排可能与原来的调度有很大的差异， 从而破坏过程操作的延续性，所以只有在参数变化较大以至于必须对调度进行重 大改动时才使用重调度策略。在线调整的主要任务是在参数变化较小时对调度或 过程进行在线调整，适当地修改原始调度或过程操作参数以使过程得以继续执 行。反应型调度主要包括以下几种方法： 青岛科技大学研究生学位论文 ( 1 】设置中间储罐法： 此法是k a r i m i 4 5 1 于1 9 8 5 年提出的，通过在两个间歇级之间设置中间储罐， 把不能及时处理的物料暂时保留在储罐中，使上下两级解耦，以消除时间变化对 操作的影响，使原来的调度仍然可用。但是考虑到化工产品的不稳定性和工艺操 作条件的限制，这种设置中间储罐的方法就受到了局限。况且究竟设置多少储罐 可以满足要求也不好确定。 ( 2 ) t 艺条件改变法： 此方法基于对将来工艺状态的预测，当处理时间变化时，动态地改变工艺条 件如温度、压力等，控制特定任务的处理时间，使操作返回原有的调度。可是产 品质量在很大程度上取决于工艺操作条件，另外改变工艺条件也增加了工艺条件 控制的困难。此方法的思想一些文献都提到，但未见有具体的研究和实例。 ( 3 ) 调度修改法( 调度的在线调整，o n - l i n em o d i f i c a t i o n ) ： 上述两种方法，通过调整过程本身，使过程适应原来的调度时间表。两者均 假定用于产生调度的时间是实际处理时间的精确表示，并且原调度是最优调度。 事实上调度使用的处理时间，是对已往运行中观察到的处理时间的粗略估计或简 单平均；因此原调度本身的正确性就值得怀疑。况且间歇过程运行的实际情形在 给出调度时是根本不可能完全预见的，那么在实际过程与原调度发生偏离的时 候，原调度本身的最优性也值得商榷。所以一味地将已经发生偏离的实际过程按 原来的调度次序执行并不是一个明智的做法。应考虑对调度安排进行动态修改( 即 在线调整) ，使其适应过程的动态变化并优化调度目标。 此方法是在不确定性因素出现时，在尽量保持过程的延续性的基础上通过对 调度方案进行适当的修改提供在新情形下可行的最优调度。k a n a k a m e d a l a f , 6 j 提 出了基于对后续操作影响最小的启发式方法，可有效地减小处理时间及设备可用 性变化的影响。通过将受干扰的操作依次进行简单移动或更换其所使用的设备， 较快地求得新的调度。r o d r i g u e t 4 7 1 将k o n d i l i 1 0 1 的状态一任务网络( s t a t et a s k n e t w o r k ，s t n ) 表示与滚动时域( r o i l i n gh o r i z o n ) 方法相结合，将总调度时间 划分为若干滚动时域，在每一时域上利用s t n 建模，并对其进行逐次求解。因每 次调度只对小调度区间内的操作进行，减小了问题求解的规模。在每一时域中， 将到期时间早的操作分配在任务等待队列较短的设备上处理，减少设备争用和操 作延迟。这种调度策略，当过程操作出现较大扰动时，才采取重调度，维持了生 产的连续性；通过调度区间的滚动，捕捉过程的动态扰动。处理产品原始交货期 及设备可用状态的变化。 相对而言反应型调度比随机调度更具有实时性、更灵活、求解也相对简单， 而且其在制造行业已有一定程度的应用。但随机调度对不确定性因素的处理思怒 青岛科技大学研究生学位论文 具有借鉴意义，建模时应综合考虑。 反应型调度中的在线调整方法要求能够迅速根据变化情形给出调度的调整 方案，所以对求解速度要求较高。如何建立更简单有效的模型和探索更高速的求 解方法受到众多研究者的关注。 1 3 间歇调度问题的求解策略 调度模型建立后，其求