Optimal restricted due date assignment in scheduling

Dvir Shabtay

European Journal of Operational Research, 2016, vol. 252, issue 1, 79-89

Abstract: In classical scheduling problems it is common to assume that the due dates are predefined parameters for the scheduler. In integrated systems, however, due date assignment and scheduling decisions have to be carefully coordinated to make sure that the company can meet the assigned due dates. Thus, a huge effort has been made recently to provide tools to optimally integrate due date assignment and scheduling decisions. In most cases it is common to assume that the assigned due date(s) are not restricted. However, in many practical cases, assigning due dates too far into the future may violate early agreements between the manufacturer and his customers. Thus, in this paper we extend the current literature to deal with such a constraint. This is done by analyzing a model that integrates due date assignment and scheduling decisions where each job may be assigned a different due date whose value cannot exceed a predefined threshold. The objective is to minimize the total weighted earliness, tardiness and due date assignment penalties. We show that the problem is equivalent to a two stepwise weighted tardiness problem, and thus for a large set of special cases it is strongly NP-hard, even when the scheduling is done on a single machine. We then provide several special cases that can be solved in polynomial time, and present approximation results for a slightly modified (and equivalent) problem on various machine settings.

Keywords: Scheduling; Due date assignment; Approximation algorithms; Earliness; Tardiness (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715011820
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:252:y:2016:i:1:p:79-89

DOI: 10.1016/j.ejor.2015.12.043

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