An improved particle swarm optimisation with a linearly decreasing disturbance term for flow shop scheduling with limited buffers

Abstract

The flow shop scheduling problem with limited buffers is a typical combinational optimisation problem that is NP-hard. In this article, an improved particle swarm optimisation with a linearly decreasing disturbance term (LDPSO) is presented for permutation flow shop scheduling with limited buffers between consecutive machines to minimise the maximum completion time (i.e. the makespan). A linearly decreasing disturbance term was added to the velocity, updating formula of the standard particle swarm optimisation algorithm. The decision probability of the linearly decreasing disturbance term was used to control the utilisation of the global exploration operation and the local exploitation search based on problem-specific information so as to prevent premature convergence and concentrate computing efforts on promising neighbour solutions. Theoretical analysis based on previous studies showed that the improved algorithm converged to the global optimum at a probability of 1. The ranked-order-value encoded method transferred the continuous particle position of the LDPSO to the order sequence. Furthermore, the neighbour search strategy based on block guaranteed that the entire order sequence could be searched. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the LDPSO. The effects of buffer size and decision probability on optimisation performance are discussed in this article.

Keywords:

• flow shop scheduling
• limited buffers
• particle swarm optimisation
• premature convergence
• linearly decreasing disturbance term

Acknowledgements

This work was financially supported by the National Natural Science Foundation of China under grant numbers 61064011. It was also supported by scientific research funds from Gansu University, the General and Special Program of the Postdoctoral Science Foundation of China, the Science Foundation for Excellent Youth Scholars of Lanzhou University of Technology under grant numbers 1114ZTC139, 2012M521802, 2013T60889 and 1014ZCX017 respectively.