بهینه سازی کلونی مورچگان مبتنی بر دانش برای مشکلات زمانبندی تولید کارگاهی انعطاف پذیر

A Knowledge-Based Ant Colony Optimization (KBACO) algorithm is proposed in this paper for the Flexible Job Shop Scheduling Problem (FJSSP). KBACO algorithm provides an effective integration between Ant Colony Optimization (ACO) model and knowledge model. In the KBACO algorithm, knowledge model learns some available knowledge from the optimization of ACO, and then applies the existing knowledge to guide the current heuristic searching. The performance of KBACO was evaluated by a large range of benchmark instances taken from literature and some generated by ourselves. Final experimental results indicate that the proposed KBACO algorithm outperforms some current approaches in the quality of schedules.

Scheduling problems have a vital role in recent years due to the growing consumer demand for variety, reduced product life cycles, changing markets with global competition and rapid development of new technologies. The Job Shop Scheduling Problem (JSSP) is one of the most popular scheduling models existing in practice, which is among the hardest combinatorial optimization problems [1]. Many approaches, such as, Simulated Annealing (SA) [2], Tabu Search (TS) [3], Genetic Algorithm (GA) [4], Ant Colony Optimization (ACO) [5], Neural Network (NN) [6], Evolutionary Algorithm (EA) [7] and other heuristic approach [8], [9] and [10], have been successfully applied to JSSP. In order to match today's market requirements, manufacturing systems need not only automated and flexible machines, but also flexible scheduling systems. The Flexible Job Shop Scheduling Problem extends JSSP by assuming that, for each given operation, it can be processed by any machine from a given set. Bruker and Schlie [11] were among the first to address this problem. The difficulties of FJSSP can be summarized as follows. (1) Assignment of an operation to an appropriate machine; (2) Sequencing the operations on each machine; (3) A job can visit a machine more than once (called recirculation). These three features significantly increase the complexity of finding even approximately optimal solutions. Although EA has been applied to solve numerous applications, but there have two disadvantages for solving combinational optimization problems by a canonical EA. (1) A canonical EA is a ‘generation-evaluation’ type of searching technique, which only uses fitness value or objective value to guide the evolutionary search [12]. (2) The optimization results obtained by the canonical EA are still limited due to the reliance on randomized natural selection and recombination [13]. For improving the performance of EA, several researches integrated some optimization strategies into the EA [14] and [15]. Also, the study of interaction between evolution and learning for solving optimization problems has been attracting much attention [16], [17], [18] and [19]. The diversity of these approaches has motivated our pursuit for a uniform framework called Knowledge-Based Heuristic Searching Architecture (KBHSA), which integrates knowledge model and heuristic searching model to search an optimal solution. We demonstrate the performance of this architecture in the instantiation of the Knowledge-Based Ant Colony Optimization (KBACO) which is applied to common benchmark problems. Experimental results show that KBACO algorithm outperforms previous approaches for solving the FJSSP. The remainder of this paper is organized as follows. Section 2 reviews some recent works related to the FJSSP. Section 3 describes the proposed architecture (KBHSA) and its instantiation (KBACO). Section 4 presents and analyzes the performance of KBACO when applied to solve common benchmarks in literature and others generated by ourselves. Finally, Section 5 gives some concluding remarks and directions for future work.

The contribution of this paper can be summarized as follows. It proposes a KBACO algorithm for the FJSSP. The performance of KBACO was largely improved by integrating the ACO model with knowledge model. In KBACO, some available knowledge was learned from the optimization of ACO by the knowledge model, at the same time, the existing knowledge was applied to guide the current heuristic searching of ACO. Final experimental results indicate that the proposed KBACO algorithm outperforms some published methods in the quality of schedules. In the proposed KBACO, the knowledge model is simply a memory keeping good features from previous iteration. For this reason, we intend to focus on enhancing KBACO via explorations in machine learning so as to improve the efficiency of the knowledge model. Also, the extension to multi-objective FJSSP will be investigated in the near future.