Just-in-time scheduling with two competing agents on unrelated parallel machines

The objective of agent A is to maximize the weighted number of its just-in-time jobs that are completed exactly on their due dates, while the objective of agent B is either to maximize its maximum gain (income) from its just-in-time jobs or to maximize the weighted number of its just-in-time jobs. We provide a bicriterion analysis of the problem, which seek to find the Pareto-optimal solutions for each combination of the two agents׳ criteria. When the number of machines is part of the problem instance, both the addressed problems are NP-hard in the strong sense. When the number of machines is fixed, we show that the problem of maximizing agent A׳s weighted number of just-in-time jobs while maximizing agent B׳s maximum gain can be solved in polynomial time, whereas the problem of maximizing both agents׳ weighted numbers of just-in-time jobs is NP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.