A Branch and Bound Algorithm for Assembly Line Balancing Problems with Formulation Irregularities

Roger V. Johnson
Additional contact information
Roger V. Johnson: University of California at Los Angeles

Management Science, 1983, vol. 29, issue 11, 1309-1324

Abstract: This paper describes a branch and bound algorithm which can solve assembly line balancing probems with nine modifications to the originally formulated problem of minimizing the required number of assembly stations, given a cycle time, a set of tasks with given deterministic performance times, and between-task precedence relationships. The first two formulation modifications are those of permitting planned imbalance in the total of task performance times at each assembly station, and allowing specific tasks to be assigned to specific types of assembly stations. Seven further problem modifications can be solved by the proposed algorithm, or by any algorithm or heuristic that can solve problems containing these first two modifications. They are: treatment of stochastic task performance times on unpaced lines; requirement of particular tasks to be assigned to particular stations; requirement of task groupings according to task skill levels; requirement of particular tasks to be assigned to only a left-of-line or right-of line station; required task separations; some mixed model situations; and where paralleling of a specified task into two (or more stations) is permitted. The algorithm is presented in both conceptual and detailed form. Computer computation times to solve a selected cross-sectional sample of problems are provided.

Keywords: production/scheduling: line balancing; facilities/equipment planning: design; networks/graphs: applications (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.29.11.1309 (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:29:y:1983:i:11:p:1309-1324

Access Statistics for this article

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