Homework 2A: Weighted Scheduling Problem

 

Consider the following optimization problem regarding the sum of weighted completion-time:

Given n jobs J1, J2, ..., Jwhere for 1≤ k ≤ n each job Jk takes Tunits 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.