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

Flexible job shop scheduling problem (FJSP) is an extension of the traditional job shop scheduling problem (JSP).It is assumed that a process can be processed on multiple machines, and it not only needs to determine the processing sequence of the operations, but also allocate the machine to each operation, however, FJSP is more suitable for the actual production environment. Despite FJSP can reduce machine constraints, but it increases the uncertainty of the machine, expand the search range of feasible solutions, it is a kind of more complex NP-hard problem, therefore,the research on this problem has important theoretical significance and application value. This research is to focus on FJSP, and the main work is as follows:First of all, the research status of FJSP at home and abroad is reviewed, and the basic ant colony optimization is analyzed to solve the problem of flexible job shop scheduling problem, and then the research ideas of this paper is put forward.Secondly, the multi-objective scheduling model of flexible job shop scheduling problem is constructed by considering the production cost, delivery time, completion time and so on.Thirdly, an improved ant colony optimization is proposed to solve the FJSP. Firstly, the improved ant colony optimization is applied to solve the static and dynamic flexible job shop scheduling problem. According to the characteristics of FJSP, a new machine selection strategy is proposed in order to expand the space of machine selection. An improved ant colony optimization is proposed in this paper, and the main improvements are shown in the following aspects:(1) An initialization mechanism of uniform distribution of initial position of the ants is proposed, and it is unnecessary for the ants to follow the pheromone guiding mechanism to choose the path in the initial stage, but the pheromone is allowed to guide the way for finding the optimal path only when the pheromone is more than a certain value; (2) A new node selection method which combining priori knowledge, probability search and random search is proposed, meanwhile the unreasonable paths under transition probability are excluded; (3) The mode of the pheromone update is improved. The local optimal state of the ant colony optimization is broken by destroying mandatory the pheromone on the path when the ant colony optimization fall into local optimal. Meanwhile, the pheromone is initialized when the amount of pheromone on a certain path exceeds the total 90% pheromone of all paths; (4) In the process of building the solution, when the solution searched by ants is greater than the current global optimal solution, then the ant will exit the travel early. These improvements can further accelerate the convergence rate and improve the global search ability. Several simulation examples are carried out, and the results were compared with other algorithms. The results prove the effectiveness and feasibility the of our proposed improved ant colony optimization.Finally, According to the production needs of enterprises, the platform of flexible job shop scheduling system is developed.