Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers
From MaRDI portal
Abstract: 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 nodes.
Recommendations
- A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem
- A computational study of the permutation flow shop problem based on a tight lower bound
- Parallel hybrid heuristics for the permutation flow shop problem
- New hard benchmark for flowshop scheduling problems minimising makespan
- A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation
Cites work
- A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem
- A fast tabu search algorithm for the permutation flow-shop problem
- A General Bounding Scheme for the Permutation Flow-Shop Problem
- A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
- A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
- An adaptive branching rule for the permutation flow-shop problem
- An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
- Benchmarks for basic scheduling problems
- Branch-and-bound and parallel computation: A historical note
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- Iterative beam search algorithms for the permutation flowshop
- Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters
- New hard benchmark for flowshop scheduling problems minimising makespan
- On Flow Shop Scheduling with Release and Due Dates to Minimize Maximum Lateness
- Optimal two- and three-stage production schedules with set-up time included
- Parallel Branch-and-Branch Algorithms: Survey and Synthesis
- Parallel depth first search. I: Implementation
- Parallel hybrid heuristics for the permutation flow shop problem
- Parallel Search Algorithms for Discrete Optimization Problems
- Solving large quadratic assignment problems on computational grids
- The Complexity of Flowshop and Jobshop Scheduling
- Towards a heterogeneous and adaptive parallel branch-and-bound algorithm
Cited in
(5)- A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem
- New hard benchmark for flowshop scheduling problems minimising makespan
- Deterministic constructive N-NEH+ algorithm to solve permutation flow shop scheduling problem with makespan criterion
- A parallel ``Go with the winners algorithm for some scheduling problems
- Bounds for the permutation flowshop scheduling problem: new framework and theoretical insights
This page was built for publication: Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5057997)
