Homework 2A: Weighted Scheduling Problem
Consider the following optimization problem regarding the sum of weighted completiontime:
Given n jobs J_{1}, J_{2}, ..., J_{n }where
for 1≤ k ≤ n each
job J_{k} takes T_{k }units of time to complete and
has a priority weight W_{k}, you need to schedule these jobs in some
order one by one. No two jobs can overlap in time. As soon as one job finishes,
the next job in the schedule starts immediately according to the schedule. Time
starts from the time point 0 on the time line. If job J_{k.} starts at
time S_{k}, it will be completed at the time S_{k} +
T_{k}. Obviously the start time S_{k} and the finishing time S_{k} + T_{k
} for each job J_{k} depend
on the order of the jobs in the schedule. The goal is to find the schedule that
minimizes the sum of weighted completion time over the jobs:
∑ _{1≤ k ≤
n} W_{k} * (S_{k} + T_{k}) .
For example, the following is a concrete sample
problem instance.

Job 1 
Job 2 
Job 3 
Job 4 
Job 5 
Job 6 
Job 7 
Job 8 
Job 9 
Job 10 
W_{i} 
6 
7 
5 
7 
8 
2 
11 
9 
13 
11 
T_{i} 
4 
5 
2 
3 
6 
1 
10 
7 
8 
9 
(1) Spend at least one hour to think about different greedy criteria that may lead you to find optimal solutions for the scheduling problem above. Put down at least two different greedy criteria that you have considered.
(2) Apply each of the greedy criteria you have in (1) above to the sample problem instance. Report the solutions you get. After you implement the exhaustivesearch program in (3) below, check and report whether your greedy criteria lead you to the optimal solution.
(3) Write a program to find an optimal solution for this weighted scheduling problem through exhaustive search of all possible solutions. Check to see whether your greedy criteria in (2) above lead you to the optimal solution.
Note the following things:
(4) Submission: Fill out this selfevaluation report about your program, including your findings in Step 1, Step 2, and Step 3 into the selfevaluation report, and then submit the selfevaluation report and the your source code file(s) as single zip file under Canvas.