Notes on Complexity of the Simple Assembly Line Balancing Problem - Mines Saint-Étienne
Conference Papers Year : 2012

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.
No file

Dates and versions

emse-00766921 , version 1 (19-12-2012)

Identifiers

  • HAL Id : emse-00766921 , version 1

Cite

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⟩
119 View
0 Download

Share

More