A Dynamic Programming Approach to Stochastic Assembly Line Balancing

Robert L. Carraway
Additional contact information
Robert L. Carraway: Colgate Darden Graduate School of Business Administration, University of Virginia, Charlottesville, Virginia 22906-6550

Management Science, 1989, vol. 35, issue 4, 459-471

Abstract: Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constraints, and a lower bound on the probability of the work at any station being completed within the cycle time. We present two dynamic programming (DP) algorithms for this problem, each guaranteed to be optimal under a certain mild condition. Our general approach is based on the Held et al. (Held, M., R. M. Karp, R. Shareshian. 1963. Assembly-line-balancing-dynamic programming with precedence constraints. Oper. Res. 11 442--459.) formulation of the deterministic line balancing problem and thus represents a modification of previous work by Kao (Kao, E. P. C. 1976. A preference order dynamic program for stochastic assembly line balancing. Management Sci. 22 1097--1104.). Computational results indicate that both algorithms significantly outperform an alternative DP approach suggested by Henig (Henig, M. I. 1986. Extensions of the dynamic programming method in the deterministic and stochastic assembly-line balancing problems. Comput. Oper. Res. 13 443--449.).

Keywords: production/scheduling; line balancing; stochastic models; dynamic programming (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.35.4.459 (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:ormnsc:v:35:y:1989:i:4:p:459-471

Access Statistics for this article

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