$1.[40$ points$]($U&G$-$required$)$

Consider the following scheduling problem: a single processing resource can handle jobs

from multiple customers. For each customer i$,$ we know that their job will take ti time to

be processed on the resource. Given an ordering of jobs from customers $($a schedule$),$ we

denote with Fi the time when job i has finished. For example, if there is only one job, F$1=$

t$1.$ If there are two jobs, scheduled in the order job $1$ and immediately afterwards job $2,$

then F$2=$ F$1+$ t$2.$ Each customer has a weight wi that represents how important they are

for the company. The happiness of customer i is expected to be dependent on the finishing

time of i$$s job. Thus, the company decides to order the jobs to minimize the weighted sum

of the finishing times, $=$

$$

$=1.$

Design an efficient algorithm to solve this problem: given a set of n jobs with a processing

time ti and a weight wi for each job, order the jobs in such a way to minimize the weighted

sum of the finishing times, $$

$$

$=1.$

Example. Assuming two jobs with time t$1=2$ and weight w$1=5,$ and t$2=4$ and w$2=1.$

$$ Schedule $1$: job $1$ then job $2$: F $=2*5+(2+4)*1=10+6=16$

$$ Schedule $2$: job $2$ then job $1$: F $=4*1+(4+2)*5=4+30=34$

Note: you have to prove that your strategy yields the optimal solution.