多产品批处理过程调度的MILP建模

A New Mixed Integer Linear Programming(MILP) Model for Multiproduct Batch Plant Scheduling

基于时间间隙的概念和连续时间描述 ,将设备、产品分配给时间间隙分别表达为两类 0 - 1变量 .采用一个时间轴 ,建立了具有并行生产线的单阶段多产品批处理过程的调度数学模型 .模型表达为一个混合整数规划 ( Mixed Integer Linear Programming,MILP)问题 .相对于已有的基于时间间隙描述的调度模型 ,该模型 0 - 1变量少 ,且能处理顺序相关建立时间 .求解采用分支定界法( BAB) .计算表明 ,该模型求解速度快 ,松弛线性规划和 MILP的最优解之差 ( Integrality Gap)小 。

This paper presented a new mixed integer linear programming(MILP) mathematical model for the scheduling of single stage multiproduct batch plant with parallel lines based on the notation of time slot and continuous time representation. The allocation of products and units to time slots is handled through two sets of binary variables respectively, and one time coordinate is used. This model involves less binary variables than any other model based on the notation of time slot, and can accommodate sequence dependent setup time when different products are processed on the same unit. The branch and bound technique was used to solve the model that reveals small integrality gap. The computation shows that the optimal solution can be derived quickly, especially when the scheduling problem involving several identical several batches is considered.