Notes on Complexity of the Simple Assembly Line Balancing Problem

Abstract : In this paper, we consider the assembly line balancing problem, for which it is necessary to minimize the number of used machine for a given cycle time. We propose a special case of the problem for which any Branch and Bound algorithm with any polynomial time computed Lower Bound can't solve some instances even for n=60 operations in appropriate time. Additionally, we analyze the worst maximal--station-load line balance and present a technique to reduce the graph of precedence relations that provides some advantages.
Document type :
Conference papers
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00766921
Contributor : Florent Breuil <>
Submitted on : Wednesday, December 19, 2012 - 11:22:16 AM
Last modification on : Monday, January 14, 2019 - 12:08:18 PM

Identifiers

  • HAL Id : emse-00766921, version 1

Citation

Evgeny R. Gafarov, Alexandre Dolgui, Alexander Lazarev. Notes on Complexity of the Simple Assembly Line Balancing Problem. Conference UKI'2012, Apr 2012, Moscou, Russia. 8 p. ⟨emse-00766921⟩

Share

Metrics

Record views

143