Homework 2A: Weighted Scheduling Problem
Consider the following optimization problem regarding the sum of weighted completion-time:
Given n jobs J1, J2, ..., Jn where
for 1≤ k ≤ n each
job Jk takes Tk units of time to complete and
has a priority weight Wk, 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 Jk. starts at
time Sk, it will be completed at the time Sk +
Tk. Obviously the start time Sk and the finishing time Sk + Tk
for each job Jk 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 Wk * (Sk + Tk) .
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 |
Wi |
6 |
7 |
5 |
7 |
8 |
2 |
11 |
9 |
13 |
11 |
Ti |
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 exhaustive-search 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 self-evaluation report about your program, including your findings in Step 1, Step 2, and Step 3 into the self-evaluation report, and then submit the self-evaluation report and the your source code file(s) as single zip file under Canvas.