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.
Type de document :
Communication dans un congrès
Conference UKI'2012, Apr 2012, Moscou, Russia. 8 p., 2012
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00766921
Contributeur : Florent Breuil <>
Soumis le : mercredi 19 décembre 2012 - 11:22:16
Dernière modification le : jeudi 11 janvier 2018 - 06:16:31

Identifiants

  • 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., 2012. 〈emse-00766921〉

Partager

Métriques

Consultations de la notice

72