On the complexity of dynamic programming for sequencing problems with precedence constraints

DOI10.1007/BF02248587zbMath0709.90063MaRDI QIDQ922284

George Steiner

Publication date: 1990

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

assembly line balancingstorage requirementsregression equationsprecedence constrained sequencing

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (11)

An exact algorithm with linear complexity for a problem of visiting megalopolises ⋮ Finding a Level Ideal of a Poset ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization ⋮ On estimating the number of order ideals in partial orders, with some applications ⋮ Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem ⋮ Solving a Routing Problem with the Aid of an Independent Computations Scheme ⋮ On one routing problem modeling movement in radiation fields ⋮ Balancing \(U\)-lines in a multiple \(U\)-line facility ⋮ Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm to generate the ideals of a partial order
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• Complement reducible graphs
• A decomposition algorithm for the single machine total tardiness problem
• A decomposition theorem for partially ordered sets
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A Dynamic Programming Approach to Sequencing Problems
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
• Searching in Trees, Series-Parallel and Interval Orders
• The Recognition of Series Parallel Digraphs
• On Dynamic Programming Methods for Assembly Line Balancing
• Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
• Assembly-Line Balancing—Dynamic Programming with Precedence Constraints
• Transitiv orientierbare Graphen
• An Experimental Investigation and Comparative Evaluation of Production Line Balancing Techniques

This page was built for publication: On the complexity of dynamic programming for sequencing problems with precedence constraints