Branch-and-Cut方法及其在物流时空调度中的应用研究

发布时间：2018-08-02 11:08

【摘要】：制造和物流系统中的物流时间与空间调度问题可以归结为整数规划问题。Branch-and-Cut算法是目前最优求解整数规划问题的有效算法之一,其基本思想为利用分支定界算法的框架结构,在其构建的分支定界树中的叶子节点处增加有效不等式用以动态提升下界(最小化问题),达到减少分支定界树分支个数,提高算法求解效率的目的。由于整数规划问题大多属于NP-难题,因此,研究Branch-and-Cut算法的改进对整数规划的最优求解的规模和效率的提升具有重要意义。本文首先以物流系统时间调度中的典型吊机调度问题为背景,对Branch-and-Cut算法进行了方法研究,以工厂吊机调度为背景进行了方法的应用研究。然后,以图论中的经典图着色问题为背景,对Branch-and-Cut算法进行了方法研究,并以物流系统的空间调度中的板坯入库垛位决策问题为背景进行了应用研究。论文主要工作及研究成果概述如下：1)典型吊机调度问题：对于由M个吊机完成N(MN)个去向已知的待运任务,需要确定任务在吊机上的分配以及在所分配吊机上的执行顺序,在保证吊机任务之间的优先关系要求以及避免吊机间发生交叉和碰撞的同时,使得完成全部任务所需的时间最短。对该问题的整数线性规划模型采用Branch-and-Cut算法求解。基于问题特点的分析提出了有效不等式,并设计了改进的基于禁忌搜索方法的分离策略用于有效不等式的发现。数值实验的结果表明了所提算法的有效性。2)板坯库吊机调度问题：对于由M个吊机完成N(MN)个工件的出库操作,将每个工件的连续(不中断)出库操作定义为一个任务,需要决策出库操作是否中断及全部任务在吊机上的分配及执行顺序,在满足完工顺序、避免吊机间交叉和碰撞、任务在缓冲垛位的服务规则等要求的情况下,使得所有任务的完成时间短。针对该问题建立了初始的整数规划模型,基于对问题性质分析对模型进行重建。基于具有紧下界的重建模型,设计了Branch-and-Cut算法求解。在算法实施中,提出了多类有效不等式用于提升问题下界,同时,引进变量降低技术以有效降低搜索域,进而提高算法的搜索效率。基于工业实际数据的数值实验证明了所提出算法能够在合理的时间内获得工业问题规模的最优解,其性能明显优于商业优化求解软件CPLEX,验证了提出的模型和算法的有效性。3)典型图论优化问题——图着色问题：对给定的图内的每一个顶点着一种颜色,在保证任意相连的两点着不同颜色的要求下,决策所需要的最少颜色个数。针对该问题建立了整数线性规划模型,设计了Branch-and-Cut算法进行最优求解。针对此问题,提出了变量固定策略用于削减可行域,构造了基于动态规划的有效不等式,嵌入了基于独立集的有效不等式、基于团的有效不等式,有效地提高了Branch-and-Cut算法收敛速度。通过Benchmark标准测试数据的实验结果表明了提出的算法的有效性。4)基于图着色的板坯入库垛位决策问题：对于板坯库入库的板坯,需要决策存放的垛位位置,在保证板坯按照出库顺序提取时不产生倒垛操作的要求下,使得占用的垛位数最少。该问题通过归结为图着色问题进行建模,将入库板坯定义为顶点,板坯入出库顺序定义为边,同一垛位的板坯集合定义为图中着同样颜色的点的集合,最少占用垛位数对应于最少使用的颜色数。通过图着色问题建立的板坯入库垛位决策问题模型,可以直接应用提出的Branch-and-Cut算法进行求解。数值实验验证了该问题基于图着色建模方法的有效性。5)以国内某大型钢铁企业的板坯库物流作业为背景,以上述板坯库吊机调度问题和板坯入库垛位决策问题模型和算法为内核,开发了板坯库物流优化决策支持系统。通过实际数据的应用验证,数值结果表明了所开发的模型及算法的性能优于流行的商业软件和手工编制作业方法。
[Abstract]:The problem of logistics time and spatial scheduling in manufacturing and logistics systems can be attributed to the integer programming problem..Branch-and-Cut algorithm is one of the most effective algorithms to solve the problem of integer programming. The basic idea is to use the framework of the branch and bound algorithm to increase the effectiveness of the leaf nodes in the branch and bound tree. The equation is used to dynamically elevate the lower bound (minimization problem) to reduce the number of branches of the branch and bound tree and improve the efficiency of the algorithm. As the integer programming problem is most of the NP- problem, it is of great significance to study the improvement of the Branch-and-Cut algorithm for the improvement of the scale and efficiency of the optimal solution of integer programming. Taking the typical crane scheduling problem in the time scheduling of logistics system as the background, the method of Branch-and-Cut algorithm is studied. The application of the method is studied with the factory crane scheduling as the background. Then, with the background of the classic graph coloring problem in the graph theory, the method of Branch-and-Cut calculation is studied, and the space of the logistics system is used. The main work of the paper and the research results are summarized as follows: 1) the scheduling problem of typical crane: for the M crane to complete the known N (MN) task, it is necessary to determine the assignment of the task on the crane and the order of execution on the distributed crane. The priority relation between the tasks of the crane and the avoidance of crossover and collision between the cranes, the shortest time needed to complete the complete task is made. The integer linear programming model of this problem is solved by Branch-and-Cut algorithm. An effective inequality based on the analysis of the problem characteristics is proposed, and an improved taboo based on the taboo is designed. The separation strategy of the search method is used for the discovery of effective inequalities. The results of the numerical experiment show the effectiveness of the proposed algorithm.2) the scheduling problem of the slab crane crane: the continuous (uninterrupted) outgoing operation of each work piece is defined as a task for the output of the N (MN) workpieces by the M crane. The distribution and execution order of the interruption and all tasks on the crane, in order to satisfy the completion order, avoid the intersect and collision between the hoists and the requirements of the service rules of the buffer stacks, make the completion time of all the tasks short. Row reconstruction. Based on the reconstruction model with tight lower bounds, the Branch-and-Cut algorithm is designed. In the implementation of the algorithm, a multi class effective inequality is proposed to improve the lower bounds of the problem. At the same time, the introduction of variable reduction technology is introduced to effectively reduce the search domain and improve the search efficiency. Numerical experiments based on industrial actual data prove that It is proposed that the algorithm can obtain the optimal solution of the scale of the industrial problem in a reasonable time, its performance is obviously superior to the commercial optimization solution software CPLEX, validates the validity of the proposed model and algorithm.3) the typical graph theory optimization problem - the graph coloring problem: a color for each vertex in a given graph is guaranteed to be arbitrarily connected. At the request of different colors, the least number of colors required by the decision is required. An integer linear programming model is established for the problem. The optimal solution of the Branch-and-Cut algorithm is designed. A variable fixed strategy is proposed to reduce the feasible domain and constructs an effective inequality based on dynamic programming. The effective inequalities of the erect set, based on the effective inequality of the regiment, effectively improve the convergence speed of the Branch-and-Cut algorithm. The experimental results of the Benchmark standard test data show the effectiveness of the proposed algorithm.4) based on the graph coloured slab entry position decision problem: the slab storage for the slab library needs decision storage Position position, in order to ensure that the slab is extracted in the order of out of the storehouse, does not produce the reverse stacking operation, which makes the occupying digits least. The problem is modeled by the graph coloring problem, and the storeboard is defined as the vertex, the slab is defined as the edge, and the stack of the same stacks is defined as the point in the same color. The minimum occupancy of the stacking number corresponds to the least used color number. The model of the slab storage position decision problem established by the graph coloring problem can be solved directly by the proposed Branch-and-Cut algorithm. The numerical experiment shows that the problem is based on the validity of the graph coloring modeling method.5) in a large steel enterprise in China. In the background of slab storehouse logistics operation, the logistics optimization decision support system of slab storehouse is developed based on the scheduling problem of slab hanger crane and the model and algorithm of slab storage staging decision problem. The application verification of actual data shows that the performance of the developed model and algorithm is superior to the popular commercial software and hand. The manufacturing method of the industrial editor.
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：F402;F252;TP301.6

【相似文献】