Balanced number partitioning

rdf:langString Balanced number partitioning

rdf:langString Balanced number partitioning is a variant of multiway number partitioning 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 identical-machines scheduling where each machine has a job-queue that can hold at most k jobs. The problem has applications also in manufacturing of VLSI chips, and in assigning tools to machines in flexible manufacturing systems. In the standard three-field notation for optimal job scheduling problems, 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 "".