Strongly polynomial algorithms for the high multiplicity scheduling problem

A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, the authors study various high multiplicity problems of scheduling unit-time jobs on a single machine. They provide strongly polynomial algorithms for constructing optimal schedules with respect to several measures of efficiency (completion time, lateness, tardiness, the number of tardy jobs and their weighted counterparts). The algorithms require a number of operations that are polynomial in the number of groups rather than in the total number of jobs. As a by-product, the authors identify a new family of n×n transportation problems which are solvable in O(nlogn) time by a simple greedy algorithm.