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.

This was so confusing !

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!

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"

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

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🙏🏻🙏🏻

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

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

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

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

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...

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).

sir what if you get the upper bound greater than previous do we need to kill that?

Sorry - I did not understand the logic behind the cost at a certain node being the penalty associated to the prior job skipped. Can someone explain the logic? Thank you.

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?

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

can't we jobs in different order, is it necessary to do in sequence

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

Thank you for your efforts

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...

sirdo you have any lecture on VRP using branch and bound algo

sir please make videos on tsp using branch and bound

Thnk q sir very nicely explained

How is ordering taken into account? The job order is always ascending down the depth of the tree. How would this find a solution where Job 4 comes before Job 2?

--doubt How do we come to know that we need to switch from cost and upper bound to time method?

Thank Sir Pass ho gaya exam ke pehle

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

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

Sir, I think your last logic is doesn't execute . Because node 9 J4 also have no time for last work as usual node 11 or 12. I can't find any difference in this three nodes. Sir, Please can you explain this....

Sir please provide job sequencing using lifo and fifo branch and bound

we have total 84 view can write book and consolidate all problems in one book. it is easy for us to review after watching this viedo

very nice explanation sir.... sir can you please suggest a good reference book for this subject..

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

Thank you.

But we don't check the feasibility of the minimum upper bound, then how can we kill the other nodes which have a greater upper bound?

Sir could you please make video again on this topic ,I didn't get the logic even I had watched for several times.. It looks some what difficult to understand

Sir , can you please explain how node 8 is feasible because the time required for job 1 and job 4 are the same and their deadlines are also the same .

Thank you sir❤❤❤

@Abdul Bari 8:47 isn't J3's deadline 2?

Sir, is its time complexity O(n!)?? If so, then why use this technique??? greedy was serving us better in O(n^2) time and was also giving the optimal solution each and every time..!

Does anyone have a working code for this? Literally can't find a solution for this anywhere.

How to do it if profits are given?

Is this topic have for 21 scheme🤔

Thank you!

We have got cost 0, we must do J1 ,J2 then why we are going for J2,J3?

is this FIFO branch and bound...............

Great explanation sir

big fan sir

i think the answer here is just j2 bcz forj3 we have already crossed te deadline

I don't understand when using time, could everybody explain in the comment? Thanks

Also. How is maximum time 3h. I couldnt get your logic sir.

sir, is it FIFOBB or LCBB ?

Where it's mentioned that total available time is 3 hrs?

Don't worry is u face trouble implementing it! It's an expert level problem!

Does anyone have the code for this?

what is the actual meaning of cost here ?? Here cost value is depend on order of jobs . the order in which we will perform the job. here doubt is==> "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." suppose here , if we exchange the order of job 2 and job 3. So now job 3 is processed in 2nd branch(node 1 to node 3) of tree and job 2 will be processed in 3rd branch(node1 to node 4) of tree. if u exchange, there will be no problem of time and deadline. My calculation says that this is not a good way to calculate cost in job sequencing with deadlines by branch and bound. we should keep track the time and deadlines at each node. And the cost calculation at each node in state space tree should depend on time and deadlines of each job.

Why did we even explore doing job 1 where penalty was more.

Can u explain me how to calculate u and c I am very confused? please replay me......

that's a very good explanation sir, but a little bit confusing, at last, I am trying to solve it,,,, >m=max(deadline);//maximum time slot >upperbound=999....; loop_____________________ >rs=m-T; //rs=remaining slot //T=time taken by the jobs which are already been done //update (rs) in each steps with (c) and (u) >c=remaining penalty before last job,taken >u=remaining penalties >if(upperbound>u) upperbound=u; _________________terminating condition ...(1) rm=0 (2)c>upperbound

Perfect

node 4 is kil

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

job 3 deadline is 2 then why you are mentioning job 3 deadline is 1

sir aap starting mei wrong ho galat baat

sabka badla lega tera faizal

Those who are having problem with the job 3's deadline.....can see this video also kzfaq.info/get/bejne/Y956rJt7lrirqGg.html No promotion just a student who face the same problem like you in this video. No offence Abdul Bari sir is a great teacher.

Sir in this during considering Job 3 its 10+5+3=18 you have considered 10+5=15 its wrong

Unclear.

sir are you fascist??? 🤌🤌🤌🤌