Single Machine Two-Agent Scheduling Involving a Just-in-Time Criterion

We study a set of single machine two-agent scheduling problems where the performance measure of the first agent, F₁, is the weighted number of jobs completed exactly at the due date, i.e., completed in a just-in-time mode. The performance measures of the second agent, F₂, is either the makespan, the total completion times or the weighted number of jobs completed exactly at the due date. For each combination of performance measures of the two agents, we study four different variations of the problem. We show that all four problem variations are strongly NP-hard for when the performance measure of the second agent is either the makespan or the total completion time, even if all of the first agent`s weights are equal. We also study the special case of these problems where the job processing times of the second agent are all equal. For this special case we prove that three variations of this problem are ordinary NP-hard with respect to the instance size, while all four problem variations are polynomial solvable with respect to the number of jobs. For the problem where the performance measure of both agents is the weighted number of jobs completed at the due date, we show that one problem variation is solvable in polynomial time, while all other three variations are ordinary NP-hard.