Font Size: a A A

The Research And Application Of Shop Scheduling Problem Based On Genetic Algorithm

Posted on:2014-01-16Degree:MasterType:Thesis
Country:ChinaCandidate:Z L YuanFull Text:PDF
GTID:2232330398966287Subject:Mechanical Manufacturing and Automation
Abstract/Summary:PDF Full Text Request
Job Shop Problem (JSP) is a typical NP-hard problem, it is of great practical significance tothe further study of the resource scheduling which has become a hot research today. As anintelligent optimization method for random search, Genetic Algorithm (GA) has been widely usedin solving JSP. In the solution of JSP, GA showed strong robustness. But the genetic parameters(especially the crossover rate and mutation rate) affect the optimization performance of GA greatly,incorrect parameters setting will often make the optimization results of GA discount. On the basisof improving standard genetic algorithm, the paper did algorithm design on four types of job shopscheduling problem. Comparing the optimization effect of algorithm through the example, weverified the validity and superiority of the improved GA to solve the job shop scheduling problem.This paper did a lot of research and analysis on the genetic algorithm at first, and we foundstandard GA in solving shop scheduling problem often fall into local optimal, low searchefficiency and resulting in an illegal solution. In view of this situation, the paper proposed amodified GA which combines heuristic rules and other methods, makes the generated initialindividual distributing in the solution space of the problem as much as possible, it also ensures thediversity of Solutions. Combining the characteristics of resource scheduling problem, the paperdesigns unique crossover and mutation, ensure the feasibility of solutions. By comparing the twoalgorithms, we found the improved GA can not only avoid the local optimum and guarantee thelocal search speed, but also improve the optimal rate and find the global optimal solution.On the basis of using the improved GA, the paper gave different algorithm implementationsfor four categories of job-shop scheduling. And the process of the realization of the algorithm areadjusted and improved reasonably. Then through scheduling three kind of shop scheduling model,the algorithm shows good results.Finally, we developed a shop optimization scheduling system which applied in the actualproduction and introduced the functions and operation of each module. Applying the system in theactual production and taking the parts processing as the object in an automobile plant to schedule, we got a good result of the scheduling. Lastly, this paper looked ahead to the next work.
Keywords/Search Tags:resources scheduling, Genetic Algorithm, Crossover operator, Mutationoperator, Flow-Shop scheduling, Job-Shop scheduling, Flexible Job Shop SchedulingProblems with Dual-resource
PDF Full Text Request
Related items