用Lagrangian松弛法解化工批处理调度问题

SCHEDULING FOR BATCH CHEMICAL PROCESSES USING LAGRANGIAN RELAXATION BASED APPROACH

研究基于Ｌａｇｒａｎｇｉａｎ松弛法的化工批处理过程的调度方法．建立了化工批处理过程调度问题的一种混合整数规划（ＭＩＬＰ）模型，并通过松弛离散变量和连续变量共存的约束，将问题分解为一个两层次的优化问题，其中上层是原问题的对偶问题，下层由两个子问题构成：一个与产品批量有关，另一个确定操作时间表，分别用线性规划和动态规划方法解这两个子问题．然后从对偶问题的解构作原问题的可行解．数值试验结果证明了该方法的有效性．

In this paper,an approach based on Lagrangian Relaxation to schedule batch chemical processes is presented.The scheduling problem is modeled as a compact MILP formulation.The constraints including both discrete and continuous variables are relaxed and the problem is turned into a two level optimization problem.The high level is the dual of the original problem,and the low level consists of two subproblems,one for batch sizing,the other for deciding the time table.Linear programming and dynamic programming methods are used to solve the subproblems.A feasible solution is then constructed based on the solution of the dual problem.Computational results are given to demonstrate the effectiveness of the approach.