Research On Job Shop Scheduling Problem Based On Improved Genetic Algorithm

Manufacturing industry is the foundation of national economy,and scheduling is the key to achieve high efficiency,flexibility and reliability of manufacturing production.The research shows that 95%of the total time consumed in the manufacturing process is in the non-cutting process,and the scheduling technology in the manufacturing process directly affects the manufacturing cost,efficiency and benefit,which has very important research and practical significance.Therefore,the static,dynamic and flexible job shop scheduling problems are studied successively in this paper.First of all,the problem is described and modeled.Then,the corresponding scheduling strategy and improved genetic algorithm are proposed.Finally,the program is realized by MATLAB software and the simulation experiment is carried out by using benchmark cases.By analyzing the results obtained,the feasibility and effectiveness of the improved algorithm are proved.On the basis of the previous research,the corresponding job shop scheduling management system is designed and used to management personnel information and generate the scheduling scheme by enterprise workshop managers.The main research contents of this paper are as follows:(1)The static job shop scheduling problem is described and the model of problem is established.Genetic algorithm is improved by using process-based coding method,elite solution retention selection strategy,cross-operation of single-point crossover and sequential crossover,exchange mutation operation,and adaptive adjustment crossover and mutation probability to solve FT06 benchmark case.The maximum completion time is 55s,which has reached the currently known optimal solution.The third generation gets the optimal solution,and the search efficiency of improved genetic algorithm is higher than the traditional.(2)The dynamic job shop scheduling is described and the model of problem is established.Event-driven priority mixed rescheduling strategy based on rolling window technology was proposed,and the problem was solved by improved genetic algorithm.The algorithm involves process-based coding method,elite solution retention and roulette combination method,and local search algorithm.First,the benchmark cases of FT06,FT10 and LAO 1-08 are solved,and the results were compared with other algorithms to verify the effectiveness and superiority of the improved algorithm.Secondly,for FT06 benchmark case,the rescheduling cycle is set to 30s,the completion time of the obtained scheduling scheme is the known optimal solution 55s and the stability of the shop processing is improved.Subsequently,the result of rescheduling is reduced according to the occurrence of dynamic events such as machine failure,raw material delay arrival and assembly delay,the processing time is at least 4s,which can save up to 15 s.At last,the result of rescheduling is reduced about 21s for the urgent insertion event.(3)The flexible job shop scheduling is described and the model of problem is established.Genetic algorithm is improved by fusing particle swarm optimization,and the improvement strategy of eliminate the same individuals and further evolution of chromosomes are proposed.The problem is simulated and solved by MK01-10 benchmark case,and the obtained result can reach or close to the known optimal solution which verifies the superior solution ability of the improved algorithm.(4)The theory is applied to practice based on the above research,and the GUI of MATLAB is used to design and exploit the job shop scheduling management system which integrate information management and job shop scheduling.There is important practical significance to integrate the research content and improved algorithm into the system,therefore the workshop managers can use the system to manage the information of workshop,personnel,process and inventory,and conduct different kinds of workshop scheduling and obtain corresponding scheduling schemes.