A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem

Fred F. Easton

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

It has been suggested that relaxation and fathoming methods can be used to reduce the state space of certain dynamic programs. This paper applies these techniques to the dynamic program for assembly line balancing and shows that with an optimal upper bound, a substantial reduction in state space is possible. With a static nonoptimal upper bound however, the approach is found to offer little improvement over conventional dynamic programming. To achieve more consistent results, a dynamic upper bound procedure is proposed. Applied to a well-known set of assembly line balancing problems, the performance of the proposed algorithm was found comparable to a state-of-the-art integer programming method. The approach appears generalizable to dynamic programs with a similar structure.

Original languageEnglish (US)
Pages (from-to)163-175
Number of pages13
JournalComputers and Operations Research
Volume17
Issue number2
DOIs
StatePublished - 1990

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem'. Together they form a unique fingerprint.

Cite this