On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates

Gur Mosheiov (), Daniel Oron () and Dvir Shabtay ()
Additional contact information
Gur Mosheiov: The Hebrew University
Daniel Oron: The University of Sydney Business School
Dvir Shabtay: Ben-Gurion University of the Negev

Journal of Scheduling, 2022, vol. 25, issue 5, No 6, 577-587

Abstract: Abstract We study two $$\mathcal {NP}$$ NP -hard single-machine scheduling problems with generalized due-dates. In such problems, due-dates are associated with positions in the job sequence rather than with jobs. Accordingly, the job that is assigned to position j in the job processing order (job sequence), is assigned with a predefined due-date, $$\delta _{j}$$ δ j . In the first problem, the objective consists of finding a job schedule that minimizes the maximal absolute lateness, while in the second problem, we aim to maximize the weighted number of jobs completed exactly at their due-date. Both problems are known to be strongly $$\mathcal {NP}$$ NP -hard when the instance includes an arbitrary number of different due-dates. Our objective is to study the tractability of both problems with respect to the number of different due-dates in the instance, $$\nu _{d}$$ ν d . We show that both problems remain $$ \mathcal {NP}$$ NP -hard even when $$\nu _{d}=2$$ ν d = 2 , and are solvable in pseudo-polynomial time when the value of $$\nu _{d}$$ ν d is upper bounded by a constant. To complement our results, we show that both problems are fixed parameterized tractable (FPT) when we combine the two parameters of number of different due-dates ( $$\nu _{d}$$ ν d ) and number of different processing times ( $$\nu _{p}$$ ν p ).

Keywords: Scheduling; Single machine; Generalized due-dates; $${\mathcal {NP}}$$ NP -hard; Pseudo-polynomial time algorithm; Parameterized complexity. (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00743-9 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:jsched:v:25:y:2022:i:5:d:10.1007_s10951-022-00743-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00743-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().