中国科学: 技术科学 2010年 第40卷 第1期: 41 ~ 51

《中国科学》杂志社

SCIENCE CHINA PRESS

tech.scichina.com

一类含积分约束的生产制造系统优化调度

管晓宏, 翟桥柱*, 冯泳翰, 高峰

①

①

②

①

① 西安交通大学系统工程研究所, 机械制造系统工程国家重点实验室, 智能网络与网络安全教育部重点实验室, 西安 710049; ② 西安交通大学理学院, 西安 710049 * E-mail: qzzhai@sei.xjtu.edu.cn

收稿日期: 2009-04-21; 接受日期: 2009-08-03

国家自然科学基金(批准号: 60704033, 60736027)、国家高技术研究发展计划(“863”计划)(批准号: 2007AA04Z154)和教育部新世纪优秀人才计划(批准号: NCET-08-0432)资助项目

摘要 “即时消费”类生产制造系统的优化调度具有重要学术和应用价值. 满足此类系统对产量的实时需求, 考虑调度计划的可实现性具有挑战性. 如何得到精确满足累积产量实时需求的最优调度目前尚无系统方法, 迫切需要研究. 本文建立了含积分约束的生产制造系统优化调度新模型. 通过对生产量变化率约束的深入分析, 证明了该类优化问题等价于光滑非线性规划问题. 生产设备在各时段的产量上下界可表述为时段初、末时刻瞬时生产率的二元函数, 且为精确可达的上下界. 本文结合梯度映射的单调性, 证明了上下界函数的凸性(凹性), 在生产成本为凸函数时, 进一步证明了此类优化调度问题等价于凸规划问题. 本文以上述分析为基础, 针对含积分约束的生产制造系统优化调度问题, 提出了两阶段数值求解方法, 在许多情况下可以迅速获得调度问题的全局最优解. 新模型和相应求解方法克服了生产量变化率约束带来的困难, 获得了精确满足累积产量实时需求的最优调度. 本文同时以电力生产优化调度问题为例, 进行数值求解, 并对结果进行了讨论, 验证了新模型和相应方法的有效性.

关键词 生产调度 积分约束 最优控制 凸规划

生产调度是生产制造系统运行最重要的任务之一. 通常, 调度的主要目的是合理调配资源和设备, 在满足需求、确保安全等运行约束的前提下降低成本、节约资源、减少污染. 优化生产调度能够在不改变基本工艺过程、不更动装备的情况下实现节能降耗, 降低成本, 获得巨大的社会经济效益, 在当前能源、环境问题日趋严峻的形势下, 具有特别重大的意义. 因此, 生产调度理论与方法长期以来一直是一个活跃的研究领域, 受到众多学者关注[1~6].

在生产制造系统中, 有一类生产所谓不可存储产品, 即“即时消费”或“鲜活”(Perishable)类产品的系统[1], 其显著特点是产品必须立即消费而不能存储, 最

典型的例子是电力生产. 在电力生产调度问题中[7,8], 每个瞬时生产的电量必须与系统负载需求保持平衡. 其它类似的系统包括管道输送天然气生产和许多服务业的即时服务等. 这类系统的优化调度问题不但会有实时系统需求等, 还可能有十分复杂的离散和连续的动态运行约束, 几乎不可能按连续时间求解. 目前广泛采用的建模方式是将时间离散化, 在一个调度时段内, 假设系统需求为恒定值, 用生产设备的平均生产量满足这一时段恒定的需求. 将平均生产量作为优化决策变量, 求解离散时间点的生产量, 可将调度问题由连续时间最优控制问题转化为数学规划问题, 从而大大降低问题的复杂性[2,7~10].

引用格式: Guan X H, Zhai Q Z, Feng Y H, et al. Optimization based scheduling for a class of production systems with integral constraints. Sci China Ser E-Tech Sci,

2009, 52(12): 3533?3544, doi: 10.1007/s11431-009-0359-y

管晓宏等: 一类含积分约束的生产制造系统优化调度

时间离散化的生产制造系统优化调度问题一般模型为整数规划或混合规划问题, 国内外研究者对此类问题进行了大量研究[2~19], 取得了许多重要成果. 基于Lagrange松弛的优化方法是解决此类问题最有效的方法之一[3,5,9,11]. 近年来, 随着通用整数规划或混合规划算法效率和计算机性能的大幅度提高, 通用离散和混合优化方法求解此类生产制造系统优化调度问题也取得了很大成功[10,12~14].

由于满足“即时消费”类生产制造系统的实时需求是对调度计划的基本要求, 按离散时间模型获得的调度方案的可实现性就十分重要. 许多生产设备产量的变化率受物理限制, 如发电机组出力的爬升率有限, 不可能每个时间段起点突变, 完全按上述离散时间模型得到的调度计划不可能操作实现, 也不一定有必要. 实际上很多情况下, 我们只要求这类生产系统在一个时段内的累积产量, 即生产率对时间的积分精确等于实时需求. 例如电力生产系统的生产率是出力(功率), 我们只要求系统在一个时段内交付的能量(功率的积分)满足实时需求. 然而, 在复杂调度问题中“不多不少”精确满足累积产量的实时需求绝非易事. 我们在前期工作中详细阐述了电力生产中离散时间最优调度即使满足出力爬升约束, 也可能存在能量不可交付性, 并给出了判定能量可交付性或调度计划可实现性的充分必要条件[16]. 然而, 如何取得精确满足累积产量实时需求的最优调度目前还没有答案, 迫切需要研究.

本文建立了含积分约束的生产制造系统优化调度新模型. 通过对生产量变化率约束的深入分析, 证明了该类优化问题等价于光滑的非线性规划问题. 生产设备在各时段的产量上下界可表述为时段初、末时刻瞬时生产率的二元函数, 且为精确可达的上下界. 本文结合梯度映射的单调性, 证明了上下界函数的凸性(凹性), 在生产成本为凸函数时进一步证明了此类优化调度问题等价于凸规划问题. 本文以上述分析为基础, 针对含积分约束的生产制造系统优化调度问题, 提出了两阶段数值求解方法, 在许多情况下可以迅速获得全局最优解. 新模型和相应求解方法克服了生产量变化率约束带来的困难, 获得了精确满足累积产量实时需求的最优调度. 本文以电力生产优化调度问题为例, 进行了数值求解, 并对结果进行了讨论, 进而验证了新模型和相应方法的有效性.

应该指出, 本文提出的模型和求解方法可以推

42

广到求解有库存或存储的生产系统调度问题[2]. 限于篇幅, 此类问题未在本文中讨论.

本文结构安排如下: 第1节用一个简单例子说明了目前文献中通用的建模方式存在的缺陷; 第2节给出了按连续时间方式表述生产率及产量积分约束的精确调度模型; 第3节对模型的约束结构特征, 尤其是积分约束的结构特征进行了深入分析, 得到了一些重要理论结果; 第4节证明了新模型等价于一个可行域为闭凸集的光滑非线性规划问题, 特别当生产成本为凸函数时进一步等价于一个简单的凸规划问题, 提出了两阶段数值求解框架; 第5节以电力生产优化调度问题为例验证了本文提出的有关理论和方法; 第6节对全文进行了总结.

1 积分约束的必要性举例

我们以电力生产调度的简单例子, 说明积分约束的必要性.

某台发电机组最小发电功率为150 MW, 最大发电功率为450 MW, 最大爬升速率为6 MW/min, 假定第1 h内的发电功率恒定为g(1) = 150 MW, 现确定第2 h的发电计划.

如果按传统模型, g(1), g(2)表示第1和2 h内机组的平均发电功率(单位: MW). 如每个离散调度时段长度为1 h, g(1), g(2)在数值上等于机组在对应时段的发电量或产出的能量(单位: MWh), 并满足以下约束:

150≤g(2)≤450,

g(2)?g(1)≤6×60=360.显然在满足上述约束的情况下, g(2)的最大取值为g(2) = 450 MW. 然而, 容易说明机组在第2 h内的最大发电量或能量远远无法达到450 MWh, 见图1所示.

图1 机组发电功率与电量

中国科学: 技术科学 2010年 第40卷 第1期

因机组在第1 h末发电功率为150 MW, 对应于图1中A点, 由于爬升速率有限, 发电功率不可能在第2 h初突变, 即便按最大爬升速率上升, 至多在1 h 50 min

k=1,2,",K; (2) ∑pi(k)=D(k),

i=1

I

(b) 原料限制:

I

处达到最大发电功率450 MW, 对应图中C点, 此后

保持不变. 因此机组在第2 h内最大可实现的发电量为五边形 ACDFE 的面积, 对应为 325 MWh, 远低于450 MWh(对应于矩形 BDFE 的面积). 因此, 如果要进行电量的调度, 应该考虑发电功率的积分和相应的约束.

∑aj,ipi(k)≤Rj,k, (3)

i=1

其中j=1,2,",J, k=1,2,",K. 约束(3)具有通用性, 可以表示许多形式的约束, 除原料限制约束外, 还可表示电力生产调度中的系统备用约束、传输容量约束(均可视为广义的原料限制约束)等.

(c) 产量-生产率关系:

pi(k)=∫

kτ(k?1)τ

2 含积分约束生产制造系统优化调度模型

考虑一个生产制造系统有I台生产设备, 生产过

gi(t)dt, (4)

程需消耗J种原料、调度周期为K时段. 本文采用的变量和符号定义及说明如下:

i j k

设备编号,i=1,2,",I; 生产原料编号, j=1,2,",J; 调度时段编号, k=1,2,",K; 每个调度时段的时间长度;

第i台设备生产每单位的产品, 需消耗的第j种原料量;

Rj,k t gi(t) ui(t) pi(k) Δi

i,gi

其中i=1,2,",I, k=1,2,",K.

(d) 生产率-生产率变化率关系:

gi(t)=gi(0)+∫ui(ξ)dξ,?t∈[0,Kτ], (5)

0t

其中i=1,2,",I. 在本文考虑的调度问题中, ui(t)为决策变量, gi(t)和pi(k)为状态变量.

(e) 生产率变化率界约束(生产率爬升约束):

?Δi≤ui(t)≤Δi,?t∈[0,Kτ], (6)

τ aj,i

第k时段允许消耗的第j种原料总量; 连续时间变量, 从0时刻开始计时, 调度周期总时间长度为K?τ;

设备i在t时刻的生产率, 是时间的连续函数;

设备i在t时刻的生产率变化率, ui(t)是分段连续函数;

设备i在第k时段的生产量; 设备i的生产率变化率上限; 设备i的最大、最小生产率;

其中i=1,2,",I.

(f) 生产率界约束:

gi≤gi(t)≤i,?t∈[0,Kτ], (7)

其中i=1,2,",I.

(g) 调度初始及终止时刻生产率约束:

gi(0)=gi?,0,gi(Kτ)=gi?,K, (8)

其中gi?,0和gi?,K是给定常数. 该组约束中的后一个可