Assembly-Line Balancing---Dynamic Programming with Precedence Constraints

Michael Held, Richard M. Karp and Richard Shareshian
Additional contact information
Michael Held: International Business Machines Corporation, New York, New York
Richard M. Karp: International Business Machines Corporation, New York, New York
Richard Shareshian: International Business Machines Corporation, New York, New York

Operations Research, 1963, vol. 11, issue 3, 442-459

Abstract: This 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.

Date: 1963
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.11.3.442 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:11:y:1963:i:3:p:442-459

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().