Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

Abstract

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.

Keywords:

• ant colony optimisation algorithms
• permutation flow shop scheduling
• batch processing machines
• nonidentical job sizes
• makespan

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Xu Zheng  http://orcid.org/0000-0002-3773-7845

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [Grant number 71671168] and the Natural Science Foundation of Hunan Province [Grant number 2018JJ3891].