A Late Acceptance Hill-Climbing Algorithm for Flexible Job Shop Scheduling Problems with Worker Flexibility

Abstract

The Flexible Job Shop Scheduling Problem with Worker constraints (FJSSP-W) is a challenging optimization problem that simultaneously coordinates machine assignment, worker allocation, and operation sequencing. This paper proposes a Late Acceptance Hill Climbing (LAHC) metaheuristic to address the FJSSP-W. LAHC uses a single-state trajectory with a history-based acceptance criterion, enabling straightforward parameter tuning and interpretation. Our implementation explores a neighborhood structure comprising machine and worker reassignments, as well as job-sequence permutations, while using a secondary objective of workload balance to break ties in makespan values. Experimental results on the competition's benchmark demonstrate that the proposed LAHC approach is a promising algorithm to address the problem.