Minimizing average flow-time under knapsack constraint

We give the first logarithmic approximation for minimizing average flow-time of jobs in the subset parallel machine setting (also called the restricted assignment setting) under a single knapsack constraint. In a knapsack constraint setting, each job has a profit, and the set of jobs which get scheduled must have a total profit of at least a quantity Π. Our result extends the work of Gupta et al. (2009) [8] who considered the special case where the profit of each job is unity. Our algorithm is based on rounding a natural LP relaxation for this problem. In fact, we show that one can use techniques based on iterative rounding.