Precedence constrained scheduling to minimize sum of weighted completion times on a single machine

Precedence constrained scheduling to minimize sum of weighted completion times on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20003427
Country: Netherlands
Volume: 98
Issue: 1/2
Start Page Number: 29
End Page Number: 38
Publication Date: Nov 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: programming: linear
Abstract:

We consider the problem of scheduling a set of jobs on a single machine with the objective of minimizing sum of weighted completion times. The problem is NP-hard when there are precedence constraints between jobs. We provide an efficient combinatorial 2-approximation algorithm for this problem. In contrast to our work, earlier approximation algorithms achieving constant factor approximations are based on solving a linear programming relaxation of the problem. We also show that the linear ordering relaxation of Potts has an integrality gap of 2.

Reviews

Required fields are marked *. Your email address will not be published.