（化学工艺专业论文）列队竞争算法在化工生产调度中的应用研究.pdf

摘要 生产调度是企业生产管理的核心内容和关键技术，好的调度方案能够合理 分配任务和资源，降低生产成本，提升企业的生产经营效率和快速应变能力， 从而增强企业的竞争力。因此，开展对生产调度问题的研究，为企业提供科学、 高效的生产调度方案将具有重要的意义。 本文对几种典型的化工生产调度问题进行了分析和研究，主要做了以下几 个方面的工作。 概述了化工生产的基本特点，并讨论了化工生产中所存在的基本调度问题 和难点调度问题。综述了求解生产调度问题的几种经典和现代最优化方法。 研究了零等待的顺序型多目的化工厂生产调度问题，针对以总生产完成时 间( m a k e s p a n ) 最短为目标函数的调度优化模型，提出了一种启发式的“离散回 缩”策略，有效地简化了在一定生产排序下的总生产完成时间的计算。应用列 队竞争算法对产品加工排序的组合优化问题进行了求解研究，确定出了较好的 变异邻域策略，提高了收敛速率。 对锅炉蒸汽系统循环调度问题进行了研究。分析了锅炉蒸汽系统循环调度 问题的基本特点，提出了时间分段的问题分解策略，在此基础上建立了此循环 调度问题的混合整数非线性模型。应用列队竞争算法对该问题进行了求解分析， 并结合某个生产过程锅炉蒸汽系统循环调度实例进行了研究。实例计算结果表 明，循环调度优化能够取得明显的节能效果。 研究了发酵过程中空气供应量受限的一种资源受限调度问题。建立了以资 源限制为约束条件，以总生产完成时间最短为目标函数的优化调度模型。应用 列队竞争算法对某个生物农药厂的发酵生产调度问题进行了求解，获得了优化 的生产调度方案。此问题的研究对资源受限的一类调度问题具有重要的参考作 用。 以某生物农药厂发酵生产为背景，开发出了基于m a t l a bw e bs e r v e r 的优化 调度远程决策支持系统，该系统实现了生产调度优化方案的远程在线生成，提 高了调度工作的效率和资源利用率。 关键词：列队竞争算法，最优化，间歇生产调度，循环调度，m a t l a bw e b s e r v e r 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 ec o r ec o n t e n ta n dt h ek e yt e c h n o l o g yo fe n t e r p r i s e s p r o d u c t i o nm a n a g e m e n t ag o o ds c h e d u l i n gp r o g r a mc a nd i s t r i b u t et a s k sa n d r e s o u r c e sr e a s o n a b l y , r e d u c et h ep r o d u c t i o n c o s t s ，a n di m p r o v et h ep r o d u c t i o n o p e r a t i o ne f f i c i e n c ya n dt h er a p i d l yr e s p o n s ec a p a b i l i t yo fe n t e r p r i s e s ，a c c o r d i n g l y e n h a n c et h ec o m p e t i t i v e n e s so fe n t e r p r i s e s t h e r e f o r e ，s t u d yo nt h e p r o d u c t i o n s c h e d u l i n gp r o b l e m s ，p r o v i d i n gs c i e n t i f i ca n de f f i c i e n tp r o d u c t i o ns c h e d u l i n g p r o g r a m sf o re n t e r p r i s e s ，i so f g r e a tp r a c t i c a lv a l u e t h i sp a p e ra n a l y z e ds e v e r a lt y p i c a ls c h e d u l i n gp r o b l e m si nc h e m i c a lp r o d u c t i o n , a n dt h em a i nr e s e a r c hc o n t e n ti sa sf o l l o w s ： p r e s e n tt h em a i nc h a r a c t e r i s t i c so f c h e m i c a lp r o d u c t i o n , a n dd i s c u s s e dt h eb a s i c a n dt h ed i f f i c u l ts c h e d u l i n gp r o b l e m se x i s t e di nc h e m i c a l p r o d u c t i o np r o c e s s s e v e r a lc l a s s i ca n dm o d e mo p t i m i z a t i o nm e t h o d sf o rp r o d u c t i o n s c h e d u l i n g p r o b l e m sw f f f es u m m a r i z e di nt h i sp a p e r t h e p r o d u c t i o ns c h e d u l i n gp r o b l e mo fs e q u e n t i a lm u l t i p u r p o s ec h e m i c a lp l a n t w i t hz e l o w a i t ( z w ) p o l i c yw a ss t u d i e d f o rt h eo p t i m a ls c h e d u l i n gm o d e lw i t h o b j e c t i v ef u n c t i o no fm a k e s p a n ，t h i sp a p e rp r e s e n tah e u r i s t i c “s e p a r a t e c o n s t r i c t s t r a t e g yt os i m p l i f yt h ec a l c u l a t i o no f t h em a k e s p a ni nac e r t a i np r o d u c t i o ns e q u e n c e u s i n gl i n e - u pc o m p e t i t i o na l g o r i t h m ( l c a ) t oo p t i m i z et h ep r o d u c t i o ns e q u e n c e ， s i m u l t a n e o u s l y , ap r o p e rm u t a t i o ns t r a t e g yw a sp r o p o s e dt oi m p r o v et h er a t eo f c o n v e r g e n c e - t h eb o i l e rs t e a ms y s t e mc y c l i cs c h e d u l i n gp r o b l e mw a si n v e s t i g a t e d p r o p o s e d as u b - t i m es t r a t e g yf o rt h i ss c h e d u l i n gp r o b l e m ，a n de s t a b l i s h e dam i x e d - i n t e g e r n o n l i n e a rp r o g r a m ( m i n l p ) m o d e lb a s e do nt h ep r o p o s e ds t r a t e g y l c aw a s a d o p t e dt os o l v et h em i n l pp r o b l e m ，a n dac a s eo fb o i l e rs t e a ms y s t e mc y c l e s c h e d u l i n gp r o b l e m w a ss t u d i e d t h er e s u l t ss h o w e dt h a t c y c l es c h e d u l i n g o p t i m i z a t i o n c a l la c h i e v er e m a r k a b l ee n e r g ys a v i n ge f f e c t t h ef e r m e n t a t i o np r o c e s sw i t ha i rs u p p l yc o n s t r a i n t ，ak i n d o fr e s o u r c e c o n s t r a i n t s ，w a sa n a l y z e d a no p t i m a ls c h e d u l i n gm o d e l ，w h i c hh a dr e s o u r c e c o n s t r a i n t sa n da d o p t e dm a k e s p a na so b j e c t i v ef u n c t i o n , w a sb u i l t a p p l i e dl c a t o s o l v et h es c h e d u l i n gp r o b l e mo f ab i o l o g i c a lp e s t i c i d ep l a n t a n do b t a i n e da no p t i m a l s c h e d u l i n gp r o g r a m t h es t u d yo ft h i sp r o b l e mi sa ni m p o r t a n tr e f e r e n c et o t h e s o l u t i o no f r e s o u r c e c o n s t r a i n ts c h e d u l i n gp r o b l e m s j i ar e m o t es c h e d u l i n go p t i m i z a t i o ns y s t e m , b a s e do nm a t l a bw e bs e r v e ra n di n t h eb a c k g r o u n do ff e r m e n t a t i o np r o c c s so f a m o l o g i c mp e s t i c i d ep l a n t ，w a sd e s i g n e d t h i ss y s t e mr e a l i z e sar e m o t co n - l i n eo p t i m i z a t i o nt op r o d u c t i o ns c h e d u l i n g , a n d i m p r o v e st h ee f f i c i e n c yo f s c h e d u l i n ga n dr e s o u r c eu t i l i z a t i o n k e yw o r d s ：l i n e - u pc o m p e t i t i o na l g o r i t h m ，o p t i m i z a t i o n ，b a t c hp r o d u c t i o n s c h e d u l i n g ，c y c l i cs c h e d u l i n g ，m a t l a bw e bs e r v e r h i 武汉理工大学硕士学位论文 第1 章绪论 生产调度是企业生产管理的核心内容和关键技术，好的调度方案不仅能够优 化资源利用，降低生产成本，而且能够提升企业的生产经营效率和快速反应能力， 从而为企业带来较强的竞争优势i i 】。 生产调度问题已越来越引起企业界的重视。随着全球经济一体化趋势的加 剧，企业之间的竞争将日趋激烈，越来越多的企业认识到要想在激烈的市场竞争 中生存，就必须对市场的变化做出快速反应。因此，加强技术的改造与创新，从 生产管理中挖掘效益，不断提高企业的竞争力，是企业的必然选择。与此同时， 企业之间的激烈竞争也促使企业引进越来越复杂的生产制造系统，新系统已产生 了新的生产调度优化问题，这些都是企业迫切需要解决的问题1 2 , 3 】。 生产调度作为生产管理最为困难的问题，吸引了国内外许多学者和实际调度 人员的关注1 4 ，特别是近年来随着相关学科( 运筹学、应用数学等) 及优化技术的 发展，在调度领域出现了许多新的优化方法，比如基于人工智能、计算智能和实 时智能的各种智能调度方法，这些都推动了生产调度问题研究的不断深入和发 展，目前，对生产调度问题的研究已经成为领域内的研究热点。 本章简要地介绍了本文工作的研究背景。首先概述了化工生产的基本特点， 讨论了化工生产中所存在的基本调度问题和难点调度问题，接着简单介绍了求解 生产调度问题的几种常用的最优化方法，最后概括了本文的主要研究工作。 1 1 化工生产概述 化工行业包括石化、医药、塑料、化妆品以及许多生产中间化学品的行业， 是国民经济的重要产业【5 1 。在上世纪3 0 年代，大部分化工过程以间歇方式操作， 主要依靠操作工人的工作经验来安排生产，不仅自动化水平低、劳动强度大，而 且产品质量不稳定。为此，化学工程师们致力于将间歇方式改为连续生产方式。 化工过程一直是朝着连续加工方向发展，尤其是大规模生产过程更是如此。直到 5 0 年代人们还普遍认为技术员最终的使命就是将“古老”的间歇过程转变为现代 化的连续过程，这是由于随着加工任务的扩大，对工作效率、能源消耗、产品质 量等提出了更高的要求，于是出现了化工企业向大型连续稳定生产方式转变的热 潮。所以在上世纪无论是模拟分析、还是实时优化，都是以稳态、连续过程为主， 这些技术基本上满足了上世纪化学工业发展的要求删。进入颏世纪后化学工业出 现了新的要求：( 1 ) 产品的个性化强，以满足客户的特定需求；( 2 ) 生产是根据客户 需求进行产品设计，然后是过程设计；( 3 ) 生产产品的投资少、见效快，以快速满 足不断变化的市场需求；( 4 ) 生产是柔性生产，便于多产品、多牌号生产，改造更 武汉理工大学硕士学位论文 新也比较容易。鉴于间歇生产过程能满足上述要求，特别适应批量小、产值高、 品种多、变化易、上市快的生产，所以2 l 世纪间歇过程又将成为化工过程的重 要生产形式之一。 目前化工生产的发展有两个方面的明显趋势：对于一些数量需求很大的产 品，趋于采用连续生产方式，扩大单个装置的处理量以追求规模效益，如汽煤柴 油、尿素和乙烯的生产等。另一方面，对于许多数量要求不大，但品种和牌号有 多种不同变化要求的产品，趋于向精细化发展的化工间歇生产方式，这种生产方 式需要有很大的柔性，用有限量的标准设备，通过不同的组织方式，以满足多品 种、高质量和高附加值的市场化需求【”。 1 2 化工生产调度问题 1 2 1 问题描述 生产调度是在一定的时间内，进行可用共享资源的分配和加工任务的排序， 以满足某个或某些特定的生产指标。生产调度主要涉及生产作业的具体安排和资 源的详细分配。其中，共享的生产资源包括：原料、加工设备、存贮设备、运输 设备、人力、资金和能源等；加工任务就是在指定时间内生产特定的产品，这些 产品既可是用户订购的产品，又可是根据市场需求计划生产的产品；生产指标制 定的目的是为了尽可能获得最大的经济效益和较好的社会效益，所以生产指标一 般定为成本最低、库存费用最少( 减少流动资金占用) 、生产周期最短、生产切换 最少、设备利用率最高等。 化工生产过程中，物料进入某个设备、开始加工、直至离开该设备，称为一 个生产步骤，每个生产步骤中包括若干个离散事件。事件是引起研究对象系统状 态发生变化的行为，例如以间歇生产过程作为研究对象系统，对象系统中的元素 是设备和物料，生产过程中开启阀门、开始加工、加工结束等事件就会引起对象 系统状态的变化( 设备空闲状态的变化、物料流动等) 。本文中所指的化工生产加 工过程是指从原料到最终产品在经过的各个生产步骤中的离散事件序列，本文所 研究的化工生产过程是狭义上的化工过程，并不包括全部工艺意义( 不涉及物流本 身的化学性质) ，仅仅是指物料由一个设备进入另一个设备的离散事件时间序列， 表现出来的是物质资源的流动。本文研究的化工生产过程调度问题着重在于设备 的优化调度，调度体现在一张“切换操作调度表”中，从一个设备到另一个设备的 物料通道的打开或关闭称为一个切换操作，每一切换操作指令可以引发一个或多 个离散事件的执行。通过对化工生产过程的研究，建立优化调度模型，制定调度 方案【刀。 2 武汉理工大学硕士学位论文 1 2 2 化工生产中的热点调度问题 化工生产过程中目前难以求解的热点调度优化问题主要有：循环调度优化和 间歇化工厂生产过程调度优化两类问题。 循环调度主要存在于一些大型连续化工生产过程中，在这些生产过程中，一 般有多台并行设备，其中至少有一台设备作为备用，随着设备运行时间的增加， 设备的性能或效率下降，而且各个设备性能下降的曲线不同，在此条件下，循环 调度要解决的问题是：确定每个设备的停运( 以恢复其性能) 和备用设备的启动时 间，以使在考虑的时间内总费用最少。这类问题的典型例子有催化反应器中韵催 化剂逐渐老化，需要更新或活化；裂解炉炉管内壁逐渐结焦，需要清焦，锅炉的 管壁逐步结垢，需要清洗等。这类调度问题可归结为混合整数非线性规划问题 ( m i n l p ) 来求解，问题的求解时间将随锅炉总数的增加呈指数增加，近年来这类 调度问题的研究报道不少，但目前的进展不大1 8 1 。 间歇化工厂的调度问题属于比较典型的生产调度问题，一般可分成两类：多产 品( m u l t i p r o d u c t ) 厂和多目的( m u l t i p u r p o s e ) 厂。在多产品厂中所有产品的处理步 骤都相同，类似于流水作业( f l o w s h o p ) ：而在多目的厂中，产品可以有各自不相 的处理步骤，类似于工件作业( j o bs h o p ) 。前者的调度问题在理论和应用研究方面 已相当成熟，但后者的调度问题研究进展相对滞后，对规模较大的多目的厂调度 优化的求解一直是一个难题，如果再考虑有资源限制条件的约束，则求解将更加 的困难。然而，当今有资源条件限制的多目的厂的调度问题在间歇化工生产企业 中又相当的普遍，目前对这一问题的研究已经引起了国内外许多学者的关注【9 - 1 1 】， 但由于问题本身的复杂性，研究还停留在中小规模的调度问题上，缺乏有效的优 化调度方法。 上述两类问题是目前化工生产调度领域中研究的热点和难点问题，对它们的 求解取得突破，具有重要的理论和实际意义。 1 3 求解生产调度问题的最优化方法 生产调度问题的研究方法最初集中在数学规划、仿真调度和简单的规则上， 这些方法只适用于求解中小规模的生产调度问题，对于大规模调度问题的求解效 果不好。随着各种新的相关学科与优化技术的建立和发展，在调度领域出现了许 多新的优化方法，近年来，模拟退火法、t a b u 搜索法、神经网络和进化算法等依 据自然法则具有智能因素的搜索算法在解调度优化问题中得到了相当广泛的研究 和应用，在解决诸多难的调度优化问题上显示出了较好的特性，取得了比传统方 法要好的结果。下面对这些搜索算法作一概述。 武汉理工大学硕士学位论文 ( 1 ) 数学规划法 数学规划法( m a t h e m a t i c a lp r o g r a n 1 m i n g ) ：是把生产调度问题归结为一个较为 符合实际的包括若干限制条件的模型，在此基础上建立一个有约束、多变量的最 优化模型，再采用适当的算法得到问题的最优解。在化工生产过程的研究中，通 常建立的是m i l p 或m i n l p 模型，求解的方法主要有分支定界法、外近似法和广 义b e n d e r s 分解法等，这几种方法都在间歇过程问题的求解中得到应用。但这些 方法的求解要么采用对所有节点的树枚举法，要么将原问题的数学模型采用一定 的方法分解为m i l p 和n l p 进行求解。由于间歇过程调度问题的组合爆炸特性， 问题的求解时问往往与问题的规模成指数函数关系，如果建立模型为规模较小的 m i l p 或m i n l p 模型，可以采用一些优化软件包如l i n g o 、g a m s 等求解( j a e e t a 1 1 9 9 4 ；潘明，钱宇，李秀喜，2 0 0 6 ) 1 2 以3 1 ，而对于规模较大的问题，求解一般很困 难，需根据问题的特点选择方法。目前对于这类问题的求解，一是对特殊形式的 问题，寻找普遍化的算法；或者是对精度要求不是很高的问题，使用启发规则来 求得一个满意解；另外就是借鉴其它学科的发展，寻找一些智能型的方法。 ( 2 ) 模拟退火法 模拟退火法( s i m u l a t i o na n n e a l i n g ，s a ) 是一种基于热力学退火原理建立的随 机搜索算法。s a 算法的思想最早是由m e t r o p o l i s 于1 9 5 3 年提出的【1 4 】，后来由 k i r k p a t r i e k 等人研究发展了s a 算法的理论 1 5 1 。在化工生产调度领域s a 算法已 用于多产品化工过程最优设计与调度问题的求解( d a se ta 1 ，1 9 9 0 ；p a t e le ta 1 ，1 9 9 1 ： 王举，袁希钢，2 0 0 0 ) 1 6 - 1 8 ，并取得了满意的结果。 s a 算法解优化问题的出发点是基于固体物质的退火过程与优化问题的相似 性。在对固体物质进行退火处理时，通常是将它加温熔化，使其中的粒子可自由 运动，然后逐渐降低温度，使粒子形成低能态的晶体。如果温度下降的足够慢， 则固体物质一定会形成最低能量的基态。对于优化问题也有这样类似的过程，优 化问题解空间中的一点代表一个具有不同目标函数值的解，若把目标函数看成是 能量函数，某一控制参数视为温度，解空间当作形态空间，那么，s a 算法寻找 基态的过程也就是求目标函数最小值的过程。 在s a 算法的搜索过程中，为防止陷入局部最优解，s a 算法使用基于概率的 双向随机搜索技术；当基于邻域的一次操作使当前解的质量提高时，s a 算法接 受这个解；在相反的情况下，s a 算法以一定的概率接受质量较差的解。并且接 受质量较差解的概率随搜索过程的进行慢慢趋向于零，这使得算法有可能从局部 最优解中跳出，尽可能找到全局最优解。 s a 算法存在的主要问题是当目标函数有较深的局部最优解时，仅利用随机 性难以跳出局部最优解；另外，由于没有记录搜索的历史信息，有可能多次搜索 4 武汉理工大学硕士学位论文 到同一解或同一区域；此外，控制参数( 最高温度、内循环次数、降温速率和终止 温度等) 不易选定，且收敛速率太慢。 ( 3 ) t a b u 搜索法 t a b u 搜索法是一种启发式搜索算法。最早由g l o v e r 提出【1 9 1 ，具有记忆功能 是t a b u 搜索法的特点之一，算法的核心是利用列表形式记录搜索的历史信息，用 以控制搜索过程。近年来人们对此算法进行了深入地研究，c a v i nl 等a ( 2 0 0 4 ) 2 0 1 运用t a b u 搜索法求解多目的厂的多目标过程设计问题；y a n gt 等人( 2 0 0 4 1 【2 1 悃 t a b u 搜索法解决多处理机的流水作业调度问题，取得了满意的效果。该算法的框 架可描述如下： 1 ) 由随机方式产生一初始可行解作为当前解，确定初始列表； 2 ) 从当前解的邻域中搜索除列表中可行解以外的最优解； 3 ) 当前解取为所搜索的最优解； 4 ) 调整列表； 5 ) 若满足终止条件，则停止；否则，转到第( 2 ) 步。 算法在搜索过程中为了避免陷入局部最优解，允许一定的上山操作( 解的质量 变差) 。另外，利用列表形式记录搜索的历史信息，可避免搜索路径的往返重复， 并可在一定程度上使搜索过程避开局部极值点，开辟新的搜索区域。在实际应用 中，列表可以非常灵活，它可以把各种先验知识、规律、搜索的历史信息和解的 性质等用列表的形式记录下来，从而控制搜索过程。 t a b u 搜索法的灵活性使得它很容易与其他算法结合起来，如与遗传算法的结 合】，可以改善遗传算法的局部搜索能力，提高优化的质量和搜索效率。 t a b u 搜索法的主要问题是列表的大小( 控制参数) 不易确定。一般来说，太小 的列表可能无法避免搜索路径的往返重复，这将影响算法的全局搜索性能；另一 方面，列表过大除了增加计算时空复杂度外，还可能因列表对搜索区域的过分限 制，而使t a b u 搜索法难以接近最优解的近旁，这又从另一个方面影响算法的全局 搜索性能。所以在实际应用中，需要对列表进行调整。 ( 4 ) 神经网络方法 基于神经网络的问题求解技术是一种无启发的白适应随机搜索方法，它利用 神经元的巨量并行和神经元的动力学演变来快速解优化问题。用神经网络求解优 化问题是1 9 8 5 年由h o 西e l d 教授提出的【2 3 1 ，自1 9 8 5 年h o p f i e l d 教授开创这一目题求 解技术以来，己取得了引人注目的成就，s g 等人【2 4 】使用基于神经网络和启发 式搜索的混和方法来求解j o b s h o p 调度问题；d o n g - 等( 1 9 9 6 ) 【2 5 j 把神经网络用于间 歇过程控制最优化，取得了满意的结果。 应用神经网络求解优化问题时，须把优化问题映射到神经网络上，为此必须： 武汉理工大学硕士学位论文 1 ) 选择一种问题表达方式，使神经网络的输出与问题的解彼此对应； 2 ) 构造一种能量函数，使其最小值对应于问题的最优解； 3 ) 由能量函数推导出网络参数： 4 ) 构造出求解问题的神经网络。 在问题求解时，关键是构造能量函数，能量函数是一种全局量，它反映出系 统的动力学演变过程。在实现神经网络计算的过程中，系统内计算能量函数在网 络运行过程中沿着问题的状态空间中的一条非平衡轨迹单调递减，每个非平衡轨 迹最终趋向于它的平衡状态，达到平衡状态时能量最小，神经网络系统稳定下来， 此时得到问题的解。 神经网络对优化问题的求解过程是一个自适应和学习过程，类似于人脑的特 性，这是区别于一般的优化搜索算法的本质所在，也是人们对此感兴趣的原因。 神经网络优化方法的不足之处在于收敛效果不太好，较难得到全局最优解。目前 已有一些改进的方法，它们从不同的角度比现有的方法有所深入和创新。 ( 5 ) 进化算法 进化算法( e v o l u t i o n a l g o r i t h m ，e a ) 倒是一类模拟生物进化过程的随机搜索算 法。耳前研究的进化算法主要有三种：遗传算法( g e n e t i ca l g o r i t h m ，g a ) ，进化 规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 和进化策略( e v o l u t i o n a r ys t r a t e g i e s ，e s ) 。尽 管它们很相似，但在历史上是独立发展起来的，遗传算法是1 9 7 5 年由h o l l a n d 创 立【翊，后由d ej o n g 和g o l d b e r g 等人进行了改进f 2 帕9 】。进化规划最早由l f o g e l 等人提出【3 0 1 ，后由d b f o g e l 进行了完善【3 1 】；进化策略是r e c h e n b e r g 和s c h w e f e l 建立的1 3 2 1 。群体搜索策略和优化计算时不依赖于梯度信息的特性使得进化算法 的应用范围比较广泛，适合于处理传统搜索方法难以解决的高度非线性问题。在 生产调度领域的典型研究和应用有：秦宏启，袁一等人用遗传算法解决多产品连 续化工生产过程的调度优化问题【3 3 1 ；双兵和顾辛生用遗传算法求解有交货期限制 的连续生产过程生产调度问题【3 4 l ；b i e r w i r t h 和m a t t f e m 提出一种遗传遗传算法 用于解决描述静态、动态和非确定生产环境的一般作业车间调度问题j ，等等。 进化算法的不足之处在于：难于保证群体的多样性和不能有效地均衡局部搜索与 全局搜索，致使在搜索过程中常常陷入局部最优解，并且收敛太慢。 ( 6 ) 列队竞争算法 现代优化算法有很多，包括前面提到的数学规划、神经网络、模拟退火和遗 传算法、等算法。这些算法对于复杂多变量问题的求解，或其解的质量不高，或 计算效率较低，存在一定的局限。针对上述优化技术的局限与不足，鄢烈祥教授 提出了列队竞争算法( l i n e u pc o m p e t i t i o na l g o r i t h m l c a ) 3 6 1 ，该算法是一种进化算 法，它在求解非线性规划问题和组合爆炸问题方面表现出了优良的特性，特别是 6 武汉理工大学硕士学位论文 对规模越大越难求解的全局优化问题，越能表现出该算法的稳健性和搜索效率。 该算法已成功应用于求解旅行商问题 3 7 1 、布局分布问题【3 8 l 等经典的组合优化问 题；在化工过程系统方面，成功应用于求解大规模管路网络综合【3 9 l 、换热网络综 合【帅】，多产品间歇生产过程调度优化【4 1 】等问题，取得了较好的效果。 列队竞争算法是一种群体并行搜索、多层次竞争的全局优化搜索算法，搜索 过程与进化算法的基本机制相似，也有繁殖、变异和选择等操作算子，主要的区 别在于：列队竞争算法在进化过程中始终保持m 个独立并行进化的家族，每个家 族仅有一个个体，通过无性繁殖产生后代。此外，在竞争机制上与进化算法完全 不同。列队竞争算法中有两个竞争水平，一个是纵向竞争，即指同一家族内繁殖 的子代为生存进行的竞争；另一个是横向竞争，指不同家族之间的列队地位竞争。 通过两个水平的竞争，使列队中的首位个体不断地被其他家族个体所取代或其值 被更新，快速地向最优点逼近。 由于列队竞争算法优秀的全局优化搜索特性，本论文拟用此算法来求化工生 产过程的调度优化问题。 1 4 本文的工作 本文运用列队竞争算法这一全局优化搜索新算法求解化工生产过程调度优化 问题，主要做了以下几个方面的工作： 第二章研究了顺序型多目的化工厂的生产调度问题，针对以总生产完成时间 最短为目标函数的调度优化模型，提出了一种启发式的“离散- 回缩”策略来计算 一定生产排序下的总生产完成时间，应用列队竞争算法优化产品加工顺序，并对 文献中的典型实例进行了求解分析。 第三章分析了锅炉蒸汽系统循环调度问题的基本特点，提出了时间分段的问 题分解策略，并在此基础上建立了该循环调度问题的混合整数非线性模型，应用 列队竞争算法对该问题进行求解分析，结合某个生产过程锅炉蒸汽系统循环调度 实例进行了研究。 第四章研究了发酵过程中空气供应量受限的一种资源受限调度问题，建立了 以资源限制为约束条件，以总生产完成时间最短为目标函数的优化调度数学模型， 采用列队竞争算法优化生产排序结果，并对某生物农药厂的调度实例进行了计算 分析。 第五章以m a t l a b 作为软件开发平台，以某生物农药厂的发酵生产为背景，开 发出基于m a t l a bw e bs e r v e r 的生产调度优化远程决策支持系统。 第六章是本文的总结和展望，主要回顾了本文的工作，并提出下一步需要进 行的研究工作。 7 武汉理工大学硕士学位论文 第2 章列队竞争算法求解顺序型多目的厂 生产调度问题 2 1 引言 由于科技发展的日新月异和市场竞争的日趋激烈，进入新世纪后化学工业出 现了一些新的要求：( 1 ) 产品的个性化强，以满足客户的特定需求；( 2 ) 生产产品的 投资少、见效快，以快速满足不断变化的市场需求；( 3 ) 生产是柔性生产，便于多 产品、多牌号生产，以应对新产品被快速更新的局面。鉴于间歇生产过程能满足 上述要求，特别适应批量小、产值高、品种多、变化易、上市快的生产，所以间 歇生产方式将成为新世纪化工过程的主要生产形式之一。 间歇化工厂的一个最突出的特点是它的灵活性，即通过对处理设备、原材料 等资源的共享，在同一组设备上生产多种产品，并且可以实现较为复杂的合成过 程。由于有多种产品要共享时间和有限资源( 如原材料、处理设备、公用工程) ，而 调度的主要任务就是在时间和空间上合理利用系统的有限资源，以满足性能指标 的要求，因此间歇化工厂在生产和经济上优势的实现很大程度上依赖于生产调度， 从而确定产品在各个设备上被加工的次序，并合理地分配这些公用资源，以优化 某些经济的或系统的性能指标，使生产约束得到满足的同时生产代价最小。 生产调度问题是化工间歇生产过程优化的主要技术难题之一，对间歇化工厂 生产调度问题的研究已成当前研究的热点。在市场经济的激烈竞争下，间歇化工 厂生产模式为企业快速应对变化的市场提供了选择，为此开展对间歇化工厂生产 调度问题的研究，无疑具有相当的社会及经济意义。 本章内容主要分析了间歇化工生产的特点，以零等待的顺序型多目的化工厂 为研究对象，建立了间歇过程的优化调度模型，采用列队竞争算法对该优化问题 进行优化求解。 2 2 间歇化工过程生产调度 2 。2 1 间歇化工过程调度问题分类 间歇化工过程可以分成两类：多产品( m u l f i p r o d u c t ) 间歇过程和多目的 ( m u l t i p u r p o s e ) n 歇过程。多产品间歇过程是指所有产品都遵循同样加工路径的生 产过程，图2 1 所示是一种典型的经过两个生产步骤的多产品间歇过程。多目的间 歇过程一般是指不同的产品具有不同的加工路径，图2 2 所示是一种典型的多目的 间歇过程。在加工过程中，存在资源限制、时间和空间限制，必须实施调度以达 到总体最优的生产目标。 8 武汉理工大学硕士学位论文 图2 1 多产品间歇过程 困一匝互卜伍互卜 蔓日一囤 匮习尊丑 哥 9 圈 ： ： ： -i i l 原料m _ _ 叫设备nh 设备i 卜_ 一设备ji + l 产品mi r _ 。j _ _ _ _ 1r r 4 _ 1p 。_ _ _ 。l _ _ 。1r 。- 。1 图2 - 2 多目的间歇过程 到目前为止，多目的间歇化工过程的调度研究远没有多产品厂深入，这是因 为多目的厂能够方便灵活地按照时常要求生产多种产品，而且能够在同一套设备 上选择不同的路线生产同一产品，因而使得生产安排变得异常复杂。典型的多目 的厂又分为：顺序型多目的厂和非顺序型多目的厂。化工、食品、医药和涂料等 行业较多采用的是顺序型多目的厂这一间歇生产模式，即不同产品不同批次的物 料沿相同的方向在设备上流动，实质上，上述多产品厂就是顺序型多目的厂的一 种特殊形式。因而顺序型多目的厂的生产调度研究具有很重要的理论价值和实际 意义。 2 2 3 优化模型建立 2 2 3 ，1 问题描述 顺序型多目的厂间歇过程调度问题可定义如下：在一定时间范围内，加工若 干批次的不同产品，每种产品的加工路线方向是一致的，并且己知各个产品在各 台设备上的加工时间。作为一般化的顺序型多目的厂调度模型，每种产品生产的 批次可以不同，而且不同产品经过的设备数目也可以不同。要求在一个给定的目 标函数下对模型进行求解，使得目标值最优【1 3 】。图2 3 是顺序型多目的过程工厂 的生产过程示意图。 9 r 斗 甲罾 武汉理工大学硕士学位论文 图2 - 3 顺序型多目的厂生产过程 上述的定义可以转换为数学模型的已知条件：( 1 ) 在一个生产周期内生产产品 的种类和批次；( 2 ) 每种产品对应的加工设备次序和所需的加工时间，当某产品在 其中一台设备上的加工时间为0 时，表示该产品不需经过此设备的加工；o ) 一个 合适的目标函数，即总的生产完成时问最短。 模型需要求解出每个产品在各个设备的开始加工时间和完成时间，使得目标 函数值最小。为了减少模型的复杂程度，做出如下简化：整个生产过程中的物料 保持恒定，没有物料的损失；设备的准备时间和物料转移时间相对于产品加工时 间很小，可以忽略不计；设备之间不存在任何关联和干扰；同一台设备不能同时 处理两个或多个产品；生产过程中不存在资源限制条件的约束。 2 - 2 3 2 调度数学模型 顺序型多目的间歇过程按照中间储罐的设置方式可以分为：( 1 ) 无限中间存储 ( u n l i m i t e di n t e r m e d i a t es t o r a g eu i s ) ：( 2 ) 有限中间存储( 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 ) ；( 3 ) 无中间存储f n oi n t e r m e d i a t es t o r a g e ，n i s ) ；( 4 ) 零等待( z e r ow a i tz w ) ：( 5 ) 有限等待( f i n i t ew a i tf v 0 。其中u i s 和f i s 模式表示加工设备之间的存储设备数 目分别为无限大和有限的，而n i s ，z w 和f w 模式的加工设备之间都没有存储 设备。n i s 模式指的是中间产品在某个设备上加工完后可以在该设备中滞留任意 长的时间，z w 模式的中间产品必须立刻传送到后继加工设备中，f w 模式的中 间产品可以在加工设备中暂存一定的时间。在实际生产过程中也可能是几种存储 策略的组合。z w 方式是实际生产过程中较多采用的存储方式，以下以z w 的顺 序型多目的厂间歇过程为例，对其生产过程排序问题进行研究。 考虑有个产品，膨台设备单元的生产过程，规定产品上( ，= 1 , 2 ，n ) 的第一 道加工工序的开始时间为c ，0 ) ；产品五在第k 台设备上的加工时间为t ( z ，k ) ( i = 1 , 2 ，n ；k = 1 , 2 ，m ) ；产品正离开第k 台设备的时间记为c ( 工，k ) ：产品的加 工序列为，= | ( j i ，约+ t ( jp ，n = - l ，2 3 ，n ；= l ，2 3 ，mi bk = - l ，2 ，m ( 2 - 2 ) 至此，零等待( z w ) 的顺序型多目的厂生产调度问题的数学模型可表达为： r a i n l m n a “xl m “a s x c ( j f ，七) ( 2 3 ) s t c ( l ，k + 1 ) = c ( 五，七) + f u 。，k + 1 )f = 1 , 2 ，n ；k = 0 ，1 ，2 ， ，一1 a b s ( c ( _ ，；，_ j ) 一c ( j ，k ) ) + a b s ( c ( ，k 一1 ) - c ( j p ，k - 1 ) ) ，( 工，女) + r ( _ ，p ，_ i ) 卢l ，2 3 ，；，= 1 ，2 3 ，n ，f b k 2 1 ，2 ，m 为了满足上述( 2 2 ) 式的约束，本文提出了一种启发式的“离散一回缩”的策略， 即在g a n t t 图上将个产品在第一台设备上的开始加工时间彼此离散“很远”的距 离，以使不会出现设备任务的重叠现象。然后，按照加工序列从第2 个产品开始， 依次将产品- ，的所有加工时间向回收缩到极限距离，即刚好不发生设备任务重叠 为止，图2 4 表示了“回缩”的过程。这种启发式“离散回缩”策略，能有效地避免设 备任务冲突，满足( 2 2 ) 式的约束，简化总生产完成时间的计算。 图2 4 甘特曲线平移示意图 若给定产品加工序列- ，= ，：， ) ，应用上述策略即可以计算最短生产完 成时间c 。，产品加工的优化排序可由列队竞争算法来完成。 武汉理工大学硕士学位论文 2 3 列队竞争算法求解 列队竞争算法是一类随机算法，同遗传算法( g a ) 、进化策略( e s ) 和进化规划 ( e p ) 一样，它属于一种模拟生物进化过程的进化算法，但是与后者不同之处在于 列队竞争算法在模拟进化过程中采用无性繁殖，即始终保持家族独立并行进化。 同时，在该算法中通过家族内部的生存竞争和家族间的地位竞争这两种竞争方式， 使群体快速进化到最优或接近最优的区域。家族内的生存竞争是指各家族中仅性 状( 与目标函数值有关) 最好的家族成员得以生存并作为该家族的变异的母体，家族 间的地位竞争是根据各家族变异母体的性状从好到坏来排定位次，不同地位的家 族具有不同的竞争推动力。竞争推动力可以理解为家族变异能力的大小，处于第 一位的最优秀的个体只进行一次变异，所迁移的范围较小，有利于加速局部搜索； 列队中处于越靠后的个体，变异次数逐渐增加，个体在搜索空间的迁移范围逐渐 增大，起到了全局搜索的作用。这两种竞争方式起到均衡局部的精细搜索与全局 的粗略搜索的作用，能确保得到最优解或者满意解。对于组合优化问题，竞争推 动力的大小可用个体的变异次数或个体在搜索空间中的迁移步长来表示。 2 3 1 算法描述 在给出算法描述之前，先做出如下定义： 定义2 1 设f 是问题空间的可行域，给定一个点f f ，把某种意义上靠近于 f 的点之集合称为邻域，用n ( f ) 表示。 定义2 2 在点f 上的个体作一次变异所迁移的空间称为变异邻域。 定义2 3 把能