Single-machine scheduling with multi-agents to minimize total weighted late work

Shi-Sheng Li () and Jin-Jiang Yuan
Additional contact information
Shi-Sheng Li: Zhongyuan University of Technology
Jin-Jiang Yuan: Zhengzhou University

Journal of Scheduling, 2020, vol. 23, issue 4, No 6, 497-512

Abstract: Abstract We consider the competitive multi-agent scheduling problem on a single machine, where each agent’s cost function is to minimize its total weighted late work. The aim is to find the Pareto-optimal frontier, i.e., the set of all Pareto-optimal points. When the number of agents is arbitrary, the decision problem is shown to be unary $$\mathcal {NP}$$ NP -complete even if all jobs have the unit weights. When the number of agents is two, the decision problems are shown to be binary $$\mathcal {NP}$$ NP -complete for the case in which all jobs have the common due date and the case in which all jobs have the unit processing times. When the number of agents is a fixed constant, a pseudo-polynomial dynamic programming algorithm and a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate Pareto-optimal frontier are designed to solve it.

Keywords: Scheduling; Single machine; Multi-agent; Late work; Approximate Pareto-optimal frontier (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00646-7 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:23:y:2020:i:4:d:10.1007_s10951-020-00646-7

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

DOI: 10.1007/s10951-020-00646-7

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