Research On Algorithm For Flexible Job-Shop Scheduling With Multi-objective

Scheduling problem has many characteristics, such as complexity, constrained and multi-objective. It belongs to combinatorial optimization problems. However, it is quite difficult to obtain an optimal solution to the general problem with traditional optimization approaches owing to the high computational complexity. The Job-shop Scheduling Problem (JSP) is an important branch of scheduling problem. In the traditional Job-shop scheduling problem, it assumes each job has a unique process. This hypothesis makes JSP out of touch with actual production process, and lack practicality. In the actual production process, an operation to be processed by any machine from a given set, jobs can choose a suitable route without change sequence of operations. The Multi-objective Flexible Job-shop Scheduling Problem (FJSP) incorporates all of the difficulties and complexities of its predecessor JSP and is more complex than JSP because of the addition need to determine the assignment of operations to machines. Optimization algorithm to solve this problem is mainly heuristic algorithm. Because a single algorithm has many defects and shortcomings, in recent years by the hybrid algorithm to solve the Multi-objective FJSP become a hotspot.Firstly, this paper reviews and summarizes the scheduling problem development, classification and performance evaluation index, the niche technology, immune genetic algorithm, tabu search algorithm and simulated annealing algorithm. Secondly, this paper improves the immune genetic algorithm, and puts forward a niche technology based on immune genetic algorithm. The algorithm adopts niche technology, Selecting reproduction, two-point crossover and adaptive mutation, which can effectively solve the simple genetic algorithm convergence slow and early maturity. At the same time, a tabu simulated annealing algorithm by combining tabu search algorithm with simulated annealing algorithm. This algorithm adopts tabu search algorithm roughly search to solve the determination of initial temperature and initial state in simulated annealing algorithm. At last, this paper propose an algorithm to settle the Multi-objective FJSP with integrated approaches:Multi-objective problem is converted into single objective; The improved GA is used to assign each operation on a machine and simulated annealing algorithm is applied during the stage of sorting the operations to solve the individual value of fitness.Experimental simulation shows that this algorithm is convergent fast, can effectively avoid the remaining local optima and obtain the global optimal solution. So, this algorithm is a feasible and efficient method for solving the multi-objective flexible Job-shop scheduling problem.Although the proposed algorithm is tested with three representative instances, a more comprehensive computational study should be made to test the efficiency of proposed solution technique. Furthermore, in Multi-objective FJSP research, the theoretical and experimental study on how to solve Multi-objective FJSP by improved and hybrid algorithm.