Generating improved dominance conditions for the flowshop problem

DOI10.1016/0305-0548(87)90056-6MaRDI QIDQ580164zbMATH OpenOpenAlexFDO

Authors Jatinder N. D. Gupta, J. George Shanthikumar, Wlodzimierz Szwarc

Publication date 1987

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(87)90056-6

zbMATH Keywords

branch-and-bounddominance conditionsflowship scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Review text

This paper proposes a class of functions that generates new dominance conditions for the flowship scheduling problem and shows that the use of these conditions will eliminate more partial sequences than the existing conditions. While the problem is in the NP-complete category, the use of the proposed dominance conditions reduces the number of active partial schedules to be examined and stored. These improvements are useful in solving the flowshop scheduling problems through the branch-and-bound and elimination procedures.

Recommendations

• Elimination conditions and lower bounds for the permutation flow-shop sequencing problem
• scientific article; zbMATH DE number 2186529
• Dominance conditions determination based on machine idle times for the permutation flowshop scheduling problem
• Nonpreemptive flowshop scheduling with machine dominance
• scientific article; zbMATH DE number 3883926

Cites work

• A General Bounding Scheme for the Permutation Flow-Shop Problem
• scientific article; zbMATH DE number 3278981 (Why is no real title available?)
• Optimal Elimination Methods in the m × n Flow-Shop Scheduling Problem
• Permutation flow-shop theory revisited
• Technical Note—An Improved Combinatorial Algorithm for the Flowshop-Scheduling Problem
• Technical Note—Dominance Conditions for the Three-Machine Flow-Shop Problem
• Technical Note—Improved Dominance Conditions for the Three-Machine Flowshop Scheduling Problem
• The Complexity of Flowshop and Jobshop Scheduling

Cited in

(4)

• Minimizing total tardiness in permutation flowshops
• A new branch and bound algorithm for minimizing mean tardiness in two- machine flowshops
• scientific article; zbMATH DE number 3883926 (Why is no real title available?)
• Empirically discovering dominance relations for scheduling problems using an evolutionary algorithm

This page was built for publication: Generating improved dominance conditions for the flowshop problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580164)