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

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.