Optimal delivery time quotation to minimize total tardiness penalties with controllable processing times

Yaron Leyvand, Dvir Shabtay and George Steiner

IISE Transactions, 2010, vol. 42, issue 3, 221-231

Abstract: Scheduling problems with due date assignment and controllable processing times are studied in this paper. It is assumed that the job processing time is a linear function of the amount of resource allocated to the job, and all jobs share the same due date, which is a decision variable. The problems have many applications, e.g., in optimal delivery time quotation and order sequencing when outsourcing is an option. The quality of a schedule is measured by two different criteria. The first is the total weighted number of tardy jobs plus due date assignment cost, and the second one is the total weighted resource consumption. Four different problems for treating the two criteria are considered. It is shown that three of these problems are NP-hard in the ordinary sense, although the problem of minimizing an integrated objective function can be solved in polynomial time. A pseudo-polynomial time optimization algorithm is provided for the three NP-hard versions of the problem. A fully polynomial time algorithm for approximating a Pareto-optimal solution is also presented. Finally, important polynomially solvable special cases are highlighted.

Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1080/07408170903394322 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:42:y:2010:i:3:p:221-231

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/07408170903394322

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().