Affordable Access

Experimental comparison of approximation algorithms for scheduling unrelated parallel machines

Technische Universiteit Eindhoven
Publication Date
  • Computer Science


technische universiteit eindhoven Exp of al 5 Experimental comparison of approximation algorithms for scheduling unrelated parallel machines Tjark Vredeveld Cor Hurkens Department of Mathematics and Computing Science Technische Universiteit Eindhoven P.G.Box 513 5600 MB Eindhoven Abstract This paper presents an empirical comparison of polynomial-time ap- proximation algorithms and local search heuristics for the problem of min- imizing total weighted completion time on unrelated parallel machines. Algorithms with a worst-case performance guarantee are based on round- ing a fractional solution to an LP-rela....<ation or to a convex quadratic programming relaxation. We also investigate dominance relations among the lower bounds resulting from these relaxations. 1 Introduction In this paper, we make an experimental comparison of approximation algo- rithms for which we have constant performance bounds but no empirical ev- idence, and local search heuristics which exhibit good empirical behavior but for which we have no performance bounds. The former algorithms are so-called polynomial-time p-approximation algorithms, which are algorithms that com- pute a feasible solution in polynomial time whose value is within a factor p of the optimal solution value; p is called the performance guarantee of the algorithm. The problem under consideration is the problem of scheduling unrelated parallel machines so as to minimize the total weighted completion time. We are given a set of n jobs, J1 , ... , I n , each of which has to be scheduled without interruption on one of m machines, M 1 , .•. , M m , where m is part of the input. A machine can process at most one job at a time and all jobs and machines are available at time O. If a job Jj is processed on a machine Mi, it will take a positive integral pro~essing time Pij' Furthermore, for each job we are given a non-negative integral weight Wj' The objective is to schedule the jobs so that the sum of the we

There are no comments yet on this publication. Be the first to share your thoughts.