Approximating a two‐machine flow shop scheduling under discrete scenario uncertainty

Approximating a two‐machine flow shop scheduling under discrete scenario uncertainty

0.00 Avg rating0 Votes
Article ID: iaor201110454
Volume: 217
Issue: 1
Start Page Number: 36
End Page Number: 43
Publication Date: Feb 2012
Journal: European Journal of Operational Research
Authors: , ,
Keywords: combinatorial optimization
Abstract:

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min–max and min–max regret criteria are adopted. The min–max regret version of the problem is known to be weakly NP‐hard even for two processing time scenarios. In this paper, it is shown that the min–max and min–max regret versions of the problem are strongly NP‐hard even for two scenarios. Furthermore, the min–max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3-ϵ)‐approximable for any ϵ >0 unless P=NP if the number of scenarios is a part of the input. On the other hand, the min–max regret version is not at all approximable even for two scenarios.

Reviews

Required fields are marked *. Your email address will not be published.