On the complexity of dynamic programming for sequencing problems with precedence constraints
From MaRDI portal
Publication:922284
DOI10.1007/BF02248587zbMath0709.90063MaRDI QIDQ922284
Publication date: 1990
Published in: Annals of Operations Research (Search for Journal in Brave)
assembly line balancing; storage requirements; regression equations; precedence constrained sequencing
65K05: Numerical mathematical programming methods
90C06: Large-scale problems in mathematical programming
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
90C39: Dynamic programming
Related Items
Solving a Routing Problem with the Aid of an Independent Computations Scheme, On one routing problem modeling movement in radiation fields, Finding a Level Ideal of a Poset, On estimating the number of order ideals in partial orders, with some applications, Balancing \(U\)-lines in a multiple \(U\)-line facility, Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization, An exact algorithm with linear complexity for a problem of visiting megalopolises, Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
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
