多产品间歇过程调度问题的建模与优化
第3O卷
正
第l7期
脑 17
计 算 机 工 程
Com puter Engineering
2004年9月
Septem ber 2004
· 基金项目论文 · 文章编号：1000--3428(2004)1 7----0056----03 文献标识码：A 中圈分类号l TP39
多产品间歇过程调度问题的建模与优化
曹瑞金，俞欢军，胡上序
(浙江大 学 化工系 ，杭州 3 l0027)
摘 要 ：提 出了一种基于有色赋时PeIri网 (CTI，N)的多产品间歇过程调度问题的建模方法 ，通过引入一类方案选择库所和方案评价变迁 ，
可以灵活地实现与 各种优化方法的集成。给出了一个结合局部禁忌搜索的蚁群算法。通过示例，表明了这种多产品间歇过程调度问题的建模
与优化方 法 的有效性 。
关奠 诩 ：多产 品间歇 过程 ；有色赋 [I；]'Petri网 ； 蚁群 算法 ；禁忌 搜索
M odeling and Optimization 0f M ultiproduct Batch Plant Scheduling
CAO Ruijin，YU Huanjun．HU Shangxu
(Department ofChemical Enginccring．Zhejiang University、Hangzhou 3 10027)
【Abstract l The method of modeling and optimization of multiproduct batch plant scheduling with colored and timed Pctri net is presented A
sequential order option place and a option evaluation transition are introduced to integrate oimization aIgorithm and solve the scheduling problem flexibly
．
An ant colony system with local tabu search algorithm is presented to overcolYic these defect．Through case study
，
the efi'ectiveness of the proposed
method is iIlustmted．
【Key wordsl Multiproduct batch plant；Colored and timed Petri net(CTPN1：Ant colony algorithm；Tabu search
间歇化工过程包括 两种形 式 ：多 目的过程和多产品过
程 。多目的过程指同一种产品可能经过不同路径 ，不同产品
具有不同加工路径 。多产品过程指所有产品经过同样的加工
路径。多产品间歇过程普遍存在于精细化工、制药和食品等
行业 ，由于中间产品化学物理性质的不同，常见的有 以下几
种中间存储策略 ：(I)无限中间存储(uls)；(2)有限中问存 储
(FIS)；(3)无中间存储 (NIS)；(4)零等待(zw)；(5)有 限等待
(FW)。间歇过程生产中存在大量 的顺序和并发操作 ，对其
进行建模与优化控制是间歇过程调度问题的一个重要内容。
一 个完整 的调度 方法 应该包 括两个 方面 ：(1)能够 清
晰、简洁地描述调度 问题 ；(2)提供解决该形式化 调度问题
的优化方法。本文提出的基于有色赋It；IPetri网的多产品间歇
过程调度问题的建模 方法 ，引入 r一类方案选择库所和方案
评价变迁，可以方便地集成各种优化方法，不仅具有很强的
建模能力而且可以根据实际情况选择优化策略，使求解这一
类调度问题更加灵活方便。
多产品批处理调度是化工领域 的一个典型问题，在数学
上是NP完全的，因此近年来一些随机优化方法也被用于 求
解该问题，如模拟退 火?、蚁群算 等 。由于蚁群 算法在
组合问题领域表现出的良好 能，国内也开始对此方法进行
研究，和其它随机优化算法类似，它也会出现搜索时间过长等
缺点。本文提出的结合局部禁忌搜索的蚁群算法可以加快搜
索速度，在求解多产品批处理调度问题上取得 了很好效果。
l调度问题建模
1．1问题陈述
多产品间歇生产过程凋度一般作 以下3个假设 ：(1)多种
产 品遵 循同样的加工路径 ；(2)在 加工过程中 ，每批产品不
能和其它批次的产品混合 ，也不能分开在不 同设备．1-处理 ；
(3)原料和产品有足够 的存储容量 。调度问题 一般描述为N个
产品经过M类加工设 备(每类设备可能有多个加工单元)，产
品i在设备j上的加工时间为‘．，如何对 产品排序使生产时间
一 56-一
最短 ，该调度问题包含 的子问题有两个 ：产品排序和生产时
间 。
本文只考虑UIS和ZW两种中间存储策略。对于UIS间歇
过程调度 ，因为中间存储设备单元数量无限大，加工产品在
某个设备单元上一旦结束就立 即释放此单元 ，如果下一设备
单元没有空 闲，则进入存储设备中等待。而对于zw间歇 过
程调度 ，因为没有中间存储设备，加工产品在某个设备单元
加工结束后直到进入下一设备单元才释放此加工单元 ，又 由
于是ZW等待，在某个单元中一旦达到要求加工时间，必须
立即向后移走 ，如果加工过程不能满足这个约束条件 ，必须
推迟这一批产 品的最早加工时刻。
1．2有色赋时Petri网
Petri网由于其强大的图形表达能力和成熟的数学分析理
论 ，非常适合用于系统建模，应用于间歇过程调度建模方面
也有很大的进 。有色赋时Petri网是一种高级 网系统 ，即
在Petri网的基础上给库所结点和变迁结点上引入了时间的参
量 ，不仅能够清晰地描述间歇生产的资源约束而且能够表示
时间上的约束关系。另外 ，对于Petri网中的托肯(token)赋 予
个性 ，同一类的托肯染上同一种颜色，不同类的托肯以不 同
颜色 区分，这样一个库所可以包含几类托肯 ，一个变迁可 以
有多种变化 ，可 以大大降低模 型的复杂性 。图 1是UIS多产
品间歇生产过程调度Petri网模型 ，图2是zw多产品间歇生产
过程调度Petri网模型 ，图中库所和变迁的解释见表 1。图1和
图2中的虚框表示可能经过多个／Jn：I：设备单元的简化图。
基 金项 目：国家 自然科 学基 金 资助项 目 (20076041)
作者简介 ：曹瑞金 (1972一) ，男，硕士生，研究方向：化工信息
智能处理 ，企业级信息系统 ；俞欢军，博士 、副教授 ；胡上序，教
授 、博导
收稿 日期 ：2003-07—24 E-mail：caorj@infotech．zju．edu．cn
维普资讯 http://www.cqvip.com
圈1 U IS多产品问 过程调度
圈2 ZW多产品f回JIj旺程调度
裘1 Petri两楱塑库所和变迁的解释
库 所 变 迁
Sl 方案选择库所 Tl 产品在第1个设备上开始加工
S2 待加工产品库所 T2 产品在第1个设备上结束加工
S3 S4．S5 设备资源库所 T3 产品在第2个设备上开始；N_T-
S6．S8．S 10 产品在设备上加工 T4 产品在第2个设备上结束加工
S7．S9 中间产品库所 T5 产品在第3个设备上开始加工
Sll 完工产品库所 T6 产品在第3个设备上结束加工
T7 方案评价变迁
有色赋时Petri网模型的详细描述如下 ：
定 义 1有色赋时Petri网是一个多元组CTPN=(P，T；
F， C，I_，l+，D，Mo)。
其 中：
(1)P为有限库所集 ，一般 用圆圈表示 ；T为有 限变迁
集，一般用直线表示 ；F为连接P和T的流关系集合，一般用
有向弧表示。
(2)C=：C(P)U C(T)，是有限库所集和有限变迁集上的颜
色集合。
图l和图2中托肯的颜色有3种 ：Sl中的托肯为产品排序
方案类 ，用颜色X表示 ，x．i表示 方案X中第i批要加工 的产
品；S2中的托肯为待加工的产品类，用颜色Y表示 ，Y=<产
品l，产品2，?>产品i用Y．i表示 ；s2中的待加工产品必须遵
循Sl中给定方案排序加工 ；S4、S5、S6中的托肯为表示空
闲设备单元类，用颜色m表示 ，m．i表示第i类设备，每类设
备还有不同的颜色表示不同的加工单元。变迁上的出现色表
示变迁的不 同发生方式 ，Tl、T3和T5用复合色
表示，< i，y．j，rrLk>表示这个复合色的一个单色 ，即方案x
中的第i批产品是产剐 开始在设备k上加工。
有色Petri网是一种高级网技术，可以把同一类的个体合
并起来并且可以在同一层次上进行抽象 ，因此图1和图2还可
以进一步简化 。但是过于 忽略细节在 图形表达方面不太直
观 ，因此这里不做进 一步研究。
(3)I_∈【c(P卜·C(T)]，1．∈【C(T)--*C(P)]。
(4)D是每个库所相关的时问参数。
图l和图2中S6(t)、S8(t)和sl0(t)为赋时库所，时间参数t
表示托肯必须在这些库所中停 留的时间。图2中的S7(0)、S9(0)
表示瞬时库所，即一旦这些库所中有托肯，后继变迁必须马上
触发移走托肯。没有时间参数的库所表示没有时间约束。
J
(5)Mo为 初始标识 ，表示初始状态下托肯在库所中的分
布 。
图l和图2的Mo=( Y，m．I，m．2，m．3，0，0，0，0，0，0)。
定义2 如果存在一个变迁序列使得托肯从初始状态移
动到中止状态 ，当且仅 当托肯流过的所有的赋时库所满足 时
间约束，这也就是CTPN网的可调度性 。
托肯从初始状态移动到中止状态过程中，如果不满足可
调度性 ，则必须 回溯到向前发生序列并调整其发射时间。
1．3多产品间歇生产过程调度蔗模
基于CTPN网进行形式化建模 ，调度 目标就是使初始标
识 一(X，Y，m．1，m．2，m．3，0，0，0，0，0，0)转移到
中止标识M =(0，0，m．1，m．2，m．3，0，0，0，0，0，y)
的所有可达树 中时间最小 的路径 。图l和图2中的变迁T7表
示达到中止状态 以后，对这一次的产品排序的方案进行评价
并返回初始状态 。引入方案选择库所和评价变迁 可以集成优
化 方法 以选择优化排序方案。
一 般假设每类设备 中加工单元只有一个 ， 表示第i
批产品在第j个设备上的期望开始加工时刻，Ei,j．f~示第i批
产品在第j个设备 上的期望结束加工时刻 ， ． 和E ．对 应 了
图 l和图2的开始加工变迁和结束加工变迁的触发时间。 ；表
示第i批产品在 第j个设备上的加工时间，对应了图l和图2中
加工库所的延迟 时间。
调度 目标是安排产品排序使得完工时间最小的过程为
Min{Max{E ．r}} (I)
对于UIS多产品间歇生产过程，第i批产品在第j个设备
上的期望开始加工时刻和期望开始完工时刻为：
E
．
=Max{Ei．|_I．r，E__1．I．r} (2)
Ei
．
j．r= Ei
． j． 。
+ ti
．
j (3)
对于zw多产品问歇生产过程 ，第i批产品最早开始加工
时刻为：
Ei．1． M
．
ax(O，Ei j．f一 ri．。) (4)
a=l
第i批产品在第j个设备上的期望开始加工时刻和期望开
始完工时刻为 ：
i— I
E。
．
l，= Ei
．
j．。= Ei
． 1． +gti．。
a— l
(5)
2结合局部禁忌搜索的蚊群算法
在 图 l和 图2中由于增加了Sl方案选择库所和T7评价 变
迁 ，可以将CTPN模型与优化策略进行集成 以选择优化排序
方案，已经有多种优化方法用于求解多产品的排序问题，如
分支定界、模拟退火、遗传算法等方法 。近年来，蚁群算法
在组合问题上取得 了一系列较好的试验结果 ，表明了它是一
种比较有前景的方法 。本文提 出了一种结合局部禁忌搜索的
蚁群算法可以改善搜索性能 ，加快搜索速度。
2．1蚊群算法
人工蚁群 系 的原理就是模仿蚂蚁在搜索食物过程 中
的协同学 习机制 ，蚂蚁在寻找食物的路径上释放一种分泌物
称为信息激素，一定范围内的其它蚂蚁能感受到信息激素的
强度并影响它们 向强度高的方向移动。当一些路径上通过的
蚂蚁越多，信息激素的强度也随之增加，以后的蚂蚁选择这
些路径的概率也越大 。蚂蚁间就是通过这种信息传递机制，
互相协作，完成复杂的任务。蚁群算j虫I 在人工蚁群系统的
一 57—
维普资讯 http://www.cqvip.com
基础上增加了全局更新、局部更新规则，使整个算法更有效。
以产品排序的问题 说明蚁群算法 ，假设有N个产品，m
只蚂蚁 ，t(i，j)(i，j=1，2，?，N)表示顺序加 工的产品j
和j之 间的残余信息量，初始时刻t(i，j)=c(c是常数)，蚂
蚁k(k=1，2，?，m)在运动过程 中根据信息量选择下一个
要加工的产品，正在 加工的产品r利用以下状态规则选择下
一 要加工的产品S：
I argmax(r(r，s)u (r，s))ifq≤q0 ==i
s
“? ”
。th。 。
’
其中：allowed(k)表示蚂蚁k选择未加工的产品集合 ，刀(i，j)
表示t时刻加工产品i时选择产品i为下一批加工产品的启发函
数 ，q为【O，1】的随机数，q。∈(0，1)为实现变异的参数 ， 为
参数表示启发函数的重要性。s按以下概率来选择 ：
p(r，S)=
—
， J∈aIIowed(k) ∑r(r，s)叩 (r，s)? (7)
sE=|towed t k'
0，j allowed(k)
当每只蚂蚁都按状态规则确定了下一步要加工的产品，
局部修改规则为 ：
r，s)--0— r，s)_+ (8)
其中 ：p ∈(0，1)，t fI=(Lmin*m)一?L i 为记录中的蚂蚁最小
的完工时间。
当所有的蚂蚁全部加工结束后，记录当前循环中所有蚂
蚁中的最小完工时间L1n ，全局修改规则为 ：
r(r，s)=(I一口) r(r，s)+t2'·L-Irai
0 ∈(0， I)
2．2结合局部禁忌搜索的蚁群算法
在搜索初始阶段 ，各个路径上的信息量差别不是很大 ，
因此需要较长时间才能找到较好路径 ，因此文献【7]提 出 了
结合2-opt或者3一opt局部搜索 的蚁群算法 ，也就是对每 一代
最好的蚂蚁所走过的路径进行局部交换 。这种局部搜索方法
基于3个方面的考 虑：(I)避免过早出现停滞 ；(2)其它位 置
的顺序关系没有改变 ，不会出现由于变异太大而产生不可预
计的结果；(3)这个计算量 比蚂蚁循环一次 的计算量要小 。
试验结果表明该方法有效 ，但有时会 出现较早的停滞现象 ，
为解决此问题 ，本文提出了结合局部禁忌搜索的蚁群算法。
禁忌搜索是一种人工智能算法 ，它是局部搜索算法的一
个扩展 ，其重要思想就是标记以前得到的局部最优解到禁 忌
表中，并在下一次循环中避开它们。禁忌表是一 个先进先出
的队列 ，它的两个重要指标是禁忌对象和禁忌长度 ，禁忌对
象就是禁忌表中那些被禁的变化元素，禁忌长度就是记忆禁
忌表中对象的个数。令禁忌对象就是加工次序方案，禁忌长
度=lnt(4, nIn1个数)。由于禁忌搜索禁止重复以前达到的局
部最优状态 ，因此可以在局部搜索 阶段搜索更大的状态 空
间，防止过早出现停 滞，同时也能加快搜索速度。
结合局部禁忌搜索的蚁群算法如下：
(I)Initialize
(2)Loop
(3)所有的蚂蚁开始准备一次循环
(4)Loop
(5)所有的蚂蚁按状态规则向前走一步
(6)执 行局 部修 改规 则
(7)Until所有蚂蚁完成一个循环
一 58一
(8)记录当前循环中最好的解
(9)Loop
(1 0)如果 该解 在禁 忌表 中 ，寻 找下一 个较 好的解
(11)Until该解不在禁忌表中
(I2)如 果该 解 不存 在 ，转 (I 5)
(I3)对 该解 作2-opt局 部搜索
(I4)如果 局 部 搜 索解 有 所改 善 ， 替换 当 前循 环 中记 录最 好 解 ．
将该 解放 入禁 忌表 中 ；否 则 ，放 弃
(I 5)执行 全 局修 改规 则
(I6)Until中止 条件 为止
2．3计算示仞
表2是结合局部禁 忌搜索 的蚊群算法与蚊群算法的 比
较 ，NXM表 示N个产 品经 过M个设备 ，每 个例子测试 5O
次 。ACO表示 用蚁群算法 ，L—ACO表示用结合禁忌局部搜
索的蚁群算法 。m=30，q。=0．9，p=Q =0．1，p =2，启
发函数为1／(Tij+~· )，Tii为第j批产品加工时设备的空闲时
间， 为髑 批产品的加工．时间和，^ ∈(0
， 1)，这 里取 0．5。
当问题规模增大时，结合局部搜索的蚁群算法测试的结果 优
于蚁群算法的测试结果。
表2结合局部蘩墨搜索的j囊【群算长与筑群算法的比较
N ×M UIS UlS ZW ZW
Proportion of MeaR deviation Proportion of Mean deviation
beSt ofbest best ofbest
ACO L-ACO ACO L．ACO ACQ L-ACO ACo L．Ao0
IO × 3 100 100 0．0 0．O 100 100 n0 0．0
I5×3 l00 100 0．0 0．O l00 l00 0．0 0．0
20× 3 98 98 0．1 0．I 98 100 0．09 0．0
30× 3 92 98 0．16 0．09 92 94 0．15 0．I2
5O× 3 92 94 0．I2 0 09 90 94 0．1 0．08
单位 ：％
3 结论
本文利用CPTN准确地描述了多产品批处理生产过程 的
时间顺序、事件并发和资源共享，建立数学模型，引入评价
变迁和 方案库所 ，可嵌入各种优化方法求解UIS和ZW多产
品间歇过程排序问题 。通过示例计算表明本文的结合局部禁
忌搜索 的蚊群算法 改善 了蚁群 算法的搜索性能。UIS和ZW
间歇调度问题分男Ⅱ是有中间存储设备和无中问存储设备中的
一 般化 的问题，因此该建模和优化方法可方便地扩展到其它
中间存储策略的间歇调度 问题 中，具有 良好的应用前景。
参考文献
l王 举，袁希刚，陈中州．用于多产品间歇化工过程排序 的模拟退
火算 法fJ1．化工 学报、2000，5l(6)：751．756
2 Jayaraman V K．Ant Colony Framework for Optimal Design and
Scheduling of Batch Plants fJ1，Computers Chem．Engng,2000，24：
l901．19l2
3 Kuriyan K，Reklaitis G V．Scheduling Network Flowshops SO as to
Minimize Makespan fJ1．Computers Chem．Engng，l989，l3(1／3)：l 87
4 Gu Fian long,Cai Guoyong．The Short Term Scheduling Technique
Batch on Tim ed Petri—Net Representation for M ulti
—
Product Batch
Plants fJ1．Control Theory and Applications，2000，l 7(6)：933—936
5 Dorgo M，Maniczzo V，Colomi A．The Ant System：Optimation by a
Colony ofCooperating Agents fJ】．IEEE Trans．on System，Man and
Cybernatics，l 996，26(1)：28-4 1
6 Dorigo M，Gambardella L M ．Ant Colonies for the Travelling Salesman
Problem[J]．Biosystems，1997，43：73．8l
7 Dorigo M．Luca M ．Ant Colony System：A Cooperative Learn ing
Approach to the Travelling Salesman Problem[J]．IEEE Trans．on
Evolutionary Computation ，l 997，l(1)：53—66
维普资讯 http://www.cqvip.com
多产品间歇过程调度问题的建模与优化.pdf
