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

•This paper considers JIT scheduling with two agents on unrelated parallel machines.•Each agent desires to maximize the maximum weight or weighted number of its JIT jobs.•Two problems that seek to find the Pareto-optimal solutions are investigated.•The computational complexity status and efficient solution procedures are provided.

This paper considers two-agent just-in-time scheduling where agents A and B have to share m unrelated parallel machines for processing their jobs. 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 NPNP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NPNP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.