Listing all delta partitions of a given set: Algorithm design and results

Abstract

Let α\alpha be a set of nn elements and δ\delta be a nonnegative integer. A δ\delta -partition of α\alpha is a set of pairwise disjoint nonempty subsets of α\alpha such that the union of the subsets is equal to α\alpha and every subset has a size greater than δ\delta . We formulate an algorithm for computing all δ\delta -partitions of a given nn-element set and show that the algorithm runs in O(n){\mathcal{O}}\left(n) space and O(n){\mathcal{O}}\left(n) delay time between any two successive outputs of δ\delta -partitions of the given set. An application of the notion of δ\delta -partitions is illustrated in the following scheduling problem. Suppose a factory has nn machines and m≤nm\le n jobs to complete daily. Every job can be accomplished by operating at least δ+1\delta +1 machines. A machine cannot work on multiple jobs simultaneously. According to a utilization policy of the factory’s management, no machine is allowed to be idle, so all machines should be running on some job. Find a daily schedule of the factory’s machines satisfying all the mentioned constraints. Let α\alpha be the set of the factory’s machines. Then, an α\alpha ’s δ\delta -partition with mm subsets is a legal schedule if every subset (in the δ\delta -partition) includes exclusively δ+1\delta +1 or more machines that run on the same job.

Keywords

• constrained set partitions
• listing algorithm
• delay time