2006, Volume 8, Issue 9
Strategic Study of CAE >> 2006, Volume 8, Issue 9
Variable-separating-based Space Decomposition Algorithm of Production Scheduling
School of Control Science and Engineering, Shandong University, Jinan 250061, China
Next Previous
Abstract
Most static production scheduling problems are formulated in MILP ( mixed integer linear programming) or MINLP(mixed integer non-linear programming) . It is difficult to find solutions of scheduling because of its large scale and combinatorial characters. According to the features of MIP (mixed integer programming), integral variables and continuous variables are separated and the searching space is decomposed naturally into many continuous subspaces of less scale. Taking a typical batch production scheduling as a case, the analysis shows that variable-separating strategy decreases the scale of continuous searching problem greatly and makes it easy to solve, which can improve the speed and efficiency of optimization.
Keywords
production scheduling ; space decomposition ; sub-definite method
Figures
图1 混合整数规划搜索空间示意
图2 整数变量松弛后空间示意
图3 状态-任务网络
图4 设备-任务网络
京公网安备 11010502051620号
