Average Completion Time

Recall the problem as stated below.

Given

a set $S=\{a_1,a_2,$cdots,$a_n\}$ of tasks, where task $a_i$ requires $p_i$ units of processing time to complete.

A computer that can only handle one task at a time

Let $c_i$ be the completion time of task $a_i,$ i$.$e$.,$ the time at which task $a_i$ competes

Goal:

minimize the average completion time $=\frac{c_1+c_2+\text{d}\text{o}\text{t}\text{s}+c_n}{n}$

Example:

$S=\{a1,a2\}$ with $p_1=3,p_2=5$

Scheduling: $a_1,a_2{c}_1=3,c_2=8c=5\mathrm{.}5$

Scheduling: $a_2,a_1{c}_1=8,c_2=5c=6\mathrm{.}5$

Now consider the following example:

$S=\{a_1,a_2,a_3,a_4\}$ with the process time as $\{9,3,5,2\}.$

What is the minimal average completion time?

Question $4$

Average Completion Time $($Cont$.)$

Now if our goal is to Minimize Average Waiting Time for the same problem, what will be the minimal average waiting time?

$($Fill in the answer in the form of $x.)$

Given

a set $S=\{a_1,a_2,$dots,$a_n\}$ of tasks, where task $a_i$ requires $p_i$ units of processing time to complete.

A computer that can only handle one task at a time

Let $w_i$ be the waiting time of task $a_i,$ i$.$e$.,$ the time at which task $a_i$ starts working.

Goal:

minimize the average waiting time $w=\frac{w_1+w_2+\text{d}\text{o}\text{t}\text{s}+w_n}{n}$

Example:

$S=\{a_1,a_2\}$ with $p_1=3,p_2=5$

Scheduling: $a_1,a_2{w}_1=0,w_2=3w=1\mathrm{.}5$

Scheduling: $a_2,a_1{w}_1=5,w_2=0w=2\mathrm{.}5$