The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs

Rubing Chen, Jinjiang Yuan () and Yuan Gao
Additional contact information
Rubing Chen: Zhengzhou University
Jinjiang Yuan: Zhengzhou University
Yuan Gao: Zhengzhou University

Journal of Scheduling, 2019, vol. 22, issue 5, No 5, 593 pages

Abstract: Abstract In this paper, we revisit a two-agent scheduling problem on a single machine. In this problem, we have two competing agents A and B, which means that the job set of agent A and the job set of agent B are disjoint. The objective is to minimize the total completion time of agent A, under the constraint that the total number of tardy jobs of agent B is no larger than a given bound. The complexity of this problem was posed as open in Agnetis et al. (Oper Res 52:229–242, 2004). Leung et al. (Oper Res 58:458–469, 2010a, b. https://doi.org/10.1287/opre.1090.0744ec ) showed that the problem is binary NP-hard. However, their NP-hardness proof has a flaw. Here, we present a new NP-hardness proof for this problem. Our research shows that the problem is still NP-hard even if the jobs of agent A have a common processing time.

Keywords: Two-agent scheduling; Total completion time; Total number of tardy jobs (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0598-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:22:y:2019:i:5:d:10.1007_s10951-018-0598-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0598-5

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().