Due date assignment and scheduling on a single machine with two competing agents
研究了单机上两个竞争代理的截止日期分配与调度问题，针对三种分配方法，提出了线性组合优化问题的多项式时间算法，并证明约束优化问题是NP难的且存在完全多项式时间近似方案。
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.