Due date assignment and scheduling on a single machine with two competing agents

Du Juan Wang, Yunqiang Yin, Shuenn Ren Cheng, Edwin Tai Chiu Cheng, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

Abstract

We study a single-machine due date assignment and scheduling problem involving two agents each seeking to optimise its own performance. We consider three due date assignment methods, namely the common, slack and unrestricted due date assignment methods. For each due date assignment method, we consider two types of optimisation problem, namely a linear combination optimisation problem (minimising the total integrated cost of the two agents) and a constrained optimisation problem (minimising the objective of one agent, subject to an upper bound on the objective of the other agent). We present a polynomial-time dynamic programming algorithm to solve the linear combination optimisation problem, and show that the constrained optimisation problem is-hard in the ordinary sense and admits a fully polynomial-time approximation scheme.
Original languageEnglish
Pages (from-to)1152-1169
Number of pages18
JournalInternational Journal of Production Research
Volume54
Issue number4
DOIs
Publication statusPublished - 16 Feb 2016

Keywords

  • due date assignment
  • scheduling
  • two agents

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this