On the parameterized tractability of single machine scheduling with rejection

Danny Hermelin, Michael Pinedo, Dvir Shabtay and Nimrod Talmon

European Journal of Operational Research, 2019, vol. 273, issue 1, 67-73

Abstract: In this paper we study a single machine scheduling problem with rejection. In such a scheduling problem, the scheduler can reject to process a job in the shop at a certain cost. Our objective is to minimize the total completion time of the jobs to be processed in the shop, given that the total rejection cost will not exceed a certain predefined threshold. The problem is known to be NP-hard, and to better investigate its hardness our objective is to study whether the problem becomes tractable when some specific natural parameters are of a limited size. The analysis is done by using the theory of parameterized complexity and includes the following parameters: the cardinality of the set of accepted jobs, the number of different processing times, the number of different rejection costs, the maximal processing time, and the maximal rejection cost. We show that the problem is W[1]-hard for the first parameter, while it is fixed-parameterized tractable for all other parameters.

Keywords: Single machine scheduling; Scheduling with rejection; Parameterized complexity; Fixed-parameter tractability (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171830660X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:273:y:2019:i:1:p:67-73

DOI: 10.1016/j.ejor.2018.07.038

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
Bibliographic data for series maintained by Catherine Liu ().