Two-agent single-machine scheduling with unrestricted due date assignment

• This paper considers two problems of single-machine scheduling that involve two agents (agents A and B) and DIF due date assignment.
• The objective is to minimize the total cost associated with due date assignment and weighted number of tardy jobs subject on some measures of agent B.
• This paper discusses the complexity and develops polynomial or pseudo-polynomial solutions for the problems, respectively.

We address two scheduling problems arising when two agents (agents A and B), each with a set of jobs, compete to perform their respective jobs on a common machine, where the due dates of agent A’s jobs are decision variables to be determined by the scheduler. Specifically, the objective is to determine the optimal due dates for agent A’s jobs and the job sequence for both agents’ jobs simultaneously to minimize the total cost associated with the due date assignment and weighted number of tardy jobs of agent A, while keeping the maximum of regular functions (associated with each B-job) or the number of tardy jobs of agent B   below or at a fixed threshold. We prove that both problems are NPNP-hard in the strong sense and develop polynomial or pseudo-polynomial solutions for some important special cases.