Schedule Optimization

This is a very simple example of a greedy algorithm.

A common problem in computer science is scheduling tasks (aka jobs). For instance: threads on a CPU, lectures in a classroom, or meetings on a calender. Tasks typically have 2 attributes.

  1. Time
  2. Weight (priority)

A schedule is the order in which each task is completed.

Completion time = Sum of the lengths of the preceding jobs in a schedule ($S$) plus the length of the job ($j$) itself

The Objective Functions defines an “optimal schedule”. For the purposes here, optimal schedule is defined as the minimum sum of weighted completion times.

The goal is to minimize the weighted completion time over the entire schedule. Calculating the weighted completion time for each possible schedule would require calculating $n!$ different schedules. Therefore, a greed approach is optimal in this case.

Consider the case where jobs = [{l=5, w=10}, {l=5, w=20}, {l=5, w=5}]

  • The optimal schedule is [{l=5, w=20}, {l=5, w=10}, {l=5, w=5}] because it has the minimal sum of weighted completion times.

    Optimal Schedule:

      {l=5, w=20} {l=5, w=10} {l=5, w=5}
    Weighted Time 5*20 = 100 (5+5)*10 = 100 (10+5)*5 = 75
    Objective 100 200 275

    Suboptimal Schedule:

      {l=5, w=5} {l=5, w=10} {l=5, w=20}
    Weighted Time 5*5 = 25 (5+5)*10 = 100 (10+5)*20 = 300
    Objective 25 125 425
    • The reader is encouraged to check the other four cases if they are in doubt

Consider the case where jobs = [{l=20, w=5}, {l=5, w=5}, {l=10, w=5}]

  • The optimal schedule is [{l=5, w=5}, {l=10, w=5}, {l=20, w=5}] because it has the minimal sum of weighted completion times.

    Optimal Schedule:

      {l=5, w=5} {l=10, w=5} {l=20, w=5}
    Weighted Time 5*5 = 25 (5+10)*5 = 75 (15+20)*5 = 175
    Objective 25 100 275

    Suboptimal Schedule:

      {l=20, w=5} {l=10, w=5} {l=5, w=5}
    Weighted Time 20*5 = 100 (20+10)*5 = 150 (30+5)*5 = 175
    Objective 100 250 425
    • The reader is encouraged to check the other four cases if they are in doubt

Asymptotic Complexity

$O(n\log{n})$

Pseudo Code

schedule:
    J = set of n jobs with postive lengths and weights
    returns: job sequence that minimized the sum of weighted completion time
    order J by weight/length in descending order

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions