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

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.

Keywords:

• scheduling
• two agents
• due date assignment

Acknowledgements

We thank the editor, an associate editor and anonymous referees for their helpful comments on earlier versions of our paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This paper was supported in part by the National Natural Science Foundation of China [91024029,71301022]; in part by the subproject of National Science and Technology Supporting Program of China [2013BAK02B06]; and in part by the Ministry of Science Technology (MOST) of Taiwan [grant number NSC 102-2221-E-035-070-MY3], [grant number MOST 103-2410-H-035-022-MY2].