# Schedule Optimization

Under Construction: Consider this content a preview of the real thing which is coming soon (hopefully).

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

$C_{j}(S)$

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

$\min\sum_{n}^{j=1}w_{j}C_{j}(S)$

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


Full Repo

Relevant Files: