Due date assignment and scheduling on a single machine with two competing agents

Du-Juan Wang, Yunqiang Yin, Shuenn-Ren Cheng, T.C.E. Cheng and Chin-Chia Wu

International Journal of Production Research, 2016, vol. 54, issue 4, 1152-1169

Abstract: We study a single-machine due date assignment and scheduling problem involving two agents each seeking to optimise its own performance. We consider three due date assignment methods, namely the common, slack and unrestricted due date assignment methods. For each due date assignment method, we consider two types of optimisation problem, namely a linear combination optimisation problem (minimising the total integrated cost of the two agents) and a constrained optimisation problem (minimising the objective of one agent, subject to an upper bound on the objective of the other agent). We present a polynomial-time dynamic programming algorithm to solve the linear combination optimisation problem, and show that the constrained optimisation problem is -hard in the ordinary sense and admits a fully polynomial-time approximation scheme.

Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2015.1056317 (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:tprsxx:v:54:y:2016:i:4:p:1152-1169

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

DOI: 10.1080/00207543.2015.1056317

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().