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

33 Citations (Scopus)

Abstract

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
Volume79
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this