Solving Permutation Flow Shop Problem By Ant Algorithms

The Permutation Flow Shop Problem is classical in the shop scheduling theory. It has both theoretical and real-life meanings.Some NP-hard problems with permutation property can be reduced to this problem, which means that if we can effectively solve the permutation flow shop problem,then we already have the tool to deal with some other permutation ones.In real-life settings,various industrial problems can be modeled into the permutation flow shop problem,such as in VLSI fabrication area etc.Due to the complexity of the problem, we utilize the ant algorithm to solve it. The success of its application to Tsp encourages us to expand its functional domain. In this paper, with respect to solution quality and computation time separately, we designed some original schemes and made some improvement thoughts.The research thread of this thesis is as follows:At first,the general structure of the ant algorithm for permutation flow shop problem is presented.To the solution quality end,a new path construction method is proposed,in which an ant select two jobs at each step when constructing a full path;A new local heurist information is proposed which adopts the concept of coordination from one job to another. We gather these schemes together to form a new ant algorithm. Through experiments,we found it an effective one.To the computation time end,a new quick-sort-like path construction method is proposed,which have smaller computation complexity;A branch-cutting scheme stepping from the characters of critical path and critical block is utilized;Parallel computing is adopted to reduce computational time.We examined the proposed mechanisms through computation experiments.