我们研究在无关机器上进行 makespan 最小化，同时构造多样化的调度集合。传统只输出单一调度，但实际中处理时间不确定或约束可能后续出现，$k$ 个质量相近的调度能提供备选。我们用作业分配的加权 Hamming 距离衡量两两多样性，并关注文献中的两种目标：最大总距离（max‑sum）和最大最小距离（max‑min）。
对于 max‑sum 目标，我们证明在保持经典 $2$‑近似 makespan 保证的前提下，可在多项式时间内得到最优多样性。具体地，对于任意可行的 makespan 上限 $T$，我们能构造 $k$ 条 makespan \le 2T 的调度，使其 max‑sum 多样性在所有 makespan \le T 的 $k$ 条调度中达到最优。于是我们同时匹配 Lenstra、Shmoys、Tardos (1990) 的 $2$‑因子保证并保留最优多样性。
对于 max‑min 目标，问题本质更难。即使不加 makespan 限制，判断是否存在三条满足给定两两距离的调度已是 NP‑hard。针对固定的 $k$ 和任意 \varepsilon\in(0,1)\，我们给出两种互补的双准则近似算法。第一种在 makespan \le (3\lceil12/\varepsilon\rceil+1)T 的前提下，几乎保留全部最优 max‑min 多样性。第二种将 makespan 保持在任意接近经典 $2$ 的因子，同时获得 \frac12(1-\varepsilon) 的最优 max‑min 多样性比例。
这些结果表明，在无关机器调度中同时追求质量和多样性是可行的，但不同的多样性度量导致算法复杂度差异显著。
点评