• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Notes on Complexity of the Simple Assembly Line Balancing Problem

P. 259-266.
Lazarev A. A., Gafarov E., Dolgui A.

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.