A gravitational search algorithm for flow shop scheduling

Yanmei Hu

Caai Transactions on Intelligent Systems · 2010 · 11 citations · 0 references

Concepts

Abstract

An improved gravitational search algorithm(IGSA) was proposed to solve the flow shop scheduling problem with the objective of minimizing production time.First,to make a GSA suitable for permutation of the flow shop scheduling problem(PFSSP),a new largest-rank-rule based on a random key was introduced to convert the continuous position of the GSA into the discrete job permutation so that the GSA could be used for solving PFSSP.Second,a new boundary mutation was proposed.This operation stopped the agents which have mutations as a result of using the above method from gathering at the border.They were distributed at a feasible distance from the boundary.This improvement also improved the population diversity.Third,by combining the communicating operator and inserting operator,the new local search was designed to help the algorithm escape from the local minimum.Finally,the convergence of the iterative algorithm and its complexities in time and space were proven.Additionally,simulations and comparisons based on PFSSP benchmarks were carried out,which show that the proposed algorithm is both effective and efficient.