A Research On Branch-and-Cut Algorithm And Application In Time-Space Logistics Scheduling

Many Time-Space Logistics Scheduling problems, that arising from manufacturing and logistics systems, can be formulated as integer programming (IP) model. As one of the most efficient algorithm for solving IP, Branch-and-Cut algorithm is designed based on the framework of Branch-and-Bound algorithm. Besides, valid inequalities are added to the node of the Branch-and-Bound tree dynamically to improve lower bound (minimizing problem) and decrease tree size, therefore enhance algorithm efficiency. As most of IPs are NP-hard problems, it is extremely important to study Branch-and-Cut algorithm to enlarge the size of the IPs that it can solve and also improve algorithm efficiency.In this dissertation, Branch-and-Cut algorithm and its application are studied based on two kinds of background:i) taking classical crane scheduling problem of logistics system as background, a research on its Branch-and-Cut algorithm is investigated first. Then, an application research on solving factory crane scheduling problem is conducted accordingly. ?) taking graph coloring problem as background, a Branch-and-Cut algorithm is proposed to solve it. Then, The application of Branch-and-Cut algorithm on solving the incoming slab stacking decision problem is researched, by formulating the incoming slab stacking decision problem as a graph coloring problem. The main contents of dissertation are summarized as follows:1) Classical crane scheduling problem:given M cranes and N known tasks, the problem is to assign N tasks to M cranes and sequence the assigned tasks on each crane with the objective of minimizing the completion time of all tasks. When making decision, the requirement of crane collision avoidance and tasks precedence must be satisfied. The problem is formulated as an integer linear programing (ILP) model. Branch-and-Cut algorithm is designed to solve it. In the algorithm, based on the analysis of problem properties, structure-oriented valid inequalities are proposed, and an improved separation heuristics designed based on tabu search is performed to explore the proposed valid inequalities. Computational experiment results approved the effectiveness of the algorithm.2) Factory crane scheduling problem:given M cranes and N known delivery jobs, a crane moving a job from one location directly to the exit of the yard is defined as a delivery task. The problem is to decide whether the delivery process of a job should be interrupted, assign all of the resulting tasks to cranes, and sequence tasks on each crane with the objective of minimizing the completion time of all tasks. During decision making process, the requirement of jobs delivered sequence, crane collision avoidance, and buffer stack rule for preemptive jobs must be considered. The problem is formulated as an integer programming model. To obtain a tight lower bound, the problem is reformulated based on the problem properties analysis. Branch-and-Cut algorithm is implemented based on the reformulation. In the algorithm, several kinds of valid inequalities are proposed to lift lower bound, variable reduction technique is adopted to reduce the search region, and hence to improve algorithm efficiency. By observing the results of computational experiment on real data collected from slab yard, we can see that:i) the proposed algorithm based on the reformulation model can solve the actual size problem instances to optimality in a reasonable time, and ii) the proposed algorithm takes much less time than CPLEX for the problems that are solved to optimality, and its performance outperforms CPLEX.3) Graph coloring problem which is a kind of classical graph theory problem:given a graph, the problem is to assign a color to each vertex considering the constraint that any pair of connected nodes cannot be covered with the same color. The objective is to minimize the number of colors needed. For the ILP model, a Branch-and-Cut algorithm is proposed to solve it to optimality. Variable reduction technique is proposed to reduce the feasible region. In addition, a series of dynamic programming-based valid inequalities, independent set-based valid inequalities, and clique-based valid inequalities are added into the algorithm to improve its convergence rate. Computational experiment on benchmark instances demonstrated the efficiency of the proposed algorithm.4) Incoming slab stacking decision problem based on graph coloring formulation: given a sequence of incoming slabs, the problem is to decide the stacking locations of each incoming slab. During the retrieval process, it must be satisfied that no shuffles occur if slabs are delivered following the given sequence. The objective is to minimize the number of stacks that need to be taken by all incoming slabs. The problem can be represented by a graph coloring based model as follows. We create a vertex for each incoming slab, and create an edge for each pair of incoming slabs that have the relationship of coming and retrieving sequences. Then, slabs that are assigned to the same stack are viewed as the nodes that are covered with the same color, and hence the objective of minimizing the number of used stacks is equivalent to minimizing the number of used colors. Based on above, the Branch-and-Cut algorithm that is used to solve graph coloring problem can be directly used for solving incoming slab stacking decision problem by formulating the incoming slab stacking decision problem as graph coloring problem. Computational experiment shows the efficiency of graph coloring based formulation.5) Taking the logistics operations of slab yard in some large-scale domestic steel-iron enterprise as background, embedding above proposed models and algorithms for factory crane scheduling problem and incoming slab stacking decision problem, a decision support system is designed and developed. Computational experiment results demonstrated the performance of the proposed algorithm outperforms manual planning approach and CPLEX IP solver.