An Experimental Study of Algorithms for Weighted Completion Time Scheduling |
| |
Authors: | I D Baev W M Meleis A Eichenberger |
| |
Affiliation: | (1) Department of ECE, Northeastern University, Boston, MA 02115, USA. \{baev,meleis\}@ece.neu.edu., US;(2) Department of ECE, North Carolina State University, Raleigh, NC 27695, USA. alexe@eos.ncsu.edu., US |
| |
Abstract: | We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints,
P| prec|\sum w
i
C
i
. This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known
approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental
behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively
a range of weighted completion time scheduling algorithms.
We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show
that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find
schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We
then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for
the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark.
Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion
time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For
these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions
in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for
difficult optimization problems.
Received October 30, 1998; revised March 28, 2001. |
| |
Keywords: | , Experimental evaluation, Weighted completion time scheduling, Precedence constraints, Parallel machines, Compilers, |
本文献已被 SpringerLink 等数据库收录! |
|