The Optimization Algorithms Of Flexible Job Shop Scheduling Problem

Flexible job shop scheduling problem(FJSP), as a class of typically complex scheduling problem, has a strong application background with large solving complexity. Finding effiective methods to solve FJSP has attracted more and more attention. This dissertation mainly carries out research on the designs of artificial bee colony algorithm(ABC), gravitational search algorithm(GSA) and quantum-behaved particle swarm optimization(QPSO). Furthermore, the improved algorithms are also applied to solve FJSP. The primary research work and innovations of this dissertation is summarized as follows:(1) This dissertation studies the single objective flexible job shop problem in artificial bee colony(ABC). According to the power exploration and poor exploitation ability of ABC, this paper proposes a balanced bee colony with “fitness Euclidean-distance ratio” strategy(FER-ABC). This algorithm modifies the search equation based on “fitness Euclidean-distance ratio” and differential algorithm(DE). The FER strategy is useful for multi-optimization and the DE is beneficial to single- optimization. In order to exploit the advantages to full, a new search structure is proposed which will balance the exploitation and exploration. In addition, chaotic strategy is proposed in the initialization phase to improve the diversity of the swarm.(2) This dissertation studies the single objective flexible job shop problem in gravitational search algorithm(GSA). According to the strong exploitation and poor exploration abilities of GSA, a niching behavior based advanced GSA(NAGSA) is proposed. After analyzing the performance of GSA, NAGSA defines the mass affinity and euclidean-distance affinity for each particle, and then each particle’s affinity probability is calculated according to these two attributes, and replaces the original sorting mass method. The use of affinity probability and crowding niching behavior guides each particle to search in its neighboring field, thus NAGSA can make a balance between convergence rate and diversity maintaining. Besides, the value of kbest decreases according to exponential function, so that the convergence accuracy will be improved.(3) A study on pareto-ranking based quantum-behaved particle swarm optimization(QPSO) for multi-objective optimization problems is presented in this paper. During the iteration, an external repository is maintained to remember the non-dominated solutions, from which the global best position is chosen. The comparison between different elitist selection strategies(preference order, sigma value and random selection) is performed on two metrics. The results demonstrate that QPSO with preference order has comparative performance with sigma value according to different number of objectives. Finally, QPSO with sigma value is applied to solve multi-objective flexible job-shop scheduling problems. Experiments on several standard test functions and example modals show the validity of these proposed algorithms and superiority compared with other typical algorithms.