Scheduling diverse job assignments while keeping tasks on time
Diverse Schedules for Makespan Minimization on Unrelated Machines
Data Structures and Algorithms
Summary
Scheduling jobs on machines where each job takes different times is hard, especially when conditions change. The authors look for not just one plan but multiple different plans that finish jobs around the same time. They show how to find many well-performing schedules that differ greatly from each other, giving options if some conditions change or new rules appear. However, they also prove that finding schedules that are very different in the strictest way is much harder. They provide new methods balancing schedule quality and diversity.
What this means in practice
- •For manufacturing planners: Create multiple distinct job schedules with guaranteed task completion times to handle uncertain processing or changing constraints in factories.
- •For cloud operations teams: Generate diverse resource allocation plans with bounded execution times to adapt quickly when workloads or priorities shift in cloud data centers.
A theory result. No direct application yet.
Authors
Sebastian Bruchhold, Matthias Mnich, Karolina Tammemaa, Morten Weber, Michalis Xefteris, Bart Zondervan
Abstract
We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with provable makespan guarantees and substantially different job assignments. Committing to a single schedule in advance may be undesirable. Processing times may be uncertain, and constraints or domain knowledge may emerge later, so $k$ schedules of similar quality offer meaningful alternatives. We measure pairwise diversity by the weighted Hamming distance between job assignments and study the two standard objectives in the diverse-solutions literature: max-sum diversity, which maximizes the total pairwise distance between schedules, 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 makespan approximation factor. For every feasible makespan target $T$, we can compute $k$ schedules of makespan at most $2T$ whose max-sum diversity is optimal among all $k$ schedules of makespan at most $T$. Therefore, we match the classic factor-$2$ makespan guarantee of Lenstra, Shmoys, and Tardos (Math. Prog., 1990) and preserve optimal diversity. For the max-min objective, we show that the diversity problem is inherently harder. Namely, we show that, even without makespan constraints, deciding whether three schedules of given pairwise diversity exist is NP-hard. We complete this with two complementary bicriteria approximation algorithms for every fixed $k$ and $\varepsilon \in (0,1)$. The first preserves almost all of the optimal max-min diversity with makespan at most $(3\lceil12/\varepsilon\rceil+1)T$. The second keeps the makespan arbitrarily close to the classic $2$ guarantee while achieving a $\frac{1}{2}(1-\varepsilon)$ fraction of the optimal max-min diversity.