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.