Assembly-Line Balancing—Dynamic Programming with Precedence Constraints
1963; Institute for Operations Research and the Management Sciences; Volume: 11; Issue: 3 Linguagem: Inglês
10.1287/opre.11.3.442
ISSN1526-5463
AutoresMichael Held, Richard M. Karp, Richard Shareshian,
Tópico(s)Manufacturing Process and Optimization
ResumoThis paper approaches the assembly-line balancing problem as a sequencing problem involving precedence constraints that prohibit the occurrence of certain orderings. This approach permits the formulation of a dynamic programming algorithm for the exact solution of small assembly-line balancing problems. A generalization of this algorithm combined with a successive approximations technique is used for the solution of large problems. In addition, certain combinatorial problems associated with partially ordered sets are formulated and discussed in detail. These problems arise whenever sequencing problems with precedence constraints are treated by dynamic programming techniques.
Referência(s)