Treffer: Roles reversal evolutionary algorithm with neighborhood search for job shop scheduling problem considering insufficient machine buffer and AGVs.

Automated guided vehicles (AGVs) have become essential for job transportation amid the rise of automated manufacturing. However, space constraints in many workshops limit the storage capacity of machines. This study explores a scheduling problem for job shops considering insufficient machine buffers and AGVs (JSPIMBA). To formulate this problem, we designed a tailored disjunctive graph (TDG) that captures the features of JSPIMBA, explicitly modeling interactions and dependencies among processing, transportation, and buffer tasks. We then developed a mixed-integer linear programming (MILP) model based on the TDG, which includes four decision subproblems and reflects relationships among three types of task nodes. To address this challenge, we proposed a role reversal-based evolutionary algorithm with neighborhood search (RREANS). The core idea is to assign individuals three distinct roles: leader, follower, and explorer. During evolution, individuals are dynamically transitioned among these roles. For leaders, we designed a heuristic with priority weights, incorporating a just-in-time dispatching rule for AGVs, a first-in-first-out (FIFO) rule, and a high-priority weight-based rule for operations. Furthermore, we provided three theorems based on the characteristics of the problem to identify non-critical tasks and introduced three carefully designed neighborhood search operators to improve solution quality. Followers utilized the objective space by clustering around leaders, selected via a score-based operator that evaluates both fitness and distance to the best individual. Explorers, generated randomly to prevent local optima entrapment, independently explore the objective space and provide essential feedback to leaders. Furthermore, we implemented a role reversal mechanism among individuals to enhance the optimization capacity of the RREANS algorithm. Finally, we conducted an extensive computational study on 40 modified benchmark instances to rigorously evaluate the algorithm's performance. [ABSTRACT FROM AUTHOR]