USING QUADRATIC-PROGRAMMING TO SOLVE HIGH MULTIPLICITY SCHEDULING PROBLEMS ON PARALLEL MACHINES

We introduce and analyze several models of scheduling n different type s (groups) of jobs on m parallel machines, where in each group all job s are identical. Our main goal is to exhibit the usefulness of quadrat ic programming approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the mi nimization criterion. We develop polynomial algorithms for some models , and strongly polynomial algorithms for certain special cases. In par ticular, the model in which the weights are job independent, as well a s the generally weighted model in which processing requirements are jo b independent, can be formulated as an integer convex separable quadra tic cost Bow problem, and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specif ically, for the weighted model with job-independent processing require ments if we restrict the weights to be machine independent (while stil l 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 s peed, 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 wi th variable processing requirements in which all the machines are avai lable at time zero.