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: | Kasperski Adam, Zielinski Pawel, Kurpisz Adam |
Keywords: | combinatorial optimization |
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-