Research Of Flexible Job-Shop Scheduling Problem Based On Improved Ant Colony Algorithm

Job-shop scheduling problem has aroused general interests in the past years, an appropriate scheduling scheme allows the enterprise respond quickly to the market situation changes, reduce the non-cutting time, improve the product efficiency, in the context of an increasingly competitive market. Flexible job-shop scheduling problem is a more complex combination optimization problems that developed on the classical jib-shop problem, the processes can be worked on multiple machines, the machining time is also different, it is more difficult to solve, has been proved the worst NP-hard problem. The flexible job-shop problem is more in line with the actual workshop production, so the study of flexible job-shop problem has become a hot research spot in the academic and technical fields in recent years.This paper summarize the study current situation of job-shop scheduling problem and flexible job-shop scheduling problem, considering the actual job-shop production situation and the principles of ant colony algorithm, proposed an improved ant colony algorithm to solve the flexible job-shop static scheduling problem, to minimize the makespan, the main work is as follows:According to the actual situation of workshop production and the basic theory of flexible job-shop scheduling problem, combining the relevant principles of ant colony algorithm, determine the study objective of this paper:flexible job-shop static scheduling problem, in order to minimize the makespan, choose ant colony algorithm to be the tool, established an job-shop scheduling problem disjunctive graph model based on the traveling salesman problem.To solving the algorithm’s disadvantage of fall into local optimal solution and slow convergence speed, this paper proposed two improvements:use local and global mix updating tactics to update the pheromone; in the transition rule, set the fixed q0 to a function changing with the iterate time. Determine the key parameters of the algorithm by simulation experiments, test the improved algorithm and the determinedparameters on the MATLAB software.Design the steps of the colony algorithm when solving the flexible job-shop problem, including the key modules of machine selection and handle the process constraints, the specific procedure is given, demonstrate the way of improved ant colony algorithm solving flexible job-shop problem on a benchmark. Use the algorithm of this paper to solve the scheduling problem of Z workshop in Y enterprise, the maximum completion time has saved 504 seconds, verified the feasibility of using the improved ant colony algorithm to solve the flexible job-shop problems.