Balanced number partitioning

Balanced number partitioning is a variant of <a href="/facts/Multiway_number_partitioning/6dUsX2HI">multiway number partitioning</a> in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers m, k. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.
An example application is <a href="/facts/Identical-machines_scheduling/lwNSXMs6">identical-machines scheduling</a> where each machine has a job-queue that can hold at most k jobs. The problem has applications also in manufacturing of <a href="/facts/VLSI/l1Wgqr27">VLSI</a> chips, and in assigning tools to machines in <a href="/facts/Flexible_manufacturing_system/9NMulLhl">flexible manufacturing systems</a>.
In the standard <a href="/facts/Optimal_job_scheduling/XyUejB6y">three-field notation for optimal job scheduling problems</a>, the problem of minimizing the largest sum is sometimes denoted by "P | # ≤ k | Cmax". The middle field "# ≤ k" denotes that the number of jobs in each machine should be at most k. This is in contrast to the unconstrained version, which is denoted by "
 
 
 
 P
 ∥
 
 C
 
 max
 
 
 
 
 {\displaystyle P\parallel C_{\max }}
 
".

Balanced number partitioning open-in-new

Balanced number partitioning