A new perspective on single-machine scheduling problems with late work related criteria

Dvir Shabtay ()
Additional contact information
Dvir Shabtay: Ben-Gurion University of the Negev

Annals of Operations Research, 2023, vol. 322, issue 2, No 14, 947-966

Abstract: Abstract This paper provides two new perspectives on single-machine scheduling problems in which the objective involves penalties regarding late work. Both of this perspectives have been neglected in the previous literature. We begin by presenting a parameterized complexity analysis of the $$\mathcal{N}\mathcal{P}$$ N P -hard problem of minimizing the total late work on a single machine. We do so with respect to the following four parameters: (i) the number of different processing times ( $$\upsilon _{p}$$ υ p ); (ii) the number of different due dates ( $$\upsilon _{d}$$ υ d ); (iii) the maximal processing time $$({p}_{\max });$$ ( p max ) ; and (iv) the maximal due date ( $$d_{\max }$$ d max ). We use results from the literature to conclude that the problem is hard with respect to (wrt.) parameter $$\upsilon _{d}$$ υ d and is tractable (i.e., solvable in FPT time) wrt. $$p_{\max }$$ p max . We then provide two FPT algorithms showing that the problem is also tractable wrt. to $$\upsilon _{p}$$ υ p and $$d_{\max }$$ d max . We continue by analyzing a single-machine scheduling problem with assignable due dates where the cost function to be minimized includes penalties due to weighted early and tardy work. We assume that each job can be assigned a different due-date, the value of which is subject to a job-dependent upper bound. We provide an efficient method to optimally assign due dates for a given job schedule. We then use this result to reduce the problem to a purely combinatorial problem, which we show is $$\mathcal{N}\mathcal{P}$$ N P -hard in general, but solvable in either FPT time or polynomial time for some special cases.

Keywords: Scheduling; Single machine; Late work; Due date assignment; Parameterized complexity (search for similar items in EconPapers)
Date: 2023
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/s10479-022-04806-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:322:y:2023:i:2:d:10.1007_s10479-022-04806-0

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

DOI: 10.1007/s10479-022-04806-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 ().