Scheduling problems on parallel machines with machine-dependent generalized due-dates

Baruch Mor, Gur Mosheiov and Dvir Shabtay ()
Additional contact information
Baruch Mor: Ariel University
Gur Mosheiov: The Hebrew University
Dvir Shabtay: Ben-Gurion University of the Negev

Annals of Operations Research, 2025, vol. 347, issue 3, No 10, 1455-1471

Abstract: Abstract In scheduling problems with generalized due-dates, the due-dates are position-dependent (and not job-dependent as in classical scheduling). In this paper, we study scheduling problems on parallel machines, and the underlying assumption is that the generalized due-dates are machine-dependent. The following scheduling measures are considered: total tardiness, maximum tardiness, number of tardy jobs, and total late work. We show that all the problems are NP-hard even if all generalized due-dates are identical. We complement this hardness result by showing that all problems are solvable in pseudo-polynomial time and that minimizing total late work is fixed parametrized tractable with respect to the number of different generalized due-dates and processing times in the instance. We also tested the pseudo-polynomial time algorithms, showing they can easily solve instances containing up to 200 jobs.

Keywords: Scheduling; Parallel machines; Generalized due-dates; Dynamic programming; Fixed parametrized tractability (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06468-0 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:annopr:v:347:y:2025:i:3:d:10.1007_s10479-025-06468-0

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

DOI: 10.1007/s10479-025-06468-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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