Single-machine preemptive scheduling with assignable due dates or assignable weights to minimize total weighted late work

Rubing Chen, Xinyu Dong, Jinjiang Yuan, C.T. Ng and T.C.E. Cheng

European Journal of Operational Research, 2025, vol. 322, issue 2, 467-479

Abstract: In this paper we study single-machine preemptive scheduling to minimize the total weighted late work with assignable due dates or assignable weights. For the problem with assignable due dates, we show that it is binary NP-hard, solvable in pseudo-polynomial time, and solvable in polynomial time when all the jobs have agreeable processing times and weights. For the problem with assignable weights, we show that it is solvable in polynomial time. For the problem with assignable due dates and assignable weights, we show that it is binary NP-hard, solvable in pseudo-polynomial time, and solvable in polynomial time when all the jobs have the same processing times.

Keywords: Scheduling; Preemptive jobs; Total weighted late work; Assignable due dates; Assignable weights (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724008610
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:322:y:2025:i:2:p:467-479

DOI: 10.1016/j.ejor.2024.11.010

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 ().