Study For Flexible Shop Scheduling Problem Based On Column Generation

The researches of flexible shop scheduling problems mostly focus on approximate algorithms,such as heuristic algorithms,artificial intelligence algorithms and so on.Especially for the flexible shop scheduling problem with no waiting constraints,due to the complexity of the problem,it is difficult to find an exact algorithm that can effectively solve in a shorter time.This paper introduces a method to solve the flexible flow shop scheduling model and mainly focuses on two types of flexible shop scheduling problems: flexible job shop,and flexible open shop.Based on the special nature of each type of problem,an exact algorithm based on column generation(CG)is designed,and this study has certain practical guidance for production.Mathematical description of the problem was established and a mixed integer programming model was established firstly.The flexible shop scheduling problem belongs to the complex large-scale scheduling problem,and it is NP-hard even for small-scale problems.Based on the idea of column generation algorithm,a set partition model for each type of shop scheduling is established,including a restricted master problem and a pricing subproblem.A special dynamic programming algorithm is designed to solve the price subproblem,and an improved branch-and-bound algorithm is used to find the integer optimal solution.For the flexible flow shop(FFS),the optimization strategy of the proportionate flow shop(PFS)problem is analyzed,in which the dynamic programming iteration process for solving price subproblems and the branch and bound strategy for solving optimal integer solutions are based on the problem itself,that is based on the completion time of the job(completion time).For flexible job shop(FJS)and flexible open shop(FOS),we consider a two-stage proportionate shop with no wait constraint.Due to the particularity of the problem,we use a job-pair based strategy to achieve no-wait constraints.This paper analyzes the strategy of implementing machine sequencing in the form of standard job pairs,and designs a CG-based JPGC_DB algorithm to solve such complex problems.When solving the pricing sub-problem,due to the existence of special attributes of the gap within the job,a dynamic programming method tailored to the problem is proposed.In order to solve the optimal integer solution with branch and bound algorithm,an improved branch strategy is designed.A series of random instances verify the effectiveness of the algorithm.In addition,based on the above algorithm design,the graphical user interface(GUI)design for the flexible shop scheduling problem is realized,making the algorithm more intuitive and easy to use.The biggest contribution of this research is to propose a precise algorithm based on column generation(CG)for solving flexible shop scheduling problems.The algorithm framework for specific research problems is designed.The dynamic programming-based algorithm is used to solve the sub-problems of generating columns in the column generation process.At the same time,the branch strategy for the problem background is proposed to solve the optimal integer solution.