A Dynamic Programming Approach to Stochastic Assembly Line Balancing

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 constr...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1989-04, Vol.35 (4), p.459-471
Main Author: Carraway, Robert L
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Assembly lines
Cost allocation
Determinism
Dynamic programming
Exact sciences and technology
Gaussian distributions
line balancing
Operational research and scientific management
Operational research. Management science
production
production/scheduling
Programming
Random variables
Recursion
scheduling
Scheduling, sequencing
stochastic models
Storage time
Work stations
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.).
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.35.4.459