Minmax common due-window assignment and scheduling on a single machine with two competing agents
研究了单机环境下两竞争代理的共同到期窗口分配问题，目标是在限制B代理最大成本的前提下最小化A代理的最大成本，并给出了多项式时间解法。
We study the classical method of common due-date assignment and focus on minmax objective functions. In due-date assignment problems, the objective is to find the optimal due-date and job sequence that minimize the total earliness, tardiness and due-date-related costs. We extend the single-agent problem to a setting involving two competing agents and to a setting of multi-agent. In the two-agent setting (herein agents A and B), the scheduler needs to minimize the maximum cost of the agent A, subject to an upper bound on the maximal cost of the agent B. In the general model of multi-agent scheduling, the scheduler needs to minimize the cost among all A-type agents, subject to an agent-dependent upper bound on the maximal cost of the B-type agents. We further generalize the problems to the method of common due-window assignment. For all studied problems, we introduce efficient polynomial time solutions.