Single machine scheduling with two competing agents and equal job processing times

Daniel Oron, Dvir Shabtay and George Steiner

European Journal of Operational Research, 2015, vol. 244, issue 1, 86-99

Abstract: We study various two-agent scheduling problems on a single machine with equal job processing times. The equal processing time assumption enables us to design new polynomial-time or faster-than-known optimization algorithms for many problems. We prove, however, that there exists a subset of problems for which the computational complexity remains NP-hard. The set of hard problems includes different variations where the objective functions of the two agents are either minimizing the weighted sum of completion times or the weighted number of tardy jobs. For these problems, we present pseudo-polynomial time algorithms.

Keywords: Single machine scheduling; Two competing agents; Equal processing times; Complexity (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715000041
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:244:y:2015:i:1:p:86-99

DOI: 10.1016/j.ejor.2015.01.003

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