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

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.

► The min–max (regret) F2∥Cmax turns out to be strongly NP-hard for two scenarios.
► The min–max regret F2∥Cmax is not at all approximable.
► The min–max F2∥Cmax with a bounded scenario set admits a PTAS.
► For an unbounded set the problem is not approximable within a factor less than 4/3.