Scenario Based Robust Line Balancing: Computational Complexity

Abstract : This paper studies the following line balancing problem with uncertain operation execution times. Operations on the same product have to be assigned to the stations of a transfer line. The product moves along the stations in the same direction, and operations assigned to the same station are executed sequentially. Exclusion, inclusion and precedence relations are given on the set of operations. Operation execution times are uncertain in the sense that their set belongs to a given set of scenarios. The objective is to minimize the line cycle time, which is equal to the maximum total execution time of operations of the same station, for the worst scenario. An approach to reducing the scenario set is described. Several special cases of the problem are proved NP-hard and strongly NP-hard. Enumerative dynamic programming algorithms and problem-specific polynomial time algorithms are suggested for some cases.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, Volume 160 (Issues 13-14), pp.Pages 1955-1963. 〈10.1016/j.dam.2012.04.011〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00693912
Contributeur : Florent Breuil <>
Soumis le : jeudi 3 mai 2012 - 09:42:53
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

Citation

Alexandre Dolgui, Sergey Kovalev. Scenario Based Robust Line Balancing: Computational Complexity. Discrete Applied Mathematics, Elsevier, 2012, Volume 160 (Issues 13-14), pp.Pages 1955-1963. 〈10.1016/j.dam.2012.04.011〉. 〈emse-00693912〉

Partager

Métriques

Consultations de la notice

106