Resource scheduling with supply constraint and linear cost

We consider the following resource scheduling problem to minimize the total weighted completion time. There are m resources available at each time unit, and n jobs, each requiring an arbitrary number s _i of resources. Each resource can only be assigned to one job. The objective is to find a schedule that minimizes ∑ w _ic _i, where w _i is the weight/importance of job J _i and c _i is the time that job J _i receives all resources it requires. We show this problem is NP-hard when m is the input of the problem. We then give a simple greedy algorithm with 2-approximation ratio. Finally, we present a polynomial time algorithm with complexity O(n ^d+1) to solve this problem when the number of different resources requirements that are not multiples of m is at most d.