We introduce and analyze several models of scheduling
n different types (groups) of jobs on
m parallel machines, where in each group all jobs are identical. Our main goal is to exhibit the usefulness of quadratic programming
approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the
minimization criterion. We develop polynomial algorithms for some models, and strongly polynomial algorithms for certain special
cases. In particular, the model in which the weights are job independent, as well as the generally weighted model in which
processing requirements are job independent, can be formulated as an integer convex separable quadratic cost flow problem,
and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specifically,
for the weighted model with job-independent processing requirements if we restrict the weights to be machine independent (while
still assuming different machine speeds), an
O(
mn+n log
n) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm
can be improved to
O(
m log
m+n log
n). These results can be extended to related unweighted models with variable processing requirements in which all the machines
are available at time zero.
Key Words Scheduling - Quadratic programming - Parallel machines
Communicated by N. Megiddo.
The research of Frieda Granot was partially supported by Natural Sciences and Engineering Research Council of Canada Grant
5-83998. The research of Jadranka Skorin-Kapov was partially supported by National Science Foundation Grant DDM-8909206.