Integer Programming Algorithm In The Application Of Production Scheduling

Production scheduling has brought significant economic benefits to the actual production.It has been widely concerned by domestic and foreign scholars,which is a hot topic in the current theoretical research and application research area.Mixed-integer linear/nonlinear programming scheduling model based on discrete time expression is usually solved by integer programming algorithm.Commonly used integer programming algorithm includes branch and bound algorithm and cutting plane algorithm.And it has important significance in solving production scheduling problem improving the efficiency and precision of integer programming algorithm.Aiming at the application of integer programming algorithm in the production scheduling area,the following researches are done:(1)In view of the deficiency of branch and bound algorithm to choose an arbitrary variable as the first branching one,a pseudo-contribution branching strategy is defined to choose the priority branching variable which depends on the effect of non-integer variables on the objective function.We propose an improved branch and bound algorithm which combines the pseudo-contribution branching strategy with the breadth-first searching strategy.Using the classical branch and bound algorithm and the improved one to solve the integer programming problems,the results show that the latter can reduce the number of branching and calling the linear programming effectively,shorten the solution time,and achieve the goals of optimizing the searching path and improving the performance of the algorithm.(2)Combining the improved branch-and-bound algorithm with the cutting plane algorithm,an improved branch and cut algorithm is proposed.In the process of solution,by adding the cutting planes,the part infeasible region without the optimal solution is cut off,and the searching range of the optimal solution is reduced.On the other hand,the pseudo-contribution branching strategy effectively reduces the number of the branches.The improved branch and cut algorithm takes the advantages of the branch and bound algorithm and the cutting plane algorithm,and makes up for the shortcomings of the two algorithms when dealing with the integer programming problem independently.(3)Taking beer production as the research background and considering some constraints inequipment processing capability,storage capacity and material balance and so on,we use the improved branch and cut algorithm to solve the MILP scheduling model whose related data from the "Intelligent modeling software for process industry" developed by our research team to automatically generate coefficient matrix of MILP scheduling model.The results show that the effectiveness of the improved branch and cut algorithm for solving such problem.