Question

We have n activities. Each activity requires ti time to complete and has deadline di . We would like to schedule the activities to minimize the maximum delay in completing any activity; that is, we would like to assign starting times si to all activities so that max1 <= i <= n{âi} is minimized, where âi = fi â di is the delay for activity i and fi = si + ti is the finishing time for activity i. Note that we can only perform one activity at a given time (if activity i starts at time si , the next scheduled activity has to start at time fi).

For example, if t =< 10, 5, 6, 2 > and d =< 11, 6, 12, 20 >, then the optimal solution is to schedule the activities in the order < 2, 1, 3, 4 > to obtain starting/finishing times s/f =< 5/15, 0/5, 15/21, 21/23 > and achieve a maximum delay of 9 (for the third activity).
(A) State and prove the greedy choice property for this problem.

Answer 1

Explanation:

we'll begin by giving some introduction on the greedy choice property.

Greedy choice property :

As we have to minimize the maximum delay i.e finish time - deadline. To begin, we have to complete the job first which has the smallest deadline, then the next smallest and so on. If two jobs have same deadline, we then choose the job which has lesser time.

From the example given, the deadline for jobs are thus:

job1 => 11,

job2 => 6,

job3 =>12,

job4 =>20

sorting them according to the deadline gives;

job 2 => 6, job 1 => 11, job 3 =>12, job 4 =>20

therefore 2 1 3 4 is the optimal solution.

proof:

According as the greedy choice property, it says local optimal leads to the global minimum. From the question given, we are choosing a job with less deadline. Say the deadline is greater than the finish time we are skipping the jobs. Finally this helps us to minimize the maximum delay.