Exact method for the two-machine flow-shop problem with time delays

We address the two-machine flow-shop scheduling problem with time delays in order to minimize the makespan, i.e., the maximum completion time. We present a comprehensive theoretical analysis of the different lower bounds of the state of the art and we elucidate dominance relationships between them....

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2021-03, Vol.298 (1-2), p.375-406
Main Authors: Mkadem, Mohamed Amine, Moukrim, Aziz, Serairi, Mehdi
Format: Article
Language:English
Subjects:
Branch and bound methods
Business and Management
Combinatorial optimization
Combinatorics
Completion time
Computer Science
Computer simulation
Job shops
Lower bounds
Methods
Operations Research
Operations Research/Decision Theory
Production scheduling
S.I.: CoDIT2017-Combinatorial Optimization
Scheduling (Management)
State of the art
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address the two-machine flow-shop scheduling problem with time delays in order to minimize the makespan, i.e., the maximum completion time. We present a comprehensive theoretical analysis of the different lower bounds of the state of the art and we elucidate dominance relationships between them. We then introduce an exact method based on a branch-and-bound scheme. This method includes a local search-based heuristic and three dominance rules. Finally, a computer simulation of the branch-and-bound method is given on a set of 480 instances. We point out the good performance of our branch-and-bound method that outperforms the state of the art exact method. Precisely, we manage to solve all the state of the art instances except one in a very short time.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-018-3082-x