ND-agent scheduling of linear-deteriorating tasks with positional due indices to minimize total completion time and maximum cost

Rubing Chen, Jinjiang Yuan and Zhichao Geng

Applied Mathematics and Computation, 2020, vol. 365, issue C

Abstract: This paper investigates the ND-agent scheduling of linear-deteriorating tasks on a single machine with positional due indices. Under the ND-agent setting, there are two agents A and B and each agent X ∈ {A, B} has its set of tasks T(X), called X-tasks. Moreover, ND-agent means that T(A) and T(B) are allowed to be non-disjoint, which is a generalization of the traditional two-agent setting. Each task has a linear-deteriorating processing time and a positional due index. In this paper, we consider two problems: The first problem is to find a feasible schedule which minimizes the total completion time of the A-tasks under the condition that the maximum cost of the B-tasks is bounded by a threshold value. The second problem is the Pareto scheduling problem to minimize the total completion time of the A-tasks and the maximum cost of the B-tasks, simultaneously. We show in this paper that the two problems are solvable in O(n2) time and in O(n4) time, respectively. If the maximum cost of the tasks of agent B is restricted to some lateness-like criteria, for the version without the positional restriction, the time complexity for solving the above two problems can be reduced to O(nlog n) and O(n3log n), respectively. Our research includes a new technique for calculating the number of non-dominated points.

Keywords: ND-agent scheduling; Linear-deteriorating tasks; Due indices; Pareto scheduling (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319306897
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:365:y:2020:i:c:s0096300319306897

DOI: 10.1016/j.amc.2019.124697

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