整数规划算法在生产调度的应用研究

发布时间：2018-11-26 11:30

【摘要】：生产调度为实际生产带来了明显的经济效益,受到了国内外研究学者的广泛关注,是当前理论研究和应用研究的热点。基于离散时间表达的间歇过程混合整数线性/非线性规划(mixed integer linear/non-linear programming,MILP/MINLP)调度模型,一般通过整数规划算法来求解。常用的整数规划算法包括分支定界法和割平面法,不断提高整数规划算法的效率和精度,对于求解生产调度问题有着重要的研究意义。本文针对整数规划算法在生产调度领域的应用做了以下研究:(1)针对经典分支定界法任意选择分支变量的不足提出改进,定义了一种伪贡献分支策略,根据非整形变量取整对目标函数影响的大小,选择优先分支的变量。将伪贡献分支策略与广度优先搜索策略相结合,提出改进的分支定界法。分别采用经典分支定界法和改进的分支定界法对数值案例进行仿真,结果表明,改进算法有效减少了分支次数和调用线性规划的次数,明显缩短了求解时间,达到了优化搜索路径,提高算法求解效率的目的。(2)将改进的分支定界法与割平面法相结合,提出改进的分支切割法。在求解过程中一方面通过添加切平面,割去可行域中不存在最优解的部分,缩小最优解的查找范围,另一方面借助伪贡献分支策略,有效减少分支次数。改进的分支切割法结合了分支定界法和割平面法的优点,弥补了两种算法独立处理整数规划问题时的不足。(3)以啤酒生产为背景,在考虑设备加工能力、存储容量、物料平衡等约束的基础上,使用本课题组人员编写的“流程工业智能建模平台”,自动生成MILP调度模型系数矩阵,采用改进的分支切割法求解调度问题,结果表明了改进算法求解此类问题的有效性。
[Abstract]:Production scheduling has brought obvious economic benefits to actual production, and has been widely concerned by scholars at home and abroad. It is the focus of theoretical research and application research at present. The mixed integer linear / nonlinear programming (mixed integer linear/non-linear programming,MILP/MINLP) scheduling model based on discrete time representation is usually solved by integer programming algorithm. The commonly used integer programming algorithms include branch and bound method and cut plane method, which improve the efficiency and precision of integer programming algorithm. It is of great significance to solve production scheduling problems. In this paper, the application of integer programming in the field of production scheduling is studied as follows: (1) in view of the shortcomings of the classical branch and bound method, a pseudo-contribution branching strategy is defined. According to the size of the effect of unshaping variables on the objective function, the first branch variables are selected. By combining the pseudo-contribution branching strategy with the breadth-first search strategy, an improved branch and bound method is proposed. The classical branch and bound method and the improved branch and bound method are used to simulate the numerical cases respectively. The results show that the improved algorithm can effectively reduce the number of branches and the times of calling linear programming, and obviously shorten the solving time. It achieves the purpose of optimizing the search path and improving the efficiency of the algorithm. (2) an improved branch cutting method is proposed by combining the improved branch and bound method with the cutting plane method. On the one hand, by adding a tangent plane, we cut off the parts of the feasible domain where there is no optimal solution, and reduce the search range of the optimal solution. On the other hand, by using the pseudo-contribution branching strategy, we can effectively reduce the number of branches. The improved branch-cutting method combines the advantages of the branch-and-bound method and the cutting plane method, and makes up for the shortcomings of the two algorithms in dealing with integer programming problems independently. (3) taking beer production as the background, considering the equipment processing capacity and storage capacity, On the basis of the constraint of material balance, the MILP scheduling model coefficient matrix is automatically generated by the intelligent modeling platform of process industry, and the improved branch cutting method is used to solve the scheduling problem. The results show that the improved algorithm is effective in solving such problems.
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4

【参考文献】