Similarity Based Ant-colony Algorithm for Permutation Flowshop Scheduling Problems with Total Flowtime Minimization

摘要

In the paper, a similarity based ant-colony algorithm (SACO) is proposed for the permutation flowshop scheduling problems with total flowtime minimization, which is known as NP-hard. By applying the space mapping method which is testified to be reasonable, it is proved theoretically that the deposit factor ρ has hardly impact on the ACO evolutionary availability, and ρ = 0.5 is reasonable for the ACO. Similarity is defined to discover the promising sequence for solution improvement. A new solution construction method is proposed, which is stated to be better than that of another very effective ant-colony algorithm. Experimental results show that SACO outperforms the other compared seven algorithms, including three rather recent effective algorithms and four famous ant-colony algorithms. The similarity indeed helps the SACO to find the promising sequence for solution improvement, which makes the SACO be effective.