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

DOI10.1016/S0377-2217(01)00374-5zbMath1001.90065OpenAlexW2034737492MaRDI 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 relaxationbranch-and-boundflow shop scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Optimality conditions and duality in mathematical programming (90C46)

Related Items

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

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