Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost

Long Wan, Jinjiang Yuan and Lijun Wei

Applied Mathematics and Computation, 2016, vol. 273, issue C, 912-923

Abstract: This paper investigates the Pareto optimization scheduling problem on a single machine with two competing agents A and B in which agent A wants to minimize the number of tardy A-jobs and agent B wants to minimize the maximum cost of B-jobs. In the literature, the constrained optimization problem of minimizing the number of tardy A-jobs under the restriction that the maximum cost of B-jobs is bounded is solved in polynomial time. This implies that the corresponding Pareto optimization scheduling problem can be solved in a weakly polynomial time. In this paper, by presenting a new algorithm for the constrained optimization problem, we provide a strongly polynomial-time algorithm for the corresponding Pareto optimization scheduling problem. Experimentation results show that the proposed algorithm for the considered problem is efficient.

Keywords: Scheduling; Two-agent; Due date; Pareto optimization (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315014101
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:apmaco:v:273:y:2016:i:c:p:912-923

DOI: 10.1016/j.amc.2015.10.059

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().