  Makespan minimization in permutation flow-shop scheduling is a well-known
hard combinatorial optimization problem. Among the 120 standard benchmark
instances proposed by E. Taillard in 1993, 23 have remained unsolved for almost
three decades. In this paper, we present our attempts to solve these instances
to optimality using parallel Branch-and-Bound tree search on the
GPU-accelerated Jean Zay supercomputer. We report the exact solution of 11
previously unsolved problem instances and improved upper bounds for 8
instances. The solution of these problems requires both algorithmic
improvements and leveraging the computing power of peta-scale high-performance
computing platforms. The challenge consists in efficiently performing parallel
depth-first traversal of a highly irregular, fine-grained search tree on
distributed systems composed of hundreds of massively parallel accelerator
devices and multi-core processors. We present and discuss the design and
implementation of our permutation-based B&B and experimentally evaluate its
parallel performance on up to 384 V100 GPUs (2 million CUDA cores) and 3840 CPU
cores. The optimality proof for the largest solved instance requires about 64
CPU-years of computation -- using 256 GPUs and over 4 million parallel search
agents, the traversal of the search tree is completed in 13 hours, exploring
339$\times 10^{12}$ nodes.
