7.1 Job Sequencing with Deadline - Branch and Bound
Вставка
- Опубліковано 2 жов 2024
- Job Sequencing using Branch and Bound
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
This was so confusing !
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
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.
tompr
I would like to acknowledge your contributions, which have not gone unnoticed
@@Lullurluli I would like to acknowledge your acknowledgement for my contribution, which have not gone unnoticed. My job here is done. My comment has fulfilled its purpose.
op topi popi
@@anirudh7137 app mumbai asakte ho
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"
If you understood this thing, Kindly explain here too
Sir isnt Job 3's deadline equal to 2? 9:04
Anyways we can't traverse that node
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
6:30 in case of J1, J4 . Deadline of J4 is 1, then how can it be executed after J1 ???
At first level, why not discard J1 as well? U=19 which is greater than 14
because at beginning u=infinity and after j1, u =19 so 19 is less than infinity so it not discarded.
Those who are having problem with the job 3's deadline.....can see this video also ua-cam.com/video/-xJy8J1RGx4/v-deo.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.
thanks bro
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!
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...
yeah man, j3 can't do it, he messed up.
I think this algorithm only use to know which job we need to take and which not, to get minimum penalty. So in this case, J2 and J3 is taken and the finish order is J3 first and then J2. So the jobs finished on time (at 3 unit of time)
Unclear.
yeah...
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 are you fascist??? 🤌🤌🤌🤌
Sir can we do this with the help of Set Method like you told in "0/1 Knapsack Dynamic programming two method " video ?
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...
The sequence we got here is {J2,J3}but we need to get {J3,J2}
In the left most part of tree ... cost is zero ...why have we not taken that sequence
time matter
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?
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).
So nice of you Avinash
i think the answer here is just j2 bcz forj3 we have already crossed te deadline
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
can't we jobs in different order, is it necessary to do in 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....
Can you succeeded in finding the difference, I'd like to know about it.
Thank you sir❤❤❤
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.
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?
I have same question .. can someone tell?
Yeah the algorithm seems flawed
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.
--doubt
How do we come to know that we need to switch from cost and upper bound to time method?
when the total time exceeds the maximum deadline time then we should not do further calculations.Time is just to check whether we sholuld calculate further or not.
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
check how jobs & time should be calculated or considered here ua-cam.com/video/zPtI8q9gvX8/v-deo.html
sir what if you get the upper bound greater than previous do we need to kill that?
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
Don't worry is u face trouble implementing it! It's an expert level problem!
job 3 deadline is 2 then why you are mentioning job 3 deadline is 1
sirdo you have any lecture on VRP using branch and bound algo
@Abdul Bari 8:47 isn't J3's deadline 2?
exactly
sir please make videos on tsp using branch and bound
sir aap starting mei wrong ho galat baat
How to do it if profits are given?
Is this topic have for 21 scheme🤔
is this FIFO branch and bound...............
Thank Sir Pass ho gaya exam ke pehle
We have got cost 0, we must do J1 ,J2 then why we are going for J2,J3?
because of minimalization of pinalty value
Also. How is maximum time 3h. I couldnt get your logic sir.
Where is it
big fan sir
Where it's mentioned that total available time is 3 hrs?
check how jobs & time should be calculated or considered here ua-cam.com/video/zPtI8q9gvX8/v-deo.html
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..!
@@abdul_bari Thanks Sir.. :)
Greedy doesn't work on this problem since there is the time constraint here along with the deadline. For example, using the example above change the 5 to a 6 and the 3 to a 2. With the greedy approach it would get 6, then it get the other 6, then it would get the 2 since it doesnt have capacity for the 10. This is assuming we are picking greedily based on the per unit of work (divide the penalty by the time it takes to do). If we don't do it that way it also fails. To prove that, just change the time it takes for 10 to complete to 3, then when you greedily choose 10 thatat's all you can take. Whereas if you chose the other 3 you would have 14.
Does anyone have a working code for this? Literally can't find a solution for this anywhere.
Have you found the code for this?
Thank you!
Sir please provide job sequencing using lifo and fifo branch and bound
Why did we even explore doing job 1 where penalty was more.
penalty was 0 and upper bound was infinity we had to explore it.
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?
Abdul Bari That means, before updating the upper bound, we need to check if the jobs can meet their deadlines right?
yes
sabka badla lega tera faizal
node 4 is kil
Does anyone have the code for this?
google bro
Thank you so much sir.
Because of you I can pass my engineering.
Love from Faridabad and EIT.
REGARDS
MRIDUL AND CSE-6B
Job lag gyi kya ?
@@my_j.a.r.v.i.s. job lag gyi kya ?
@Jgkioskenkal Bhai Mai abhi third year me hu , next year puch mere se
Can u explain me how to calculate u and c I am very confused? please replay me......
i was going to comment the same, did you get the answer?
very nice explanation sir.... sir can you please suggest a good reference book for this subject..
Thnk q sir very nicely explained
Thank you for your efforts
very nice explanation sir...very nice....nice....
I don't understand when using time, could everybody explain in the comment? Thanks
*anybody
@@rezaadventures check how jobs & time should be calculated or considered here ua-cam.com/video/zPtI8q9gvX8/v-deo.html
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 .
it's infeasible
Cause of penalties
Thank you.
Perfect
sir, is it FIFOBB or LCBB ?
@@mahaboobbasha2337 fifo
fifo
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
all of yours algorithm videos are best
Great explanation sir
Sir in this during considering Job 3 its 10+5+3=18 you have considered 10+5=15 its wrong