Weighted Completion Times
Table of Contents
The Weighted Scheduling Problem
This is a look at the problem of arranging a schedule of jobs so that their completion times are lowest, while accounting for different priorities for each job.
Input: \(n\) jobs with positive lengths \(l_1, l_2, \ldots, l_n\) and positive weights \(w_1, w_2,\ldots,w_n\). The larger the weight, the higher the priority.
Output: A job sequence (the schedule) that minimizes the sum of the weight completion times \(w_1l_1 + w_2 l_2 + \cdots + w_n l_n\).
Completion Time
The output above is a little confusing (I'll have to re-write that later). What we're minimizing is the sum of completion times. A job's completion time is the total of all the times for the jobs that precede it as well as the time to finish the job. This means the completion time for the first job is the time to run that job, the completion time for the second job is the time for the first job plus the time for the second job, and so on.
Greedy Metrics
The greedy method for this problem involves finding a metric such that when the jobs are sorted by the metric they form the optimal schedule. One possible metric is the Greedy Difference which is the weight for a job minus the time the job takes (\(w_i - l_i\)).
Another possible metric is the Greedy Ratio which is the ratio of job-weight to job-length (\(\frac{w_i}{l_i}\)).