Single-machine two-agent scheduling involving a just-in-time criterion

Dvir Shabtay, Omri Dover and Moshe Kaspi

International Journal of Production Research, 2015, vol. 53, issue 9, 2590-2604

Abstract: We study a set of single-machine two-agent scheduling problems where the performance measure of the first agent, F1$ F_{1} $, is the weighted number of jobs completed exactly at the due date, i.e. completed in a just-in-time mode. The performance measure of the second agent, F2$ F_{2} $, is either the makespan, the total completion times or the weighted number of jobs completed exactly at the due date. For each combination of performance measures of the two agents, we study four different variations of the problem. We show that all four-problem variations are strongly NP$ \mathcal NP $-hard for when the performance measure of the second agent is either the makespan or the total completion time, even if all of the first agent’s weights are equal. We also study the special case of these problems where the job processing times of the second agent are all equal. For this special case, we prove that three variations of this problem are ordinary NP$ \mathcal NP $-hard with respect to the instance size, while all four problem variations are polynomial solvable with respect to the number of jobs. For the problem where the performance measure of both agents is the weighted number of jobs completed at the due date, we show that one problem variation is solvable in polynomial time, while all other three variations are ordinary NP$ \mathcal NP $-hard.

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

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.970706 (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:53:y:2015:i:9:p:2590-2604

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

DOI: 10.1080/00207543.2014.970706

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