Two-Agent Scheduling with Preemptions and Just-in-Time Jobs

We consider a two-agent single-machine scheduling problem under the environment that preemptions are allowed for the jobs of agent 1. The objective is to minimize the weighted number of tardy jobs of agent 1, while the weighted number of just-in-time jobs for agent 2 is greater than or equal to a given threshold. We establish the computational complexities for various cases depending on whether processing times and weights of each agents are identical or arbitrary. We show that all cases are at most NP-hard in the ordinary sense by developing a pseudo-polynomial time algorithm for the most general case and proving the NP-hardness for some special cases. Furthermore, we investigate some conditions that make the problem polynomially solvable.