Two-machine open-shop scheduling with rejection to minimize the makespan

Liqi Zhang, Lingfa Lu () and Jinjiang Yuan
Additional contact information
Liqi Zhang: Henan Agricultural University
Lingfa Lu: Zhengzhou University
Jinjiang Yuan: Zhengzhou University

OR Spectrum: Quantitative Approaches in Management, 2016, vol. 38, issue 2, No 10, 519-529

Abstract: Abstract In this paper, we consider the two-machine open-shop scheduling problem with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection cost of rejected jobs. We show that the problem is NP-hard even in three special cases and then provide a pseudo-polynomial time algorithm for this problem, which means that the problem is actually NP-hard in the ordinary sense. This answers an open problem posed by Shabtay et al. in (J Schedul 16:3–28, 2013). Finally, a 2-approximation algorithm and an FPTAS are designed for the problem.

Keywords: Scheduling; Open shop; Rejection cost; NP-hard (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-015-0409-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:38:y:2016:i:2:d:10.1007_s00291-015-0409-8

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-015-0409-8

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().