BLAST: Bottleneck-Free Large-Scale Algorithm Scheduling Throughput A Streamlined Approach to the Flexible Job Shop Problem (FJSP)

The Flexible Job Shop Scheduling Problem (FJSP) is an NP-Hard problem for task sequencing and resource allocation that poses a computational challenge universally across scientific disciplines and industries that need optimal and fast, high-throughput schedules. The impact of FJSP scheduling solutions is deeply embedded in manufacturing and logistics, genomics and sequencing, astronomy and healthcare, with applications in supply chain optimization, telescope array observation schedules optimization, and hospital scheduling for patient flow. Our proposed BLAST algorithm (Bottleneck-Free Large-Scale Algorithm Scheduling Throughput), addresses this need at its core, relying on a novel hybrid approach overcoming the combinatorial complexity inherent to FJSP problems. BLAST can solve large-scale FJSPs deterministically, yielding optimal schedules and resource allocation efficiency in record time. BLAST is a hybrid method that relies on a combination of intelligent heuristics (Filter Beam Search and Local Search), which yield a quick, nearly optimal schedule that is subsequently used by an MIP solver (Gurobi) as a warm start solution. As a consequence, BLAST deterministically solves FJSP problems (to optimality) dramatically faster than any previously reported methods, using standard and commercially available hardware. BLAST’s optimized heuristics are intelligently guided by Linear Relaxation, greatly reducing the solution space and enabling Gurobi's MIP solver to quickly reach optimal schedules.