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

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.