Algorithms for two-machine flow-shop sequencing with precedence constraints

DOI10.1016/0377-2217(84)90238-8MaRDI QIDQ800822zbMATH OpenOpenAlexFDO

Authors A. M. A. Hariri, Chris N. Potts

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0377-2217(84)90238-8

zbMATH Keywords

branch-and-bound algorithmLagrangean relaxationlower bounding ruleminimizing the maximum completion timeprecedence constraintstwo-machine flow-shop

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

Review text

This paper studies a scheduling problem of minimizing the maximum completion time in a two-machine flow-shop for which precedence constraints on jobs are specified, implying if one job has precedence over another, then the former must be completed on a machine before the latter begins processing on that machine. For this problem a branch-and-bound algorithm is proposed, including a new lower bounding rule based on Lagrangean relaxation and a new branching rule. This algorithm is compared to two existing branch-and- bound methods and tested up to 80 jobs, but it does not appear to be significantly superior to the others.

Recommendations

• The two-machine flow shop problem with arbitrary precedence relations
• The two-machine flowshop total completion time problem: improved lower bounds and a branch-and-bound algorithm
• The three-machine flow-shop problem with arbitrary precedence relations
• Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation
• Flow shop scheduling problems under machine-dependent precedence constraints

Cites work

• A branch and bound algorithm for the two-stage assembly scheduling problem
• A General Bounding Scheme for the Permutation Flow-Shop Problem
• An adaptive branching rule for the permutation flow-shop problem
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• Optimal two- and three-stage production schedules with set-up time included
• Scheduling two job classes on a single machine
• Sequencing \(n\) jobs on two machines with arbitrary time lags
• Sequencing to Minimize the Maximum Job Cost
• The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
• The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
• TWO-MACHINE SCHEDULING UNDER ARBITRARY PRECEDENCE CONSTRAINTS
• TWO-MACHINE SCHEDULING UNDER REQUIRED PRECEDENCE AMONG JOBS

Cited in

(9)

• Cellular control of manufacturing systems
• The three-machine flow-shop problem with arbitrary precedence relations
• A two-machine flowshop scheduling problem with precedence constraint on two jobs
• Flow shop scheduling problems under machine-dependent precedence constraints
• The two-machine flow shop problem with arbitrary precedence relations
• Certain exact and approximate algorithms for solving precedence problems with constraints
• An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer
• Two-machine no-wait flow shop scheduling problem with precedence constraints
• A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Algorithms for two-machine flow-shop sequencing with precedence constraints

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