Scenario Based Robust Line Balancing: Computational Complexity - Mines Saint-Étienne Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2012

Scenario Based Robust Line Balancing: Computational Complexity

Résumé

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.

Dates et versions

emse-00693912 , version 1 (03-05-2012)

Identifiants

Citer

Alexandre Dolgui, Sergey Kovalev. Scenario Based Robust Line Balancing: Computational Complexity. Discrete Applied Mathematics, 2012, Volume 160 (Issues 13-14), pp.Pages 1955-1963. ⟨10.1016/j.dam.2012.04.011⟩. ⟨emse-00693912⟩
59 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More