A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes

This paper presents a modified particle swarm optimization (MPSO) algorithm to minimize the maximum lateness for the single batch-processing machine problem with non-identical job sizes and release dates. The MPSO algorithm incorporated a diversification and a local search strategy into a basic particle swarm optimization algorithm. This incorporation enables the proposed algorithm to have a good balance between exploration and exploitation that yields high search efficiency. Additionally, a dynamic programming method is proposed to calculate a relevant value for each particle. The MPSO algorithm was tested in problems from the literature without release dates and newly generated problems with release dates. Computational results show the advantages of combining the diversification strategy, and local search methods. The performance of the proposed MPSO is competitive. For the problems without release dates, the MPSO algorithm could find 80 optimal solutions and improve 68 solutions for all benchmark instances. For the problems with job release dates, the MPSO algorithm also significantly outperformed the other two algorithms with respect to solution quality within the same computational time.