Research On Flexible Job-Shop Scheduling Problem With Transportation And Setup Times Based On Evolutionary Algorithms

Flexible job shop scheduling(FJSP)is an important combinatorial optimization problem,which is in line with the production mode of modern discrete manufacturing system.In the actual production process,in addition to the processing time that is generated when the job is processed directly on the machine should be considered,there are also a large number of transportation and setup times in the job handling,machine tool mold change,tool change and other auxiliary activities,which seriously affect the production cycle.Ignoring these time factors will lead to a great reduction in the punctuality and feasibility of scheduling scheme.Therefore,an FJSP with transportation and setup times(FJSP＿T/S)is studied from theoretical research to practical application in this paper.The main contents of this paper are summarized as follows:(1)Single-objective FJSP＿T/S research.For the single-objective FJSP＿T/S,a mixed integer programming model is established,which contains the decision variables,objective functions and constraints of the problem.According to the characteristic that a operation with multiple optional processing machines,a machine neighborhood structure is designed to assist algorithm solving.For the established model,an improved memetic algorithm is proposed,in which the local search operator is combined with a hybrid simulated annealing framework and uses the machine neighborhood structure perturbation to search for neighborhood solutions.Finally,many experiments are performed on 28 benchmark instances,and the effectiveness of the improved algorithm was verified by the comparison results with other algorithms.(2)Multi-objective FJSP＿T/S research.In this paper,a network graph model is established to describe the scheduling scheme of the multi-objective FJSP＿T/S.According to the feasible insertion theorems derived from the model constraint relationships,an insertion neighborhood structure with 4 move types is designed for different optimization objectives.In the term of solving,a hybrid multi-objective evolutionary algorithm is proposed to balance the exploration and exploitation of the algorithm.The algorithm uses a tabu search operator with the insertion neighborhood structure to improve the local search accuracy,and a reference-point based non-dominated sorting selection to guide the population to the Pareto-optimal front and keep the diversity of the population.Through three sets of experiments of 28 benchmark instances,the effect of local operators and the overall performance of the algorithm are compared and analyzed.The results show that the proposed algorithm is effective in solving multi-objective FJSP＿T/S.(3)Development of the prototype system of a job shop scheduling software.Combining with above researches,based on MATLAB,the prototype system of a job shop scheduling software with transportation,setup and delivery times is designed and developed.The software includes a graphical user interface,which can easily and quickly import processing information,rapid and effective formulation of detailed production plans.In short,this paper provides some technical reference and inspiration for manufacturing enterprises to realize intelligent production scheduling automation.In short,the software can provide some technical reference and inspiration for manufacturing enterprises to realize the automation and intelligentization of production scheduling.