  We consider the weighted completion time minimization problem for capacitated
parallel machines, which is a fundamental problem in modern cloud computing
environments. We study settings in which the processed jobs may have varying
duration, resource requirements and importance (weight). Each server (machine)
can process multiple concurrent jobs up to its capacity.
  Due to the problem's $\mathcal{NP}$-hardness, we study heuristic approaches
with provable approximation guarantees. We first analyze an algorithm that
prioritizes the jobs with the smallest volume-by-weight ratio. We bound its
approximation ratio with a decreasing function of the ratio between the highest
resource demand of any job to the server's capacity.
  Then, we use the algorithm for scheduling jobs with resource demands equal to
or smaller than 0.5 of the server's capacity in conjunction with the classic
weighted shortest processing time algorithm for jobs with resource demands
higher than 0.5. We thus create a hybrid, constant approximation algorithm for
two or more machines. We also develop a constant approximation algorithm for
the case with a single machine. This research is the first, to the best of our
knowledge, to propose a polynomial-time algorithm with a constant approximation
ratio for minimizing the weighted sum of job completion times for capacitated
parallel machines.
