Hamming Distance-Based Heuristic for Flexible Job-Shop Scheduling Problems

The flexible job-shop scheduling problem (FJSSP) has gained significant attention due to its adaptability to modern manufacturing systems. However, for large-scale production chains, finding the optimal schedule to minimize the makespan quickly becomes computationally infeasible due to the complexity of the solution space, leading to the rise of heuristic and metaheuristic methods to obtain near-optimal solutions. In the same direction, this paper models the FJSSP using mixed-integer linear programming (MILP), proposing a heuristic method based on the Hamming distance between the problem's binary variables to efficiently navigate the solution space. By iteratively adjusting routing and sequencing variables, the heuristic produces intermediate solutions that gradually improve the makespan, converging to epsilon-optimal solutions with considerably reduced computation times compared to exact optimization, as demonstrated in a case study based on an instance of a well-known benchmark for FJSSP.