A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time

DOI10.1287/MNSC.31.10.1300zbMath0601.90083OpenAlexW1991139730MaRDI QIDQ3737197

Chris N. Potts

Publication date: 1985

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.31.10.1300

zbMATH Keywords

Lagrange multipliersLagrangean relaxationbranch and boundlower boundprecedence constraintsComputational resultssum of weighted completion timessingle machine sequencingcost reduction method

Mathematics Subject Classification ID

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

Related Items (11)

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ An exact dynamic programming algorithm for the precedence-constrained class sequencing problem ⋮ Formulating a scheduling problem with almost identical jobs by using positional completion times ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ Exact solution procedures for the balanced unidirectional cyclic layout problem ⋮ Mathematical Modeling of Scheduling Problems ⋮ A branch and bound algorithm for the minimum storage-time sequencing problem ⋮ Cellular control of manufacturing systems ⋮ Scheduling identical parallel machines to minimize total weighted completion time ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

This page was built for publication: A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time