Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
复制标题
DOI：
10.1016/j.ejor.2011.08.029
复制
发表时间：
2012-02
期刊：
影响因子：
--
通讯作者：
A. Kasperski;Adam Kurpisz;P. Zieliński
中科院分区：
文献类型：
--
作者：
A. Kasperski;Adam Kurpisz;P. Zieliński
本文研究了数据不确定的两机置换Flow Shop问题，其确定性对应问题已知是多项式可解的。本文假设作业加工时间是不确定的，并将其指定为离散场景集。对于这种不确定性表示，采用了最小-最大和最小-最大后悔准则。已知该问题的最小-最大后悔版本即使对于两个处理时间场景也是弱NP-难的。本文证明了该问题的最小-最大和最小-最大后悔形式即使在两种情形下也是强NP-难的。此外，如果场景的数量是恒定的，则最小-最大版本允许多项式时间近似方案，并且它可以以2的性能比近似，而不是(4/3−ϵ)-对于任何ϵ>；0都是不可近似的，除非如果场景的数量是输入的一部分，则P=NP。另一方面，即使在两种情况下，最小-最大后悔版本也是根本不可近似的。
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.