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

Yunqiang Yin, Edwin Tai Chiu Cheng, Xiaoqin Yang, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

38 Citations (Scopus)


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 NP-hard in the strong sense and develop polynomial or pseudo-polynomial solutions for some important special cases.
Original languageEnglish
Pages (from-to)148-155
Number of pages8
JournalComputers and Industrial Engineering
Publication statusPublished - 1 Jan 2015


  • Due date assignment
  • Scheduling
  • Single machine
  • Two agents

ASJC Scopus subject areas

  • General Computer Science
  • General Engineering


Dive into the research topics of 'Two-agent single-machine scheduling with unrestricted due date assignment'. Together they form a unique fingerprint.

Cite this