3.2 Job Sequencing with Deadlines - Greedy Method

hi our next problem is job sequencing with deadlines this problem we are going to solve it using 3d method so first of all we will understand what the problem is already I have an example through an example we understand what the problem is then we will see how to solve it using 3d Matata so let us know about the problem see here in example 5 jobs are given 5 tasks are given and if that task is completed we will get this profit so associated with each job there is some profit but that job must be finished within this deadline it must be completed within the deadline like first job should be completed within a deadline - and deadline job do also - job tree is one select that every job is having some deadline so the problem is jobs are given every job is having some profit and if you complete the job you will get the profit and you have to complete that job within a deadline now let us understand what all these means assume that assume that there is a machine on that each job has to be processed each job takes one unit of time for completion this is the resolution this is the assumption in the problem right so what is this one unit I will assume this as one are so on a machine each job needs one R for its completion so you can take an example like a DTP operator or see mostly for making legal documents for on a bond paper we will find people in the market who will prepare documents suppose that preparation you take the job so he's a typist right and he completes each job in one arm that's so that example you can take now what is the situation let us understand see assume that in the morning he has opened the shop the moment he has opened the shop these five people are standing there for getting their jobs done all right so you have to take this situation to understand the problem and each person is having his own deadline he was saying that I want my job to be done first in first our only can you do it or not if you can do it do it and this person is saying that I am ready to wait for three yards not about my job needs only one heart but I am ready to do it for three years suppose this morning 9 o clock so you say ready to wait till 2 o'clock and he is ready to wait till 11 o clock and he's ready to wait till 10 o clock so whose job should be done first this job should be done further but what is the profit we are gaining if this job is done let us say this is rupees and we get just 10 rupees and if this job is done then we get 20 rupees so obviously which a job should be done first highest profit job should be done first yes now the problem is we warned the set of those jobs which can be completed within their deadlines such that the profit is maximized the profit is maximized so this is a maximization problem and what is the constraint in the problem job must be completed within the deadline all right so this is suitable for greedy method because it is an optimization problem it's a maximization problem so we can apply greedy Manhattan now let us solve this problem using grading method let us see how we can apply grading it hurt so first of all how many R's are available for that typist to complete the job see one of the person or two people are ready to weld till twelve o'clock or for three hours they are ready to wait so after that nobody is there suppose this is the only job that he have when he who has opened the shop and he has to complete this within their deadline how many slots he is having from zero to R two first are one unit of time and this R he can complete one job then first R two Sakina he can complete second job and second to third he can finish the third job so it means nobody is ready to wait beyond three units of time three yards so he has to finish jobs within these three slots only if I give the time this is nine o'clock to ten o'clock and this is ten o'clock eleven o'clock eleven to two a log-log now there are only three slots how many jobs he can do deadlines are giving just three slots so he can do only three jobs out of five he has to select just three so that the profit is maximum now if we apply greedy met her then on what basis we will select objects we will select the objects in the order of their maximum profit so first maximum profit and next maximum next maximum and so on so let us see how to solve this one who is having highest profit in this one so you can see already that the odd jobs are already arranged in the decreasing order of the profits so I have to consider them in the same order this is having highest profit now I will select this job for completion I will select it I do not perform it but in which slot I should do he is ready to wait for two units of time means he came at nine o'clock he's ready to wait till eleven o'clock and his job needs only one unit of time so let us do it in this slot now let us pick up the next job second highest profit is 15 and what's his deadline to now again go to one to two he's ready to wait till eleven two years of time but this is already occupied now see if there are any slots available on this side yes it is available so that job to here now let us select the next job third job its deadline is one can we do it let us see one means what zero to one within this no this slot is already gone so this job is rejected we cannot do this job so we have selected already these two jobs then what about this job this can be done because the deadline is three so he is ready to wait till two o'clock or third unit and every job links one unit of time remember that so we will do this in this slot so that's it and what about this job third or the reoccupied is there any slot free on this side no if there is no slot available there you can look for the slots in this side so there is no job slot available that's all we have a solution what are the jobs that we are going to do we are going to complete jobs to then sha1 and job for and in which sequence we have to do them so here both the jobs are having deadlines too so we can do them in sequence J 1 and J 2 then J 4 or else J 2 2 J 1 then J 4 we can complete them in any of these sequences so these are the sequence as possible for completing those jobs as both are ready to wait for to us total profit will be this job is 20 and this job is 15 and the profit of this job is 5 so it is 20 plus 15 plus 5 as 40 so the total profit that we gain will be 40 now let us solve this here I have a take a table now initially there is nothing and there is nothing in the solution and the profit is also 0 let us start first with job we will consider job to be considered first job I'll write one or j1 first job am considering and first job as the deadline is 2 we will assign a slot from 1 to 2 1 to 2 you remember we have the slots from 0 to 1 and 1 to and two to three because the maximum deadline is three here so these are the slots available now solution as this is included we have allotted this slot job one comes into this solution and what is the profit 20 is the profit so this first job is included then considered a second job J when I write J 2 can you assign a slot to this second job like j1 was here yes J 2 can come here so we will assign a slot from 0 to 1 and all that he want to do was already assigned to this once all the two slots are over you see and we have the solution J 1 and J 2 how much profit we have 20 plus the profit of the second job is 15 so this is 35 and just keeping it as it is now next job to be considered j-3 third job as deadline is 1 0 to 1 already occupied so no slot is a sign and everything remains the same and jobs are J 1 and J 2 only and this is 20 plus 15 only so this job is not included in the solution so next job J 4 J 4 so we can assign a slot 0 to 1 is already gone 1 to do is already gone J 4 can be done in slot 2 to 3 so this is J 4 so here we have 2 to 3 and the solution is having J 1 J 2 job for is selected and it is 5 and job 5 it cannot be selected so this remains same this remain same and this total will be 40 total will be 40 I have taken one more problem for solving this using greedy method as a problem for job sequencing with deadlines we have to follow greedy method so we decided that we will select the jobs in the degree in order of their profits and that's all we may be getting maximum profit but the constraint is they have to be finished in a deadline so how many deadlines are there here what is the maximum time we have to submit any job maximum time a job can be submitted as four so how many slots are available 0 to 1 then 1 to 2 2 to 3 3 to 4 maximum deadline for after that nobody's ready to wait if the job should be completed within that 4 units of time but every job needs just one unit of time so how many slots we have with one one unit four slots we have now let us solve this by selecting two jobs so the first job first job what is the deadline 3 is the slot vacant 2 to 3 then it's not beyond 3 so 2 to 3 years job 1 can be done and we got the profit 35 I'll write it just below this one then next job J 2 deadline is 4 so check 3 to 4 yes it's free it can be done so J 2 and the profit that we got is 30 then J 3 J 3 s deadline is for no 3 - 4 is already occupied then check this side if it can be done early yes already occupied here yes it can be done see this means that this person is ready to wait for 4 unit of time so for ours we can finish it early also we don't have to do it in 3 to 4 slot only we can finish it early also no doubt he is ready to it but that's not already we are doing it for somebody else so let us bring that one here so this third job can be done here and its profit is 25 now Jade for what is the deadline 1 - 2 - 1 - 2 or they do Cupid but can it be done early yes this slot is free so ja 4 can be done here and its profit is 20 now ja 5 job 6 and 7 I even don't have to check them because I see that all the slots are already occupied so those jobs cannot be completed so when we have limited slots and we have more jobs then we have to select the job such that the profit is maximum final profit is and all these it is 110 that's all the problem is very simple to solve right once you understand the problem then it's very easy to solve that's all about job sequencing a deadline

Channel: Abdul Bari

Views: 665,904

Keywords: algorithms, algorithm, greedy method, job sequencing, job sequencing with dealines, gate, bari, abdul bari

Id: zPtI8q9gvX8

Length: 13min 29sec (809 seconds)

Published: Wed Feb 07 2018