Minimizing the total weighted completion time of fully parallel jobs with integer parallel units

We consider the total weighted completion time minimization in the following scheduling problem. There are m identical resources available at each time unit, and n jobs. Each job requires a number s_i of resources and one resource can only be assigned to one job at each time unit. Each job is also called fully parallel such that the job is satisfied once it receives enough resources no matter how the resources distribute. The objective is to find a schedule that minimizes Σw_iC_i , where w_i is the weight of job J_i and C_i is the time when job J_i receives s_i resources. We show that the total weighted completion time minimization is NP-hard when m is an input of the problem. We then give a simple greedy algorithm with an approximation ratio 2. Finally, we present a polynomial time algorithm with complexity O(n^d+1) to solve this problem when the number of different resource requirements that are not multiples of m is at most d.