Using quadratic programming to solve high multiplicity scheduling problems on parallel machines |
| |
Authors: | F Granot J Skorin-Kapov A Tamir |
| |
Affiliation: | (1) Faculty of Commerce and Business Administration, The University of British Columbia, VGT 1Z2 Vancouver, British Columbia, Canada;(2) W. A. Harriman School for Management and Policy, State University of New York at Stony Brook, 11794-3775 Stony Brook, NY, USA;(3) School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel |
| |
Abstract: | We introduce and analyze several models of schedulingn different types (groups) of jobs onm 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), anO(mn+n logn) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm
can be improved toO(m logm+n logn). These results can be extended to related unweighted models with variable processing requirements in which all the machines
are available at time zero.
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. |
| |
Keywords: | Scheduling Quadratic programming Parallel machines |
本文献已被 SpringerLink 等数据库收录! |
|