间歇生产调度优化模型的分周期逼近算法

Periodic approximation algorithm to solve batch plant scheduling model

间歇生产调度过程中存在许多不确定因素,其中最重要的是需求不确定。考虑需求不确定的多周期间歇生产调度优化模型采用离散或连续时间表达方式,将调度时间域分割成大量与调度决策相关的时间段,导致模型中存在大量整数变量,给模型求解造成很大困难。本研究对已有求解方法进行了分析,提出分周期逼近算法。将多周期间歇生产调度决策问题分解为第一周期调度决策问题和其余周期调度决策问题,简化结构,加快求解速度。通过方案树聚集将表达需求不确定信息的方案树转化成若干方案文件,针对每个方案文件应用确定性方法获得调度决策,但只保留第一周期调度决策,可以减小最小利益方案对期望利益的影响,提高第一周期调度决策水平;获得若干第一周期候选调度决策后,以时间收缩三阶段方法确定其余周期较优调度决策,同时应用时间收缩策略和补偿策略,提高其余周期调度决策水平;最后用期望利益评估第一周期候选调度决策并确定全部周期调度决策。实例研究证明了本文提出的算法能够提高间歇生产调度决策水平,同时加快求解速度,能够有效求解多周期间歇生产调度优化模型。

Uncertain factors are prevalent in batch plant scheduling systems, wherein the most important source of uncertainty is proved to be demand. A multi-period batch plant scheduling model with uncertain demand invariably includes numerous binary variables, which leads to considerable difficulties to solve. After the comparison of other traditional approaches such as deterministic approach, two stage approach, two-stage stochastic shrinking-horizon approach etc., a periodic approximation algorithm （PAA） is presented to solve the large-scale stochastic mixed integer linear programming （MILP） problem resulted from the multi-period batch plant scheduling model with uncertain demand. PAA is comprised of two steps by using the aggregation and decomposition of scenario tree which is used to present the uncertain demand. The first step is that a set of deterministic models obtained from the aggregation of the scenario tree are used to search for potential candidate scheduling decisions for the first period of scheduling time horizon. After that, the scenario tree has been decomposed to be two smaller trees, which is benefit for improving the computation times. The second step is that three-stage stochastic shrinking-horizon algorithms can be applied to assess each of these candidates obtained from the first step in terms of the expected profits, which employs both the shrinking-horizon strategy and recourse strategy, and then complete scheduling decisions for all the periods of the scheduling time horizon can be determined. A case study helps to prove the feasibility of PAA to solve the multi-period batch plant scheduling model. The performance of the proposed algorithm shows that it can provide optimal scheduling decisions than other traditional approaches, and also suffers lower computation times than the rigorous multistage stochastic model.