1 引言
生产调度主要涉及一定时间内共享资源的可用性和设备分配等问题, 大都形成混合整数线性规划模型 (MILP)
分支定界类算法将整数变量进行松弛使其连续化, 扩展了搜索域, 大大增加了计算量。近年来, 众多学者致力于智能调度算法的开发和应用, 如模拟退火算法
通过分析混合整数规划的空间特性和生产调度问题模型的实际意义, 提出搜索空间的自然划分, 并利用间歇过程调度模型中整数变量的约束减少待搜索子空间的数目, 同时在连续变量子空间内采用半限定法进一步收缩空间, 最后采用智能算法与数学规划算法分别进行整数变量组合空间和连续子空间的寻优。
2 生产调度模型的空间划分
以间歇过程生产调度为例, 在均匀时间划分方式下, 生产调度的组合特性来自于调度间隔的划分及各调度间隔内设备的选择和分配, 即混合整数规划模型中的整数变量, 而调度间隔数在模型中位于设备组合的指数位置, 使得设备的组合数是以指数形式增长的。调度间隔和每个间隔内设备的分配确定之后, 需要确定连续变量即批量的大小, 产生此种设备分配下的目标值。因此, 可以采用将整数变量和连续变量分离的策略, 分别进行整数变量和连续变量的优化。
《2.1 混合整数规划模型的空间分析》
2.1 混合整数规划模型的空间分析
组合优化问题的可行域是离散点的集合, 连续函数优化问题的可行空间是连续的。而混合整数优化问题如MILP 和MINLP, 由于整数变量的存在, 使得搜索空间被自然地划分成多个分离的子空间, 可行域是间断的, 它们之间的间隔由整数变量决定, 其数量是整数变量的组合数。因此混合整数规划既有组合优化的特点, 又存在单个连续子空间的连续优化问题。混合整数规划模型的空间示意如图1所示。另外约束优化问题的可行域还有约束条件的限制。
《图1 混合整数规划搜索空间示意 》
图1 混合整数规划搜索空间示意 Fig.1 Sketch map of MIP's design space
图1中, 连续变量为有界实数变量, 将整数变量松弛为连续变量, 则搜索空间是灰色区域内的部分 (图2) , 但实际的待搜索空间只是几个分离的线段或断面区域, 松弛后的空间扩展了太多倍, 算法进行搜索的时间必定会大量增加。
《图2 整数变量松弛后空间示意 》
图2 整数变量松弛后空间示意 Fig.2 Sketch map after integer variables are relaxed
《2.2 空间划分及排选》
2.2 空间划分及排选
整数变量的值即设备的分配情况确定后, 批量的确定过程就是在一个连续子空间的寻优过程, 由于存在几个作业的操作共用一台设备的情况, 设备的约束使得整数变量的组合数大大减少。如有n个作业共用一台设备, 组合数由2n降至n+1 (包括该设备不使用的情况) 种可能, 以n=3为例, 使用设备的组合数降至原来的1/2, 使用同一设备的作业数越多, 此类设备数越多, 该组合数 (子空间的个数) 减少的程度越大, 设备约束在可行解域的选择中起到了重要的作用。
3 全局最优性及算法
整数变量将整个搜索域划分为多个分离的子空间, 各个子空间遍历搜索后的最优解也就是整个搜索域的解, 所以子空间的划分不改变最优解的全局性。
《3.1 组合特性的求解》
3.1 组合特性的求解
尽管有设备约束, 在实际问题中算法所要搜索的实际组合数目即子空间的个数仍然较大。因此, 仍然需要组合优化性能较好的算法进行整数变量组合空间的寻优。现代优化算法如模拟退火算法、进化算法、集群智能算法等, 在求解组合优化问题时表现出了较好的性能。
《3.2 子空间收缩及寻优》
3.2 子空间收缩及寻优
整数变量确定后, 根据问题的实际意义, 连续变量的数目由于与其相对应的整数变量的取零而大量减少, 如某作业l不在设备i上生产, 则相应的批量变量就可以不必考虑, 从而连续寻优变得快速简单。对于生产调度混合整数线性规划, 子空间连续变量的寻优是一个线性空间内的搜索, 约束和目标函数都是线性的, 因此可以简单地应用半限定方法
对于混合整数非线性规划MINLP进行变量分离和空间划分后, 子空间内的寻优是连续非线性优化, 但是由于实际调度问题的约束多数是线性的, 所以仍然可以采用半限定方法缩小子空间的搜索范围, 同时采用非线性的搜索算法进行求解。
4 实例分析
图3是Kondili等给出的基于STN (state-task network) 的批处理化工过程的生产调度的静态调度MILP模型, 共有5个加工任务、3种原料、2种产品、4个中间产品。采用等间隔划分方式, 把调度期分为5等份, 共有5个调度间隔 (H=5) 。假定共有4台设备 (i=4) , 则有100个设计变量。
设备使用 X11t, X22t, X32t, X42t, X23t, X33t, X43t, X54t,
批量 B11t, B22t, B32t, B42t, B23t, B33t, B43t, B54t,
存贮 I4t, I5t, I6t, I7t,
其中40个整数变量Xlit, 40个连续变量Blit, 20个中间变量Ijt;120个约束条件, 不考虑原材料供应约束、能源约束和加班约束及设备折旧, 优化指标为最大利润。加工设备及中间产品存储设备容量、初始库存、估计销量、售价等参数见表1, 物料的消耗和产出系数在图3中标注。
《图3 状态-任务网络》
图3 状态-任务网络 Fig.3 State-task network
《表1 批处理化工过程生产调度参数表》
表1 批处理化工过程生产调度参数表 Table 1 Parameters production scheduling of batch process
加工装置容量/kg | ||||||||||
设备 | Unit1 | Unit2 | Unit3 | Unit4 | ||||||
加工容量下限 | 0 | 0 | 0 | 0 | ||||||
加工容量上限 | 100 | 80 | 50 | 200 | ||||||
中间物料存储容量/kg | ||||||||||
物料编号 | S4 | S5 | S6 | S7 | ||||||
物料初始库存 | 40 | 40 | 75 | 80 | ||||||
库存容量下限 | 0 | 0 | 0 | 0 | ||||||
库存容量上限 | 100 | 200 | 150 | 100 | ||||||
单位存储费用/元 | 0.5 | 0.5 | 0.5 | 0.5 | ||||||
估计销量/kg | 售价/元 | |||||||||
调度间隔 | 1 | 2 | 3 | 4 | 5 | |||||
S8 | 15 | 25 | 10 | 15 | 30 | 12 | ||||
S9 | 25 | 35 | 55 | 45 | 65 | 5 |
根据图4设备的分配使用情况, 在不考虑设备约束的情况下, 共有 (u1u2u3u4) H种情形, 其中ui表示设备i的可能使用情况, u1 = 21, u2 = 23+1, u3 = 23+1, u4 = 21;则 (u1u2u3u4) H = 324H, 与设备使用相对应也有324H个连续批量变量Blit, 设备和原材料越多, 采用等间隔划分方式的调度周期H越多, 可能的设备组合情况就越多, 以指数速度增长。
《图4 设备-任务网络 》
图4 设备-任务网络 Fig.4 Unit-task network
根据设备约束, 设备2、设备3可以进行任务2、任务3、任务4的加工, 某一时刻一台设备只能进行一个任务的操作, 从而u1=21, u2=3+1, u3=3+1, u4=21;则 (u1u2u3u4) H=64H, 设备的使用情形降为原来的1/5, 即连续子空间的个数减少了80%。由于2种产品的初始库存都为零, 所以在第一个调度间隔内设备4必须进行任务5的操作, 使用设备2和设备3中的一个或都使用来进行任务3的处理, 从而设备使用的可能情况减少至原来的9/16, 即子空间的个数又减少了44%。采用上述的空间划分策略, 设备的使用确定后, 需要确定相应操作任务的批量的值, 以使目标函数最优。根据设备分配约束, 整数变量Xlit中至多有iH=20个非零, 从而相应子空间内的连续变量Blit至多有20个需要确定, 其余为零, 搜索空间的维数大大减少, 约束数目 (包括变量的边界约束) 降至50个以下, MILP与子空间模型的变量及约束数目对比见表2。且由于子空间模型是线性的, 可以调用MATLAB或LINGO的线性规划函数方便快速地求得此设备使用情况下的最优解。整个问题的求解通过组合优化算法与线性规划算法的组合进行。采用基于空间划分的不完全演化算法
《表2 MILP与子空间模型的变量及约束的数目对比》
表2 MILP与子空间模型的变量及约束的数目对比 Table 2 Comparison of variables and constraints amount in MILP and subspaces
MILP | Sub-LP | |
整数变量个数 | 40 | |
连续变量个数 | 40 | ≤20 |
中间变量个数 | 20 | 20 |
约束个数 | 120 | ≤50 |
5 结论
将混合整数规划的整数变量和连续变量分离, 整个搜索空间被自然地划分为多个连续子空间。在生产调度问题中, 整数变量常代表设备或资源的可用性, 利用生产设备的使用约束, 可以大大减少待搜索的子空间的数目, 连续子空间寻优的变量也大量减少, 从而可以采用较成熟的中小规模算法, 更快地获得更好的解。在整数变量的组合即设备的使用中充分利用调度的特性知识, 将会更有效地减少待搜索的子空间的数目, 减小搜索空间, 从而提供高效的调度求解方法。
参考文献
[3] 李歧强.具有约束指导的模拟退火算法[J].系统工程, 2001, 19 (3) :49~55
[6] 王涛, 李歧强.基于空间收缩的并行演化算法[J].中国工程科学, 2003, 5 (3) :57~61