Research On Models And Algorithms For Job Shop Scheduling Problems With Limited Waiting Time

In the actual industrial environment,due to the instability of intermediate products,the processing waiting time between many operations are limited.If the subsequent operation cannot begin processing within the designated time frame,the quality of the product will be reduced,resulting in rework or scrap.Therefore,we consider the impact of limited waiting time constraints on job shop scheduling problem,and develop the scheduling problem models of the job shop,the flexible job shop and the multi-objective flexible job shop that with limited waiting time constraints.We propose corresponding solution algorithms based on genetic algorithm.The main research content and conclusions of this article are as follows.(1)For the job shop scheduling problem with limited waiting time,a mathematical model is established with the objective of minimizing the maximum completion time.A hybrid algorithm combining genetic algorithm and tabu search algorithm is proposed to solve the problem.Based on the analysis of the problem characteristics,a decoding algorithm based on operation conflict adjustment strategy is designed,and the quality of the solution is further improved by using the bidirectional shift timetabling and rescheduling scheme.The superiority of the algorithm is verified by using standard cases.The test cases applicable to this type of problem are designed based on standard examples and the simulation results show the effectiveness and superiority of the algorithm in solving this type of problem.(2)For the single-objective flexible job shop scheduling problem with limited waiting time,a mathematical model is established with the objective of minimizing the maximum completion time.Based on the genetic algorithm framework,a machine selection method is used to improve the quality of the initial population,and the search capability of the algorithm is improved by improving the genetic operations and iterative local search algorithm.The superiority of the algorithm is verified by using standard cases,and the correctness of the model and the superiority of the algorithm in solving this type of problem are verified by constructing examples.(3)For the multi-objective flexible job shop scheduling problem with limited waiting time,a mathematical model is established with the objectives of minimizing the maximum completion time,total tardiness and total machine load.For the characteristics of multi-objective problem,the Pareto dominated method is used to obtain the Pareto optimal solution set.Using the second-generation non-dominated genetic algorithm as the framework,the population diversity is improved by designing the population initialization method and improving the elite selection strategy.The local search capability of the algorithm is improved by using tabu search algorithm.The test cases applicable to this type of problem are designed based on standard examples,and the simulation results show the superiority of the algorithm in solving this type of problem.