 Approximating a two-machine flow shop scheduling under discrete scenario uncertaintyAdam Kasperski, Adam Kurpisz and Paweł Zieliński European Journal of Operational Research, 2012, vol. 217, issue 1, 36-43 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. Keywords: Combinatorial optimization; Scheduling; Approximation; Robust optimization; Flow shop (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:217:y:2012:i:1:p:36-43 DOI: 10.1016/j.ejor.2011.08.029 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.