Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work

Dvir Shabtay, Gur Mosheiov and Daniel Oron

European Journal of Operational Research, 2022, vol. 303, issue 1, 66-77

Abstract: Traditional scheduling models assume that due dates are predefined and the aim is to find a schedule that minimizes a given scheduling criterion with respect to the given set of due dates. A more recent trend consists of models that focus on coordinating two sets of decisions: due date assignment to customers and determining a job schedule. We follow this trend by analyzing a single machine scheduling problem, where the scheduler is tasked with assigning a common due date to all jobs in order to minimize an objective function that includes job-dependent penalties due to early and late work. We show that the problem is solvable in linear time if the common due date value is unbounded, and in O(nlogn) time if it is bounded from above. We then extend the analysis to the case where a common due window has to be assigned to all jobs. We show that when the location of the due window is unbounded, the problem is solvable in O(nlogn) time (and further in linear time if the length of the due window is unbounded as well). However, it becomes NP-hard when it is bounded. We complement our analysis by (i) providing a pseudo-polynomial time algorithm to solve this hard variant of the problem, and (ii) study two special cases of this hard variant that are solvable in polynomial time.

Keywords: Scheduling; Due date assignment; Due window assignment; Late work; Early work; Complexity analysis (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722001199
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:303:y:2022:i:1:p:66-77

DOI: 10.1016/j.ejor.2022.02.017

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