A Branch And Bound Algorithm For Flow Shop Scheduling Problem

Flow shop scheduling is a simplified model of the actual assembly line production process,the fields include port ship,logistics transmission,workshop production and so on.Reasonable scheduling can optimize the allocation of limited resources,improve production efficiency and reduce transaction risk etc.Based on the existing flow shop research,this paper studies the scheduling problem of minimizing the total late work under the environment of multiple flow machines,and designes a branch and bound algorithm to solve it.Flow shop refers for each task,it needs to be processed on each machine according to the "FIFO" principle.Although the approximation algorithm can solve the solution of machines and tasks are large,but can not get the optimal solution.The branch and bound algorithm designed in this thesis can ensure that the task scale is as large as possible,and obtain the exact solution.According to the problem studied,the algorithm first builds a search tree.In order to avoid the high complexity of operation caused by all enumeration,the algorithm uses upper and lower bound pruning to delete useless branches.According to the characteristics of the search tree,the global upper bound,upper bound and local lower bound are set to improve the pruning efficiency.For the global upper bound,genetic algorithm is used to get the initial solution,chromosome coding is used to generate the next generation through selection,crossover and mutation,and finally the algorithm is terminated by limiting the number of iterations;DP and PMTN technologies are used to calculate the lower bound,and DP and PMTN algorithms are run for several times to solve the optimal sequence of minimum delay loss in the case of single machine environment with common delivery time,and finally the final lower bound MIX is obtained by combining the results of the two lower bounds,which improves the pruning effect of the branch and bound algorithm and makes the pruning process more efficient.At the same time,the comparison between the initial solution obtained by genetic algorithm and the result obtained by heuristic rule proves the improvement ability of genetic algorithm to the initial solution.Finally,the feasibility and effectiveness of the exact algorithm for solving the problem are demonstrated by experiments.The experimental data shows that through the performance of B&B＿MIX to delete the search tree node is better than that of branch and bound tree and any one of B&B＿MDP、B&B＿PMTN as the lower bound of the tree.In addition,on the improvement of the initial solution,the genetic algorithm on LPT and TSPT is weak,which shows that the two rules are better as the initial solution of the problem,and can further solve large-scale problems.