7.1 Job Sequencing with Deadline - Branch and Bound

Job Sequencing using Branch and Bound

Courses on Udemy
================
Java Programming

Data Structures using C and C++

C++ Programming

[anirudh]

Just to clear things out. The problem statement is that Pi stands for the penalty to be paid for not doing ith job before its deadline. So our goal is to try and do as many jobs possible before their deadlines and hence decrease our total penalty.
u = Total penalty for jobs not in solution. The jobs that are in solution are completed hence we don't pay for them. We must pay penalty for the remaining jobs. So u represents a max bound that this is the maximum penalty we have to ever pay. So this is like a lower bound.
c = Total penalty for job not is solution till now. So, the jobs that we have missed till now will never be done afterwards as well in this path. So we are sure that we must pay at least 'c' penalty if not more.
So, whenever we encounter a node with c>upper_bound we know that we have already missed jobs for which we have to give penalty more than the upper bound(worst case) of some other path. Hence we prune/discard this node.

[shlokakulkarni]

Gave an exam yesterday for which I had studied using your videos, and we had a 5 marker question on job sequencing. Turns out, it was this exact question, that you had taught so well! Very thankful for your amazing videos!

[kyusiv]

For all those having a doubt that if we do j2 -> j3, j3 cant be done as its d=2 and processing time for j2 is 2, so j3 cant be done, i think the explanation for that is as follows

Here in branch and bound you are just exploring the different combinations of jobs which will give the min penalties, that is why at 9:50, he says if we do j2 and j3 *together* take 3 units of time and deadline of j2 is 3. So it means a combination of j2 and j3 is giving you minimum penalty, order can be anything which satisfies deadline

[MaruhanPark]

At 1:36 it would be nice if you explain why we are using "upper bound" and "cost" because the relationship is not clear to me. For example, it's not entirely clear to me why we are tracking a "sum of penalties considering until the last job"

[shreechatane]

Thank you sir you covered our whole syllabus. I have been watching your playlist from the beginning and your explanations are butter smooth . I am very grateful for your videos🙏🏻🙏🏻

[LifeMadeEasy]

Thankyou sir...how fortunate you are as you have lot of blessings and positive vibes from all students...this blessings (gratitude) will always make you fly (inner lightness).

[WeillingHu]

At first level, why not discard J1 as well? U=19 which is greater than 14

[Si._k]

Sir isnt Job 3's deadline equal to 2? 9:04

[devalkathrecha]

6:30 in case of J1, J4 . Deadline of J4 is 1, then how can it be executed after J1 ???

[paulvanides]

I love all Abdul Bari's videos. I have gone through them and they are great. Regarding this solution however, is the order of doing jobs right in the state space tree? It seems to me that if you do job 2 first, then there would be no time to do job 3 because the deadline would have passed. It seems to me you need to do job 3 first, and then job 2. Is this a misinterpretation of the question or answer?

[MrVrtex]

i like all you videos and how you explain but I am seriously disappointed today. You taught like you were teaching yourself. Didn't understand a single logic. Please take into consideration that not all students studying here are quick to catch on like you. there are also slow learners. Hope that helps

[hotaru]

Sir can we do this with the help of Set Method like you told in "0/1 Knapsack Dynamic programming two method " video ?

[smaxiso]

09:33
when we are doing J2 first it takes 2 units of time. But J3's deadline is 2.
So how can we start J3 when J2 finishes at 2, which is J3's deadline.
In that case J3 will finish at 3 which is after it's deadline.
Someone explain this please...

[mridulkapil]

Thank you so much sir.
Because of you I can pass my engineering.
Love from Faridabad and EIT.
REGARDS
MRIDUL AND CSE-6B

[sauravchauhan]

In the left most part of tree ... cost is zero ...why have we not taken that sequence

[sayantansen]

Sir in J2 and J3 if the deadline are 3 and 2 .and time is 2 and 1
so, j2 job is done in 2 hr which has a deadline of 2 ..but then how is the next job (j3) is done? since 2 hrs are spend on j2 and the next job does not meet the deadline...

[hrhistory]

The sequence we got here is {J2, J3}but we need to get {J3, J2}

[saipraneeth]

Sir...i see no use of cost in this example...since if cost exceeds upper then upper bound also get exceeds..then why it is necessary to take that..i mean cost

[srivardhani]

very nice explanation sir...very nice....nice....

[Pritamdas-bgfp]

sir please make videos on tsp using branch and bound