Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Florent Breuil <>
Submitted on : Thursday, May 3, 2012 - 9:42:53 AM
Last modification on : Wednesday, June 24, 2020 - 4:19:08 PM

Links full text



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⟩



Record views