Parallel approximation to high multiplicity scheduling problems <i>via</i> smooth multi-valued quadratic programming

作     者：Serna, Maria Xhafa, Fatos 

作者机构：Univ Politecn Cataluna Dept LSI ES-08034 Barcelona Spain 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2008年第42卷第2期

页      面：237-252页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：parallel approximation quadratic programming multiplicity scheduling problem 

摘      要：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.