An improved branch-and-bound algorithm for the two machine total completion time flow shop problem

DOI10.1016/S0377-2217(01)00374-5zbMath1001.90065MaRDI QIDQ1604072

Frederico Della Croce, Roberto Tadei, Marco Ghirardi

Publication date: 3 July 2002

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(01)00374-5

zbMATH Keywords

Lagrangean relaxation; branch-and-bound; flow shop scheduling

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C46: Optimality conditions and duality in mathematical programming

Related Items

A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP, Enhanced lower bounds and exact procedures for total completion time minimization in a two‐machine permutation flowshop with release dates, Flow shop non-idle scheduling and resource-constrained scheduling, An effective differential evolution algorithm for permutation flow shop scheduling problem, The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation, An assignment-based lower bound for a class of two-machine flow shop problems, Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, A time-indexed LP-based approach for min-sum job-shop problems, A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function, A two-machine flowshop problem with two agents, A matheuristic approach for the two-machine total completion time flow shop problem, A robust two-machine flow-shop scheduling model with scenario-dependent processing times, Minimizing total completion time in a two-machine flow shop with deteriorating jobs, Lower bounds for minimizing total completion time in a two-machine flow shop, A bicriteria flowshop scheduling with a learning effect, Two machine flow shop scheduling problem with weighted WIP costs, An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion, Flow shops with WIP and value added costs, An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, Two-machine flowshop scheduling with a secondary criterion, The two-machine flowshop total completion time problem: improved lower bounds and a branch-and-bound algorithm, The two-machine flowshop scheduling problem with sequence-independent setup times: new lower bounding strategies, A global constraint for total weighted completion time for unary resources, The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time, A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

Cites Work

• Unnamed Item
• Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation
• The two-machine total completion time flow shop problem
• Generalized pairwise interchanges and machine scheduling
• Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems
• Two-machine flowshop scheduling to minimize mean flow time
• Minimizing Total Completion Time in a Two-Machine Flowshop: Analysis of Special Cases
• The Complexity of Flowshop and Jobshop Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey