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

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

作　　者：陈昌领[1] 袁德成[2] 邵惠鹤[1] 

机构地区：[1]上海交通大学自动化研究所,上海200030 [2]沈阳化工学院过程工程中心,沈阳110021

出　　处：《上海交通大学学报》2002年第8期1132-1137,共6页Journal of Shanghai Jiaotong University

基　　金：国家重点基础研究发展规划 (973 )项目 (G19980 3 0 4)

摘　　要：基于时间间隙的概念和连续时间描述 ,将设备、产品分配给时间间隙分别表达为两类 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.

关 键 词：MILP建模 短期调度 多产品批处理过程 混合整数线性规划 生产时间 化学工业 数学模型 

分 类 号：F407.702.2[经济管理—产业经济] F224.31