Scenario Based Robust Line Balancing: Computational Complexity - Mines Saint-Étienne
Journal Articles Discrete Applied Mathematics Year : 2012

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.

Dates and versions

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

Identifiers

Cite

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⟩
71 View
0 Download

Altmetric

Share

More