Theoretical Model Of Ant Colony Optimization & Its Applications In Production Scheduling

The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the solution construction graph that the combinatorial optimization problem can be mapped on. Based on the solution construction graph, the unified framework of the ACO algorithm is presented.An iterative update procedure of the solutions distribution in the problem's probabilistic model is proposed, that will converge to the optimal solutions with probability one, then the minimum cross-entropy pheromone update rule is proposed to approximate the iterative update procedure by minimizing the Cross-Entropy distance and Monte-Carlo sampling. The global normalized ants-seed pheromone update rule is presented to ensure that the sum of the pheromone distributed over the construction graph is a constant, in addition, the normalized mechanism solves the problem of pheromone initialization and avoids the influence of the scale of the quality function of the solution. The local normalized ants-seed pheromone update rule for the matrix solution construction is presented to ensure that the sum of the pheromone distributed over a row of the nodes in the construction graph is a constant, and it can be proved that for the non-constrained matrix construction graph, the local normalized ants-seed pheromone update rule is a minimum cross-entropy pheromone update rule. As an example, the parallel machine scheduling problem is mapped on a non-constrained matrix construction graph, and a ACO algorithm is proposed to solve the parallel machine scheduling problem. Comparison with other best-performing algorithm, the algorithm we proposed is very effective.The finite deterministic Markov decision process corresponding to the solution construction procedure of ACO algorithm is illustrated in the terminology of reinforcement learning (RL) theory. The ACO algorithms are fitted into the framework of generalized policy iteration (GPI) in RL based on incomplete information of the Markov state. Furthermore, we show that the pheromone update in the ACS and Ant-Q algorithm is based on the MC methods or some formalistic combination of MC methods and TD methods. We propose a novel ACO algorithm, Ant(λ) algorithm, based on the eligibility trace, the algorithm unifies the TD method and MC method mathematically, and can make the delayed reinforcement can be back propagated in time.Several novel ACO algorithms are presented for Flowshop scheduling problem. There are: ACO_NORM algorithm which applies the local normalized ants-seedpheromone update rule for the matrix solution construction; The ACO_STAG algorithm which is characterized by the stagnation step out mechanism and the pheromone trail limit mechanism; the Ant-Q(λ) algorithm which is based on eligibility trace. A kind of heuristic information based on the Dannenbring approach is introduced in the procedure of solution construction. The experiment shows that the stagnation step out mechanism and the pheromone trail limit mechanism can help ants stepping out of stagnation and the heuristic information is very effective, in addition, the eligibility trace mechanism in Ant-Q(λ) algorithm can greatly improve the performance of algorithm based on solution construction graph in arc mode. The local search procedure based on several critical block based neighborhood structure is hybrid with ACO_STAG algorithm, comparisons with other well-performed algorithms on Taillard's benchmark problems show that the hybrid algorithm performs better.A completion time algorithm for the multiproduct batch scheduling problem in mixed intermediate storage (MIS) policy is proposed. The transfer time, sequence-dependent setup time of equipment, and the effect of double transferring are considered in the algorithm. Based on this completion time algorithm, the ACO_STAG and ACO_NORM algorithms are applied for the optimal scheduling of multiproduct batch processes. A modified Dannenbring heuristic is introduced in the procedure of solution construction. In addition, ACO algorithm is hybrid with local search to im...