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.