Parallel-batching scheduling with two agents, release dates and equal processing times
研究在无界并行批处理机上，两个代理各有释放时间和相等处理时间的调度问题，针对三种变体（受限、线性组合、帕累托）给出多项式时间算法或NP-hard证明，并设计近似方案。
This paper investigates a two-agent scheduling problem with release dates and equal processing times on an unbounded parallel-batching machine. Each agent's scheduling criterion is regular and takes either the max-form or the sum-form. We address three variants of the problem. The first variant is the restricted version, which aims to determine a feasible schedule that minimises one agent's criterion while keeping the other agent's objective value not exceeding a specified upper bound. The second variant is the linear-combination version, which seeks to find a feasible schedule that minimises a linear combination of the criteria of both agents. The third variant is the Pareto version, which wants to identify all Pareto-optimal points and generate the corresponding Pareto-optimal schedules. When one agent's criterion is of the max-form, we present polynomial-time algorithms for all three variants. However, when both agents' criteria are of the sum-form, several variants of the problem are shown to be NP-hard. In the Pareto version under this scenario, we design a pseudo-polynomial-time algorithm and a (1,1+ϵ)-approximate Pareto-optimal frontier. For the restricted version, we provide a fully polynomial-time approximation scheme (FPTAS) as well as a super-dual FPTAS.