Dual Resource Flexible Job Shop Scheduling Problems: The xBTF Algorithm

In this paper, we unveil the xBTF, an innovative advancement to the Biggest Threat First (BTF) algorithm. In our previous research, the BTF achieved groundbreaking results for minimizing the makespan of the Dual Resource Constrained Job Shop Scheduling Problem (DRC-FJSSP). However, it faced limitations due to its inability to effectively balance worker and machine workloads. This was primarily because it constructed schedules sequentially, without considering the resource requirements of subsequent operations. The xBTF introduces a penalty when performing resource allocation, based on the expected worker and machine workload. Preliminary experimentation utilizing the MK1-10 benchmark dataset showcases xBTF’s supremacy over its predecessor, particularly in scenarios with higher resource workloads. Moreover, the xBTF utterly outperforms a state-of-the-art metaheuristic, the KGFOA, with extremely small execution times, which makes it excellent also for rescheduling in dynamic scenarios.