Issue RAIRO-Theor. Inf. Appl. Volume 42, Number 2, April-June 2008 Page(s) 237 - 252 DOI 10.1051/ita:2007032 Published online 25 September 2007

RAIRO-Theor. Inf. Appl. 42, 237-252 (2008)
DOI: 10.1051/ita:2007032

Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming

Maria Serna and Fatos Xhafa

Department of LSI, Universitat Politècnica de Catalunya, Campus Nord, Ed. Omega, C/Jordi Girona Salgado, 1-3, 08034-Barcelona, Spain; fatos@lsi.upc.edu

(Received March 17, 2004. Accepted December 24, 2006. Published online 25 September 2007.)

Abstract
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel approximablity of these problems, we show first a parallel additive approximation procedure to a subclass of multi-valued quadratic programming, called smooth multi-valued QP, which is defined by imposing certain restrictions on the coefficients of the instance. We use this procedure to obtain parallel approximation to dense instances of the two problems by observing that dense instances of these problems are instances of smooth multi-valued QP. The dense instances of the problems considered here are defined similarly as for other combinatorial problems in the literature. For such instances we can find in parallel a near optimal schedule. The definition of smooth multi-valued QP as well as the procedure for approximating it in parallel are of interest independently of the application to the scheduling problems considered in this paper.

Mathematics Subject Classification. 68W10, 68W25, 90B35, 90C20

Key words: Parallel approximation -- quadratic programming -- multiplicity scheduling problem


© EDP Sciences 2007

What is OpenURL?