We study makespan minimization on unrelated machines while constructing a set of diverse schedules. Traditional approaches output a single schedule, but in practice processing times may be uncertain or constraints may appear later, so $k$ schedules of comparable quality provide useful alternatives. Pairwise diversity is measured by the weighted Hamming distance between job assignments, and we consider the two standard objectives from the diverse‑solutions literature: max‑sum diversity, which maximizes the total pairwise distance, and max‑min diversity, which maximizes the smallest pairwise distance.
For the max‑sum objective we show that optimal diversity can be achieved in polynomial time without sacrificing the classic $2$‑approximation factor for makespan. Specifically, for any feasible makespan target $T$, we can compute $k$ schedules with makespan at most $2T$ whose max‑sum diversity is optimal among all $k$ schedules with makespan at most $T$. Thus we match the Lenstra‑Shmoys‑Tardos (1990) factor‑$2$ guarantee while preserving optimal diversity.
For the max‑min objective the problem is inherently harder. Even without makespan constraints, deciding whether three schedules with given pairwise distances exist is NP‑hard. For any fixed $k$ and any $\varepsilon\in(0,1)$ we provide two complementary bicriteria approximation algorithms. The first retains almost all of the optimal max‑min diversity while allowing makespan up to $(3\lceil12/\varepsilon\rceil+1)T$. The second keeps the makespan arbitrarily close to the classic factor $2$ guarantee and achieves a $\frac12(1-\varepsilon)$ fraction of the optimal max‑min diversity.
These results demonstrate that simultaneously pursuing quality and diversity in unrelated‑machine scheduling is feasible, yet the choice of diversity metric leads to markedly different algorithmic complexities.
Review