基于加工时间不确定的间歇化工过程随机调度研究.doc

《基于加工时间不确定的间歇化工过程随机调度研究.doc》由会员分享，可在线阅读，更多相关《基于加工时间不确定的间歇化工过程随机调度研究.doc（9页珍藏版）》请在三一办公上搜索。

1、精品论文基于加工时间不确定的间歇化工过程随机调度研究孔令启 1，2，华贲 1，李玉刚 2，韩方煜 2，郑世清 21 华南理工大学化工与能源学院，广州(510640)2 青岛科技大学计算机与化工研究所，青岛(266042）E-mail：konglingqi摘要：间歇化工过程随机调度的建模和求解十分复杂，本文将确定性调度和概率统计理论相结合提出了一种新的间歇化工过程随机调度的模型和评价体系，将随机变量清晰化降低了问题求解的复杂程度；并 以加工时间不确定的 ZW 间歇化工过程随机调度为例，研究了最优调度的完工期限与实现概率间的关系， 以及最优调度完工时间的分布规律,证明了模型和方法的有效性。 关键词

2、：间歇化工过程；随机调度；不确定性；随机规划中图分类号：TQ021.81引言随着现代化学工业的发展，化工间歇过程的重要性日益突出，特别适合于规模小、附加 值高、上市快、生产灵活的功能型产品的生产，已广泛应用于精细化学品、生物制品食品、 制药、微电子材料等领域。调度问题是实际化工间歇过程中的关键环节，是连接生产经营管 理和过程控制的纽带，在过去的十几年受到学术界和工业界的广泛关注1,2。现有文献3-8中 大多假定系统的所有数据都是确定不变的，但事实上由于化工间歇过程本身的复杂多变和市 场的灵活性，实际过程中产品的加工时间、市场需求和设备可用等不确定因素将不可避免的 出现，这些因素将导致原生产调度

3、在实际过程中表现为低效甚至不可用。因此对这种“突发 事件”做出即时调整和周期性最优化原有调度在间歇过程中显得极为关键9，近年来得到了 足够的重视10-17。对于处理这种“突发事件”的办法有两种：反应型调度（Reactive scheduling）和随机型 调度（Stochastic scheduling）。反应型调度和随机型调度最大的不同就是：前者重在针对具 体的不确定因素采用相应的解决办法对原调度进行修复或补充，要求在不确定因素到来的第 一时间内产生出最新的调度，不需要对全部的调度进行重新设立，是一种对调度干扰到来的 补救和治疗措施；而后者重在预防，即在调度的初始设计阶段就将不确定因素考虑进

4、去，对 于不确定因素对调度影响的程度和规律、调度实现的可能性进行评估，这样当不确定因素到 来的时候就不会影响调度的健康执行，所以两种调度处理方法的代价和后果是不同的，对于 简单的间歇化工过程调度，当不确定因素到来时采用反应型调度尚可补救，而对于大规模的 复杂调度过程，有些不确定因素对调度的影响可能是毁灭性的，采用随机型调度处理方法应 该更经济和可行。当然采用随机型调度需要在设计之初就将不确定因素考虑进去，因此增加 了问题的复杂程度和求解难度。由于实际间歇生产过程中每批生产很难完全重复，且人力、设备、操作等因素均会导致 生产中操作时间的波动18，因此在随机型调度研究中，产品加工时间作为一种常见的

5、不确 定因素而得到了广泛的研究19-24。这些研究的问题模型因含有数目众多的约束方程和整数变 量，对于大规模实际问题的表达和求解非常困难。2模型的数学表达2.1 不确定性调度的基本模型不确定性调度模型是在确定性调度模型中加入了不确定性的因素，其一般形式如下：9max p(d , z, x,q ) d , z, x s.t. h(d , z, x,q ) = 0 g (d , z, x,q ) 0（1）x X , z Z , d D ，其中： d 和 z 分别表示决策变量和控制变量， x 表示状态变量，q 为 不确定性参数，h 、 g 为等式和不等式约束方程。由于不确定因素的存在，使目标函数和约

6、 束评价因增加一类随机变量而变得困难，使问题的求解更加复杂。本来可以用标准数学规划 方法求解的调度问题转化成需要特殊技术的随机问题。在实际过程中，研究方法主要有两种， 一是采用适当方法将随机模型转化为模型的确 定性等价类（Deterministic Equivalent），此方法巧妙的绕开了离散化和随机取样的要求，避 免了问题规模的不必要的扩大，但对于象调度这类具有多个随机因素存在的复杂问题很难实 施。另一种是用确定性模型来近似随机模型(如对随机因素直接取期望)，然后按确定性模型 的算法决定循环生产策略或者直接采用启发式算法动态地决定下一时段的生产批量，这种算 法虽简单，但由于忽略随机因素对调

7、度的影响而在实际应用中意义不大。假设t 维随机向量e 的概率密度函数为 F(e ) ，则随机向量e 的期望值定义为：Ee = eF(e )d et单目标期望值模型的一般形式可以表示如下：max E f ( x, e )s.t. jE g ( x,e ) 0, j = 1, 2,L, p（2）Ehk ( x, e ) = 0, k = 1, 2,L, q（3）其中 x 是一个 n 维决策向量，e 是一个 t 维随机向量，其概率密度函数为 F(e ) ， f ( x,e ) 是目标函数， g ( x,e ) 和 h ( x,e ) 是随机约束函数，表示期望值算子，从而有jkEE f ( x,e )

8、 = f ( x, e )F(e )detE g j ( x, e ) = g j ( x, e )F(e )det, j = 1, 2,L, pEhk ( x, e ) = hk ( x, e )F(e )det, k = 1, 2,L, q（4）（5）（6）若 e 是一个离散性随机变量且分布函数为 Pr (e = e i ) = fi ， i I其中 I 序号集，则有（7）E f ( x,e ) = ￥fi f ( x, ei )iI E g j ( x, e ) = ￥fi g j ( x,ei ), j = 1, 2,L, piI Ehk ( x, e ) = ￥fi hk ( x,

9、ei ), k = 1, 2,L, qiI （8）（9）（10）因 此 ，一 个 解 x 可 行 当且 仅 当 E g ( x, e ) 0, j = 1, 2,L, p 和 Eh ( x,e ) = 0 同 时 满 足 ，jkk = 1, 2,L, q 。一个可行解 x * 是期望值模型（3 ）的最优解，如果对于任意的可行解 x ，E f ( x* ,e ) E f ( x, e ) 成立。2.2 数学模型的转化简单的间歇化工过程的确定性调度模型可用的混合整数线性规划（MILP）表示，对于 随机调度问题，还需要考虑随机参数的分布，这样使上述模型很难求解；本文将概率统计理 论和确定性调度模型相

10、结合，用离散的确定性调度的统计属性来描述随机调度的规律性。1不确定性因素的描述间歇过程随机调度和确定性调度的不同之处就在于调度设计上考虑了不确定参数的随 机性，本文研究间歇操作加工时间的不确定性，在很多情况下，用随机变量描述间歇加工时 间的不确定性是一种有效地方法。根据过程操作特点一般可把描述加工时间不确定的随机变 量分成以下三类。（1） 加工时间服从概率分布。根据对实际生产的历史数据的分析， 统计出加工时间 所服从的概率分布，应用服从某种概率分布的随机变量来表示随机加工时间，常用的概率分 布有均匀分布、正态分布和指数分布。（2） 加工时间处于某一区间。在生产实际中， 要依据历史的操作数据分析

11、、归纳出 加工时间满足何种概率分布， 有时是困难的。最简便的方法就是统计、整理出加工时间位于某个区间内。不确定的随机变量表示为: qi qi min,qi max ，其中qi min ，q max 为参数q 可ii能取值的下限和上限，这两个量可以通过对历史操作数据的分析整理获得。（3）加工时间为离散的值。这类不确定性主要是设备的故障，仪器、仪表的失效或误 操作等引起，或者是关键操作人员的短缺等。在数学描述上可以用一些离散的量来表示随机 加工时间。本文主要是讨论第一种情况，并以零等待（Zero-Wait，ZW）存储方式的间歇多产品厂为例来研究加工时间服从概率分布的情况，其它两种情况也可采用类似方

12、法解决。2不确定因素的清晰化如何从服从某种概率分布的变量中取得 n 个独立的量呢?实际上这是一个随机变量的清 晰化问题，即将符合某种分布的随机变量用符合相应分布的多个常量代替，对于一维变量一 般的数学软件都有常规的分布函数，本文基于一维随机变量的离散化，对多维随机变量进行 清晰化处理，所产生的集合称为清晰化集。因每个工序的加工时间都为一个随机变量，对于有多个加工工序的间歇化工过程的加工 时间可用多维随机变量来表示，多维随机变量的清晰化可基于一维随机变量的产生的方法。 按照下列步骤进行。（1）一维随机变量的清晰化：根据加工时间分布的规律，分别对各个加工工序的加工 时间进行清晰化，产生各个加工工序

13、的加工时间清晰化集合。（2）样本的产生：从各个清晰化集合中随机取出一个元素，作为样本的各个工序的加 工时间，这样就得到了各工序加工时间表的一个样本。（3）集合的产生：按照（2）的方法取点，直到所产生的样本数满足设计要求。按照上 述取点方法获得的两维取点图(X 为 9.7 hr10.2 hr 均匀分布，Y 为 13.7 hr 14.3 hr 均匀分布， 样本个数为 100)见图 1，三维取点图(X 为 9.7 hr 10.2 hr 均匀分布，Y 为 13.7 hr 14.3 hr 均 匀分布，Z 为 13.9 hr 15.1 hr 均匀分布，样本个数为 100)见图 2。14.314.2Y /h

14、r14.115.515Z /hr14.51413.913.813.79.79.89.910.010.110.2X /hr1413.514.514Y /hr13.59.7 9.89.9 10X /hr10.110.2图 1 两个随机加工时间点分布图Fig.1 Distribution of two random process times3约束条件图 2 三个随机加工时间点分布图Fig.2 Distribution of three random process times在 ZW 存储方式的间歇多产品厂调度研究中作如下假定：（1）所有产品在每个加工单元上的操作次序相同，即为排列排序；（2）产品

15、之间没有优先性；（3）一个设备不能同时处理多种产品，一种产品不能同时被多个产品处理；（4）对最终产品有足够的存储容量；（5）中间产品存储为 ZW 方式，即产品完工后马上进入下一道工序。并将变量定义如下：C i , j ：i 产品 j 工序的完工时刻，其中 C i ,0 为第 i 个产品开始加工的时刻。X i , j tX i , j ：i 产品 j 工序的加工时间， t W ， W为随机变量的清晰化集合。X ：产品加工顺序向量，确定性调度的产品加工顺序作为优化变量一般由随机性算法来优化产生4,5,16。 Xi ：产品的加工顺序中第 i 个被加工的产品代号。对于已知加工顺序的 N 个产品、M 个

16、设备单元的 ZW 多产品厂的调度的时间表问题须满足以下约束：(1) 加工时间匹配约束C i , j= C i , j - 1 + t X i , j( i = 1, 2 , L , N ; j =2 , 3 , L , M )(11)表示对于 ZW 方式，第 i 个被加工产品 j 工序的完工时间等于该产品 j-1 工序完工时间加上该任务所需要的加工时间。（2）设备空闲约束C i , j C i - 1 , j + t X i , j( i =2, 3 , L , N ; j =2 , 3 , L , M )(12)表示第 i 个被加工产品 j 工序的必须在 i-1 产品的 j 工序完工之后才能

17、进行。（3）边界条件约束C 1 ,1 = t X 1 ,1( i = j = 1） (13)表示第 1 个被加工产品首工序完工时间为 t X 1 ,1 。这里和确定性调度不同的是各工序的加工时间 t X 1 ,1 是个多维随机变量清晰化的集合，是离散的随机数。4目标函数对确定性调度问题的评价最常用的指标是最终完工时间，但对于加工时间不确定的随机1调度来说，同一个调度对不同的样本数据的完工时间结果不同，所以用随机调度完工时间的数学期望来描述； 随机调度完工时间的数学期望（最小）：F ob j 1 m i n ( E C N , M =￥ C N ,M )n(14)而对于确定性调度规定的期限内能否

18、完成的调度的评价，在随机调度必须以调度完成的概率来描述。随机调度的完成的概率（最大）：F ob j 2 m a x ( f f = P r C N ,M T ) (15)这里 T 表示希望调度的完工期限， f 为调度在规定期限 T 内实现的概率。3计算实例一个有 4 单元 6 产品(P1P6)的多产品间歇过程，采用 ZW 存储方式加工，相应的操作时间如表 1 所示，操作时间在一定范围内服从均匀分布。Unit 1Unit 2Unit 3Unit 49.7-10.213.7-14.313.9-15.110.0-10.613.1-14.211.6-12.812.0-12.314.2-14.319.0

19、-21.010.4-10.813.1-13.711.7-12.910.5-11.014.6-14.711.2-12.212.0-12.112.4-13.311.9-12.912.3-13.412.6-13.311.5-12.513.9-14.211.4-12.312.9-13.4表 1 产品在各设备单元上的操作时间 (hr) Table 1 Processing times on each unit of products (hr)UnitsProductsP1P2P3P4P5P63.1 确定性调度的计算首先采用文献5提供的确定性模型，以最短完工时间为目标函数，计算最悲观（均匀分 布的最大值）

20、时间条件下最优调度的产品加工顺序为1 3 4 2 5 6，最短总完工时间为 123.20 hr，计算最乐观（均匀分布的最小值）时间条件下最优调度的产品加工顺序为1 6 5 2 4 3， 最短总完工时间为 116.80 hr，最优调度的 Gantt 图见图 3 和图 4，因此无论在何种情况下 最优调度的完工时间必然在 116.8123.2 hr 之间。图 3 最悲观条件下的最优调度 Gantt 图Fig.3 Gantt chart of optimal scheduling on pessimistic time3.2 随机调度的计算1最优调度完工时间的数学期望图 4 最乐观条件下的最优调度 G

21、antt 图Fig.4 Gantt chart of optimal scheduling on optimistic time以随机调度完工时间数学期望最小为目标，计算最优调度完工时间期望值为 120.27 hr， 最优调度产品加工顺序为1 3 4 2 5 6，和悲观时间条件下确定性最优调度相同。2最优调度的分析以随机调度在期限 T 约束条件下所实现的概率为优化目标，计算在不同期限 T 约束下的最优调度和对应的概率，经过计算所得到的结果如表 2 所示。计算在不同期限 T 约束下实现概率最大的调度皆为1 3 4 2 5 6，将表 2 中的数据结 合最悲观和最乐观条件的最优调度完工时间对调度完成

22、的概率作图如图 5，将最优调度的完 工时间的分布按照 T 的范围作图如图 6 所示。表 2 在不同期限 T 下最优调度的概率Table 2 Probability of the optimal scheduling with different time limit TT (hr)ProbabilityT (hr)Probability1198%120.561%119.518%120.768%119.728%120.872%12037%120.980%120.143%12183%120.245%121.596%120.2751%121.798%120.354%122100%100%Probab

23、ility 80%60%40%20%0%50%40%30%20%10%0%8%10%19%probability24%22%13%4%116118120122124T /hr116.8-119.0119.0-119.5119.5-120.0120.0-120.5120.5-121.0121.0-121.5121.5-123.2图 5 最优调度在不同期限下的完工概率Fig.5 Probability of the optimal scheduling in different time limit TT /hr图 6 最优调度完成时间的频率分布Fig.6 Distribution of make

24、span of optimal scheduling由图 5、图 6 可得如下结论：1 最优调度的完工期限越大（即期限越宽裕），最优调度在该期限内实现的概率也越大， 反之亦然。完工期限松弛到一定的程度（即最乐观加工时间条件下最优调度完工时间 123.20 hr）最优调度实现概率为 100%，将总完工时间约束紧张到一定的程度（即最悲观加工时间 的最短总完工时间 116.80 hr），最优调度实现概率为 0实现。充分体现了实现目标和实现 可能之间的关系，调度设计者可根据这种关系设定合理的调度目标，不至于使调度的实际操 作过程中太保守或太冒进。2 由图 6 可知，虽然加工时间服从均匀分布，但最优调度

25、的总完工时间的分布却大多 集中在最优调度的完工时间期望值（120.27 hr）附近；采用最乐观和最悲观条件下的调度 完工时间对调度进行设计是不可行的，前者太冒进，当外界干扰时会使调度变的不可行，后 者太保守从而降低了调度本身的意义和效率。相比于其它时间段，最优调度的完工时刻落在119.5 hr121.5 hr 之间的可能性达到 78，采用最优调度的期望值作为完工期限即保证了目标本身、又保证了其实现的可行性。4结论（1）将随机规划理论和概率统计理论相结合，建立了基于随机加工时间的间歇过程不 确定调度问题的模型和评价体系。（2）将随机变量清晰化，将随机调度问题转化为确定性调度的概率统计问题，从而降

26、低了求解问题的复杂程度。（3）以零等待（Zero-wait， ZW）存储方式的多产品间歇过程为例研究了在加工时间 不确定条件下的最优调度、最优调度的实现概率和最优调度完工时间的分布等规律，证明了 本论文提出的模型和方法可为间歇化工过程不确定调度提供技术指导。符号说明C i , j i 产品 j 工序的完工时刻，hrM设备数 N产品数 样本数 T随机调度的期限，hrtX i , j i 产品 j 工序的加工时间，hrXi 产品的加工顺序中第 i 个被加工的产品代号X 产品加工顺序向量f 调度实现的概率W 调度随机变量的清晰化集合。下角标产品序号设备序号参考文献1 杨志才, 化工生产中的间歇过程,

27、 北京化学工业出版社,2001.2 李慧芳 李人厚 陈浩勋,化工批处理过程调度综述, 信息与控制,1999,28(2) : 127-135.3 陈昌领 冯晓东 邵惠鹤, 单生产线序贯多目的批处理过程短期调度的 MILP 建模, 系统仿真学报,2001,13suppl: 69-71.4 孔令启 岳金彩 李玉刚等, 列队竞争算法求解多产品间歇生产过程排序问题, 计算机与应用化学,2006,23(7) : 915-9185 孔令启 李玉刚 岳金彩等, 基于遗传禁忌算法的多目的间歇过程调度问题求解, 计算机与应用化学,2006,23(12) : 1341-1345.6 周国华,遗传算法及其在生产调度中

28、的应用,西南交通大学学报(自然科学版),2000,1(2):36-397 王举 袁希钢 陈中州,用于多产品间歇化工过程排序的模拟退火算法,化工学报 2000,51(6) : 751-756. 8 刘斐,间歇过程的最优调度策略及应用,洛阳化工学院学报,1998,19(2): 76-80.9 Carlos A. Mendez, Jaime Cerda.Dynamic scheduling in multiproduct batch plants. Computers and ChemicalEngineering 2003, 27: 12471259.10 Shah, N., & Pantelid

29、es, C. C., Design of multipurpose batch plants with uncertain production requirements.Industrial and EngineeringChemistry Research, 1992, 31, 13251337.11 Subrahmanyam, S., Pekny, J. F., & Reklaitis, G. V., Design of batch chemical plants under market uncertainty.Industrial and Engineering Chemistry

30、Research, 1994, 33, 26882701.12 Ierapetritou, M. G., & Pistikopoulos, E. N., Batch plant design and operations under uncertainty. Industrial and Engineering Chemistry Research, 1996, 35, 772787.13 Harding, S. T., & Floudas, C. A. Global optimization in multiproduct and multipurpose batch design unde

31、r uncertainty. Industrial and Engineering Chemistry Research, 1997, 36, 16441664.14 Petkov, S. B., & Maranas, C. D. Multiperiod planning and scheduling of multiproduct batch plants under demand uncertainty. Industrial and Engineering Chemistry Research, 1997, 36, 48644881.15 顾幸生,不确定性条件下的生产调度,华东理工大学学

32、报,2000,26(5): 441-446.16 Li Fan-hua, Kong Ling-qi, Li Yu-gang, et al. The study of on-line modification for multiproduct batch processes scheduling in case of orders changing. Computers and Applied Chemistry, 2005, 22, 11831186.17 李 玉刚 国纲 孔令启 等 , 基 于 设备 故障 的间 歇 化工 过程 反 应 型 调度 , 计 算 机与 应用 化学,2008,25(

33、4),459-463.18 Cott B. J. ,Macchiettot S. Minimizing the Effects of Batch Process,Variability Using Online ScheduleModification, Computers and Chemical Engineering, 1989,13 :105-113.19 曹德铭 袁希钢,操作时间不确定的间歇过程最优化设计,化工学报, 2002,53(1), 72-77.20 Peng J, Liu B D. Parallel machine scheduling models with fuzzy

34、processing times. Information Science, 2004,164(1):1-1821 Wang C Y, Wang D W, Ip W H, et al. The single machine ready time scheduling problem with fuzzy processing times. Fuzzy Sets and Systems, 2002, 127(2):117-12922 Balasubramanian J., Grossmann I. E., A novel branch and bound algorithm for schedu

35、ling flowshop plants with uncertain processing times, Computers and Chemical Engineering, 2002, 26:41-57.23 Lin F T.A job-shop scheduling problem with fuzzy processing times A.Proceedings of InternationalConference on Computational Science Part II C.Berlin Heidelberg:Springer,2001,409-41824 Kouvelis

36、, P.; Daniels, R. L.; Vairaktarakis, G. Robust scheduling of a two machine flow shop with uncertain processing times. IEE Trans. 2000, 32, 421-432A new formation and solution for batch process stochastic scheduling with uncertain processing timeKONG Ling-qi1，2, Hua Ben1, LI Yu-gang2, HAN Fang-yu2, Z

37、HENG Shi-Qing21 School of Chemical and Energy Engineering, South China University of Technology, Guangzhou, PRC,(510640)2 Research Center of Computer and Chemical Engineering, Qingdao University of Science andTechnology, Qingdao, PRC,(266042)AbstractScheduling for chemical batch process has been an

38、active area of research over the past decade. Theuncertainties of the process, which expand the scope and complexity, make the formulation and solution of the stochastic scheduling very intractable. This paper proposed a novel mathematical formulation which linked the theory of probability and stati

39、stics with the deterministic scheduling, the discretion of the stochastic variables can be used to alleviate this difficulty and complexity. An exampled of batch process stochastic scheduling with uncertain processing time was showed the relationship between the deadline and the probability of optimal scheduling, and the distribution of the makespan of the optimal scheduling was studied. Result indicated the method is effective and reasonable.Keywords：batch chemical processes；stochastic scheduling；Uncertainty；Stochastic programming；作者简介：孔令启，男，1973 年生，博士研究生，高级工程师，主要从事化工过程系统工 程、工艺过程模拟和优化方面的研究。