I want to run $k$ programs distributed on $N$ machines. Because of resource constraints, a machine can have at most $p$ of the $k$ programs installed. To have a balanced system, I can install each of the $k$ programs on the same number of machines, that part is easy.

My problem is how can I do that while minimizing the number of machines having any 2 programs installed. In other words, if I run 2 of those programs, I want to avoid having them run on the same set of machines while some other machines in the cluster are doing nothing.

In terms of sets, the questions becomes how to find $k$ subsets of a set of $N$ elements such that

1. any element is in $p$ subsets and
2. the maximum size of the intersection of any 2 subsets is minimized.

Any pointers / heuristic approach is appreciated.

• It looks to me like you're looking for something related to BIBDs. – mhum Sep 21 '15 at 21:04
• Your problem is related to scheduling theory, the case of parallel machines. You can find some useful hints in Scheduling Theory books such as this springer.com/us/book/9781461419860 – Rupei Xu Sep 22 '15 at 7:27