We consider the following scheduling problem. We have m identical machines, where each machine can accomplish one unit of work at each time unit. We have a set of n jobs, where each job j has s_j units of workload, and each unit workload could be executed on any machine at any time unit. A job is said completed when its whole workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time ∑ω_jC_j, where ω_j is the weight of job j and C_j is the completion time of job j. We first give a PTAS of this problem when m is constant. Then we study the approximation ratio of a greedy algorithm, Largest-Ratio-First algorithm. Any permutation is a possible outcome of this algorithm when ω_j = s_j for each job j, and for this special case we show that the approximation ratio depends on the instance size, i.e. n and m. Finally, when jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is 1 + (m-1)/(m+2).
展开▼
