A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem

DOI10.1016/j.ejor.2020.01.039zbMath1441.90061OpenAlexW3001967193WikidataQ126289529 ScholiaQ126289529MaRDI QIDQ2178110

Mohand Mezmaz, Nouredine Melab, Jan Gmys, Daniel Tuyttens

Publication date: 7 May 2020

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02421229/file/Gmys_et_al_Manuscript-R2.pdf

zbMATH Keywords

branch-and-boundparallel computingmakespanflowshop

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Parallel numerical computation (65Y05)

Related Items (10)

Iterative beam search algorithms for the permutation flowshop ⋮ Exactly Solving Hard Permutation Flowshop Scheduling Problems on Peta-Scale GPU-Accelerated Supercomputers ⋮ A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem ⋮ On some lower bounds for the permutation flowshop problem ⋮ Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm ⋮ Shop scheduling in manufacturing environments: a review ⋮ Maximizing total early work in a distributed two‐machine flow‐shop ⋮ Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion ⋮ Manufacturing rescheduling after crisis or disaster-caused supply chain disruption ⋮ A branch-and-bound approach to the no-idle flowshop scheduling problem

Cites Work

• New hard benchmark for flowshop scheduling problems minimising makespan
• Different behaviour of a double branch-and-bound algorithm on \(\mathrm {Fm}|\mathrm{prmu}|C_{\max}\) and \(\mathrm {Fm}|\mathrm {block}|C_{\max}\) problems
• An exact parallel method for a bi-objective permutation flowshop problem
• A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
• An empirical analysis of the optimality rate of flow shop heuristics
• An adaptive branching rule for the permutation flow-shop problem
• Two branch and bound algorithms for the permutation flow shop problem
• A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem
• An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
• A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation
• A computational study of the permutation flow shop problem based on a tight lower bound
• A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem
• Benchmarks for basic scheduling problems
• Optimal two- and three-stage production schedules with setup times included
• Fifty years of scheduling: a survey of milestones
• A Comparative Study of Flow-Shop Algorithms
• A General Bounding Scheme for the Permutation Flow-Shop Problem
• The Complexity of Flowshop and Jobshop Scheduling
• A review and classification of heuristics for permutation flow-shop scheduling with makespan objective
• Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem
• Flowshop-scheduling problems with makespan criterion: a review
• Unnamed Item

This page was built for publication: A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem