Skip to Main content Skip to Navigation
Conference papers

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 metadata
Contributor : Florent Breuil Connect in order to contact the contributor
Submitted on : Wednesday, December 19, 2012 - 11:22:16 AM
Last modification on : Sunday, June 26, 2022 - 9:36:05 AM


  • HAL Id : emse-00766921, version 1


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⟩



Record views