Optimally Balancing Large Assembly Lines with "Fable"

Roger V. Johnson
Additional contact information
Roger V. Johnson: School of Business, University of Michigan, Ann Arbor, Michigan 48109

Management Science, 1988, vol. 34, issue 2, 240-253

Abstract: A new algorithm for optimally balancing assembly lines is formulated and tested. Named "FABLE," it obtains proven optimal solutions for ten 1000 task lines, which each possess the computationally favorable conditions of an average of at least 6 tasks per work station and a small number of between-task precedence requirements, in less than 20 seconds of IBM 3033U CPU time for each problem. FABLE also performs very favorably on a benchmark group of 64 test problems drawn from the literature, which are of up to 111 tasks each. FABLE finds and proves an optimal solution to the 64 problems in a total of 3.16 seconds of IBM 3090 CPU time. FABLE is a `laser' type, depth-first, branch-and-bound algorithm, with logic designed for very fast achievement of feasibility, ensuring a feasible solution to any line of 1000 or even more tasks. It utilizes new and existing dominance rules and bound arguments. A total of 549 problems of various characteristics are solved to determine conditions under which FABLE performs most and least favorably. Performance is sensitive to average number of tasks per work station, number of between-task precedence requirements (measured by `order strength'), and the total number of tasks per problem. A heuristic variant of FABLE is also described.

Keywords: production/scheduling: line balancing; networks/graphs: tree algorithms; dynamic programming (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.2.240 (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:34:y:1988:i:2:p:240-253

Access Statistics for this article

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