Benders Decomposition Algorithm For Coal Supply Chain Equipment Maintenance Scheduling Decision Problem

Coal is the basic energy source in China.During the first 10 years of the 21 th century,the coal industry is over invested,resulting in excess production capacity and fierce homogenization competition.Equipment maintenance will cause production interruption.Boland N et al point out that the production of the coal system is interrupted by equipment maintenance,resulting in an output drop of up to 15%.What's more,due to equipment failure correlation,reasonably scheduling equipment maintenance is an important means to reduce the interruption loss of the system.The network commodity flow model is usually used to optimize the transport of bulk cargos and containers.In this paper,the capacity of the network arc is determined by the working efficiency of the corresponding equipment.When the equipment is being maintained,the corresponding arc is interrupted;in the preventive maintenance mode,the equipment has a maintenance window.Under the background of the actual scheduling of coal port supply network equipment maintenance plan,this dissertation presents the Maximum Total Flow with Flexible Arc Outages model.The coal transportation and operation at port are formulated as a time-space network,and maintenance jobs associated with arcs must be performed in their specified time windows with a process duration.Once the job gets started,it cannot be preempted,and the associated arc is unavailable during this maintenance period.Constraints for this scheduling problem are obtained according to the arc outage policy,flow balance policy at internal nodes and the traffic restriction policy.With the goal of maximizing the throughput in the planned time horizon,this dissertation attempts to find an optimal maintenance schedule.The formulated problem is a mixture of maximum flow and scheduling problem and is strong NP hard in nature.With regard to the characteristics of the model,Benders decomposition algorithm multiplied with Local branching strategy is utilized to solve the problem.Through standard data test,it is proved that the modified algorithm shows better performance.Meantime,considering the actual situation and adding maintenance resource constraints,the model is extended.The main research work and results of this paper are as follows:(1)In view of the planning situation of the facilities and equipment maintenance of coal supply chain system,a comprehensive analysis of the existing problems and the insufficiency of the research is given.This paper points out the influence on the total throughput of the system caused by the maintenance planning,and the importance of maintenance scheduling is further clarified.Then,it uses the model based on dynamic network flow to study the actual problem.At the same time,combining with the practice,considering the maintenance of resource constraints,the application scope of the model is enriched.(2)Benders decomposition method is utilized to decompose the problem into a master problem with scheduling element and a maximum flow characterized sub-problem.The pre-flow algorithm is utilized to solve the maximum sub-problem.Local branching is used to solve the master problem,quickly updating the incumbent solution,producing high quality solutions at early stages of the computation.There are few operations research algorithms for equipment maintenance,and there are not many research pages for solving optimization problems using decomposition algorithms.The Benders decomposition algorithm designed in this paper is an innovation point.And combining the characteristics of the Benders decomposition algorithm,the idea of using the pre-flow algorithm and the Local branching strategy to modify the algorithm is also an innovation point.(3)Using Python language to code the decomposition algorithm.Gurobi optimization solver is called,as a benchmark for comparison,to carry out the experiments with standard test data.The performance of Benders decomposition algorithm multiplied with Local branching strategy is tested.The results show that Benders decomposition algorithm multiplied with Local branching strategy performs better in all kinds of numerical experiments,especially in large scale network.