Min-max and min-max (relative) regret approaches to representatives selection problem - Mines Saint-Étienne Accéder directement au contenu
Article Dans Une Revue 4OR: A Quarterly Journal of Operations Research Année : 2012

Min-max and min-max (relative) regret approaches to representatives selection problem

Résumé

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min-max and min-max (relative) regret approaches are used for making a selection decision. The arising min-max, min-max regret and min-max relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.
Fichier non déposé

Dates et versions

emse-00693479 , version 1 (02-05-2012)

Identifiants

Citer

Alexandre Dolgui, Sergey Kovalev. Min-max and min-max (relative) regret approaches to representatives selection problem. 4OR: A Quarterly Journal of Operations Research, 2012, Volume 10 (Issue 2), pp 181-192. ⟨10.1007/s10288-012-0202-3⟩. ⟨emse-00693479⟩
73 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More