The Design And Implementation Of Job Shop Scheduling System Based On Genetic Algorithm And Nested Partition Algorithm

With the development of Discrete Manufacturing Industry,customer requirement has become increasingly personalized,how to formulate a precise production plan quickly according to the customer's individual needs has become a problem which the traditional manufacturing enterprises has to deal with.The key of improving production efficiency is making full use of machines and employees,especially,is how to schedule the processing order of products.And the efficiency of machine depends on the processing order of products.This paper applys Genetic algorithm,Nested Partition algorithm and improving Nested Partition algorithm to production scheduling.For the characteristics of production scheduling,every schedule and every gene is regarded as a chromosome and one kind of product,respectively.The position of gene on the chromosome represents the processing sequence of products.The objective function is the total time of producing the whole products.The reciprocal of the objective function is set as the chromosome's fitness.This paper designs the encoding,selection,crossover and variation of Genetic algorithm.Based on Nested Partition algorithm,this paper designs partitions,sampling,selecting area and backtracking strategies and partitions the products according to the full permutation of the products' serial numbers.The processing time of products serves as the measurement.The most likely domains and the group domains are selected according to the partitioning area.The backtracking strategies ensure the backtracking depth in order to obtain better solutions according to the depth of the current optimal solution.This paper analyses the functional requirements,data requirements of production scheduling system.The spring MVC system framework is used on production scheduling system.And the algorithms are released as web service based on SOA framework.The paper also designs the database and tests the system with the data from wood-working factory.The results show that Genetic algorithm is better than the other algorithms when the number of products needed scheduling is less than seven.But Nested algorithm and improved Nested algorithm has a better performance when the number of products needed scheduling is more than seven.In this case,the performance of Genetic algorithm declines and the calculation takes more time.Among the results,the improved Nested Partition algorithm is better than Nested Partition.But the improved Nested Partitionalgorithm takes more time to calculate.Scheduler can select the appropriate scheduling algorithm according to the number of jobs needed scheduling.