Study On Manufactural Job Shop Scheduling And Algorithms

With economic of market development,the characteristics of multi-species, multi-process and small quantity has become the focal point of the market which manufactory racing to control.Therefore,manufacture enterprises should be asked to range sequences rationally,take advantage of resource efficiently,shorten time limit for a project and reduce the cost of producing.The research and application of effective production scheduling methods and optimization techniques are the key elements to implement modern manufacture and promote production efficiency.And people paid more attention to the Job Shop Problem(JSP)more and more.JSP belonging to NP-hard problem is the hardest solving problem in classic optimization problem.Genetic Algorithm(GA)is a global search algorithm by choosing,crossover and mutation operations to operate the population.Although it is a common algorithm, the single GA which is applied in real project can result in the problem of early convergence.To solve this matter and improve the ability of global search,GA and Immune Algorithm(IA)are combined together in this paper.Immune Genetic Algorithm(IGA)can use the feature information selectively and purposefully to maintain the diversity of individual and avoid early convergence,and to improve the convergence speed.Then it is developed and is used to solve Job Shop Problem.Firstly,I summarized the research background and significance of this paper.It contains that researching the status,traits and outstanding problems of mordern shop manufacturing.Then I studied the research status quo and development trends of GA and IA.Secondly,the theory of Job Shop Scheduling was studied detailedly.And its algorithm was discussed primarily.And then,the classical GA and IA,and their organic combination were researched and discussed.The paper researched the theory and design of the two algorithms.Some possible improving factors were argued.One of the most important parts in the paper was the combination of the two algorithms and its improving.I designed the IGA which is fit for the example of the paper. Finally,the application of improved IGA was researched.By testing Benchmarks instances,the results showed the new algorithm was satisfactory.IGA was applied into a real-world scheduling system of a manufacturing enterprise in Zhejiang Province to settle a simplified example.The result of this example was almost perfect and very quickly.