An Integer Programming Algorithm with Network Cuts for Solving the Assembly Line Balancing Problem

F. Brian Talbot and James H. Patterson
Additional contact information
F. Brian Talbot: University of Michigan
James H. Patterson: University of Missouri---Columbia; Nijenrode, The Netherlands School of Business

Management Science, 1984, vol. 30, issue 1, 85-99

Abstract: In this paper, we describe an integer programming algorithm for assigning tasks on an assembly line to work stations in such a way that the number of work stations is minimal for the rate of production desired. The procedure insures that no task is assigned to a work station before all tasks which technologically must be performed before it have been assigned (precedence restrictions are not violated), and that the total time required at each work station performing the tasks assigned to it does not exceed the time available (cycle time restrictions are not violated). The procedure is based on a systematic evaluation (enumeration) of all possible task assignments to work stations. Significant portions of the enumeration process are performed implicitly, however, by utilizing tests described in the paper which are based on the specific structure of the line balancing problem. An artifice termed a network cut is also developed which eliminates from explicit consideration the assignment of tasks to work stations where such assignments would not lead to improved line balances. Results reported demonstrate that the procedure can obtain optimal balances for assembly lines with between 50 and 100 tasks in a reasonable amount of computation time and with modest computer storage requirements.

Keywords: production/scheduling: line balancing; programming: integer algorithms; enumerative; networks/graphs (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.30.1.85 (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:30:y:1984:i:1:p:85-99

Access Statistics for this article

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