A hardware architecture for the Branch and Bound Flow-Shop Scheduling algorithm

Branch-and-Bound (B&B) algorithms are one of the most employed techniques in optimization problems. Its complexity increases exponentially with problem size and features a challenging dynamic memory management caused by recursive processing. Most solutions focus on parallel branch evaluation in multi-core CPUs or GPUs. To the best of our knowledge, to the date, no works have employed FPGAs to implement the BB technique. In this paper, we propose a mixed hardware-software architecture to solve the Flow-Shop Scheduling Problem (FSP). We use Vivado HLS to construct a simple processing element (PE) for lower bound computation and integrate it with an ARM processor system. A Xilinx ZYNQ-7020 device is used to synthesize 10 PEs and reach an acceleration of about 5× over bare-metal execution on the same platform. In addition, we propose a pseudo-branching technique for higher computation overlapping attaining speed ups of 10.3× for a maximum problem size of 20 jobs in 20 machines.