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.

Time
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

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions