Font Size: a A A

Research On Job Shop Scheduling Problem Based On Heuristic Algorithm

Posted on:2020-08-03Degree:MasterType:Thesis
Country:ChinaCandidate:Z L FengFull Text:PDF
GTID:2392330605469368Subject:Software engineering
Abstract/Summary:PDF Full Text Request
Job-Shop Scheduling problem is common in supply chain management and operations,and it is also widely used in software development plans,computer system control,machine port scheduling,and production planning.Scheduling problems are in the existence of the situation where the jobs that must be scheduled by scarce resources.Therefore,Job-Shop Scheduling problem as a standard NP-hard problem is also be considered as one of the most challenging scheduling issues.Scheduling problem,especial the job-shop scheduling problem is at the heart of the important research content and operational management issues of integrated manufacturing technology.In this paper,based on the job shop scheduling problem with the shortest makespan,the branch and bound method is improved and applied.At the same time,a hybrid genetic algorithm based on processing demand similarity and an adaptive ant colony algorithm based on online adjustment are proposed and designed.The method is applied to solve the scheduling problem under the AGVs transportation constraints,and the specific research contents are as follows.Firstly,on the premise of known activity scheduling sequence,a calculation method of when the processing time is beginning and when will the processing end is designed,and the search efficiency of branch-and-bound method is improved by pruning the search tree with additional constraints.The comparative experiments of three different angles,it is proved that the search speed of the improved algorithm is increased by 45.39%,and the optimization of the optimal solution for large-scale problems is improved by 3.40%.The improved method provides the theoretical optimum value for the performance verification of the latter algorithm.Second,aiming at the phenomenon of maximum makespan may increased due to frequent switching of workpieces in the job-shop,the hybrid genetic algorithm based on the similarity of processing requirements in the scene with frequent job switching is improved,and the workpieces are grouped according to the processing requirements.The grouping results are added to the initial population generated by the hybrid genetic algorithm,and the selection operator of the hybrid genetic algorithm is improved.The experimental results show that the genetic simulated annealing algorithm after clustering has a faster search speed and reduces the risk of the algorithm converge early to local optimum.Thirdly,an adaptive ant colony algorithm based on online adjustment is proposed.According to the dispersion degree of the previous generation similar solution,it is judged whether the algorithm is trapped in the local optimal risk,correspondingly adjusts the ant transfer state,and adopts different pheromone matrix update strategies.The update of the feasible solution is adjusted,and the reliability of the algorithm is proved by experiments.At last,the sensitivity analysis of the improved two algorithms is carried out,and the influence of different parameters on the improved algorithm is demonstrated.The robustness of the two algorithms is compared.According to the classical benchmark test,the two improved algorithms are compared and tested.The performance difference under different scale problems;finally,the algorithm is applied to the job shop scheduling problem in the multi-AGVs transportation constraint environment,which proves the scalability of the algorithm and has a flexible application range.
Keywords/Search Tags:job-shop scheduling problem, heuristic search algorithm, genetic algorithm, ant colony algorithm, AGV
PDF Full Text Request
Related items