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 language | English |
---|---|
Pages (from-to) | 1152-1169 |
Number of pages | 18 |
Journal | International Journal of Production Research |
Volume | 54 |
Issue number | 4 |
DOIs | |
Publication status | Published - 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