An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems

摘要

Recently there has been much progress on the design of approximation algorithms for a variety of scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. Many of these approximation algorithms have been inspired by polyhedral formulations of the scheduling problems and their use in computing optimal solutions to small instances. In this paper we demonstrate that the progress in the design and analysis of approximation algorithms for these problems also yields techniques with improved computational efficacy. Specifically, we give a comprehensive experimental study of a number of these approximation algorithms for 1|r_j|∑w_jC_j, the problem of scheduling jobs with release dates on one machine so as to minimize the average weighted completion time of the jobs scheduled. We study both the quality of lower bounds given for this problem by different linear-programming relaxations and combinatorial relaxations, and the quality of upper bounds delivered by a number of approximation algorithms based on them. The best algorithms, on almost all instances, come within a few percent of the optimal average weighted completion time. Furthermore, we show that this can usually be achieved with O(nlog n) computation. In addition we observe that on most kinds of synthetic data used in experimental studies a simple greedy heuristic, used in successful combinatorial branch-and-bound algorithms for the problem, outperforms (on average) all of the LP-based heuristics. We identify, however, other classes of problems on which the LP-based heuristics are superior and report on experiments that give a qualitative sense of the range of dominance of each. We consider the impact of local improvement on the solutions as well. We also consider the performance of the algorithms for the average weighted flow-time criterion, which, although equivalent to average weighted completion time at optimality, is provably much harder to approximate. Nonetheless, we demonstrate that for most instances we consider that the algorithms give very good results for this criterion as well. Finally, we extend the techniques to a rather different and more complex problem that arises from an actual manufacturing application: resource-constrained project scheduling. In this setting as well, the techniques yield algorithms with improved performance; we give the best-known solutions for a set of instances provided by BASF AG, Germany.