A hybrid bacterial foraging optimization algorithm for makespan minimization in permutation flow shop scheduling

Abstract

Permutation flow shop scheduling problems (PFSP) with makespan minimization are a standard benchmark in production scheduling, where solution quality depends on effective search in a discrete permutation space. This paper proposes HBFO, a hybrid discrete bacterial foraging optimization method that implements bacterial foraging dynamics through permutation-preserving operators and integrates intensification and diversification mechanisms. HBFO is evaluated on Taillard's 120 benchmark instances using 20 independent runs per instance. Performance is assessed using the best-run makespan, the relative percentage deviation (RPD) relative to best-known reference values, and run-to-run variability. Compared with recent advanced metaheuristics reported on the same benchmark families, HBFO achieves the best or tied-best best-run makespan in 115 of the 120 instances, with five instances where another method attains a lower best-run value. The RPD results show frequent exact matches to the reference values and predominantly low-percentage deviations otherwise. Configuration-level summaries further indicate that both average deviation and variability vary across Taillard instance families.