Sequencing and Scheduling - Johnson's Algorithm

you so let's look at some of these things that I'm going to be using the same terminology that I'm going to be using for three machine ends and so on different textbooks use different terminology but because I want you to become familiar with this terminology that's what we are going to be using first of all ji JA I and let's write one two three four five six seven eight job problem then we will use the terminology AI to represent the processing time on the first machine ABCD so a odd is the processing time on the first machine so let's put five the eye is used to represent the processing time on the seconds so let's put some numbers in here for so this is representing a8 job to machine low shot problem and for that we have Johnson's algorithm to solve the problems the way that Johnson's algorithm works is very very very simple only two step first you have eight jobs so the sequence that we are going to be using has eight slots that need to be filled 1 2 3 4 5 6 7 so one of these jobs are going to be scheduled here here here and so the next step is to look at all these processing times both AI and bi both of them and find the minimum number minimum processing time in here the minimum processing time is warning here and there is no other minimum then when you find the minimum based on whether that minimum is on the first machine or on the second machine you will schedule it in this sequence for this the minimum processing time is on the first machine if it is on the first machine you schedule that early in the sequence first in the sequence so that is j7 so you schedule j7 in here as you schedule one job you will eliminate that job from for the consideration then you will look at the others there is one job in here and there is another job in here with the processing time off to this one this is an arbitrary choice whatever you want to select first it doesn't make any difference in here as you will see it's tubing here and it is on the first machine so you will schedule it first so the story is scheduled the next slot available it is j-3 so so this is eliminated from consideration now you have this job and it is on the second machine so it is a schedule laughs so this is j6 will be scheduled the last of the set so that's the other not if it happens that both of them were on the same machine then you have a choice you can either put them in here or any doesn't make any difference so the next one choose none we have a three in here if being here and others on the second machine so Google schedule j2 you need and you will continue this process until all jobs are exhausted next one is four and we have two fours to the next one five on the first machine and one on the second so J 1 goes in here J 5 goes in here notice that there was another floor but that's already gone it's no longer available so there are two more jobs and this is the minimum that's the minimum so j8 closed last and the last one of course is je for each ghost so this is my sequence that sequence says send these jobs in the same order on the machine so send job seven to machine one when it finishes take it to the machine to do you cannot start both of them at the same time these were the basic requirements that we introduced last time no job can be processed on two separate machines at the same time no machine can process two different jobs at the same time so these were some of the things that we introduced last time but anyway now let's look at the scan shot for the Gantt chart game and one machine 1 and M 2 machine 2 and this is of course time okay so we are going to schedule them the same way the PM job seven is one and four so anybody finished that that's j7 and that's j7 on the second machine and some of the terminologies as we going through what is the completion time I have already a scheduled job seven on two machines what is the completion time on the first machine one okay completion time on the first machine is one what is the completion time on the second machine is fine so it is 1 plus 4 which is 5 then we will a scheduled j-3 J 3 is 2 & 5 J 3 is 2 so it's going to come down here that's J 3 2 + 5 + 5 is going to go here that's J 3 to additional terminology one is idle time there is no idle time needed a machine one ever you can a scheduler right now for each other a machine to is a different story it depends on when this job finishes right now this was - and this machine was working so there was no need for the idle time it just had to meet it had to wait until second machine finishes its processing and the moment that it finished it was just sitting there waiting for this so it just started its work so there wasn't a wider time on the second machine but let's assume that this number was 10 so it would come all the way down here and this machine would finish and we'll wait for the job tree to come down so those idle times are very significant that are entered in here because this is my last machine if I enter any idle time in here if I have to incur the idle time in here what would happen to the end of the process it just keeps increasing so the idea is to avoid idle times so when you write this in terms of love mathematical rubbing minimization is to minimize desirable time if these other times are minimized then you are the bestest schedule so j-3 in here so what is the competition if if I had only these two jobs if I had only these two jobs what would be the completion on the first machine 1 X 2 is 3 X 3 and what is the completion time on the second machine is 1 plus 4 plus 5 is 10 what does that want that idle time in here that this machine has to wait until job 7 comes down what is the completion time of the schedule if you only have these two jobs 10 so the completion time of the schedule is the completion time of the last machine let's always keep that in mind because it becomes more complicated as we go through girls so it's the last machine that is playing a significant role in what the completion time of the schedule is and our intention is to minimize the completion time of this cake so job 5 so 5 is 4 and 10 you you and job six jobs six is nine and two nine and 33 is 42 so it's coming and that was 38 so it's coming in here it's coming in here at 42 and as you notice now this job is going to come right after this one with the machine has to so the resin idle time in here because it finished at 38 and it has to wake up for this job to come to be available so that's two coming down here which will make it 44 completion time on the first machine is 42 completion time on the second machine is 44 and completion time of the schedule is also 44 and this schedule is up

Channel: DrSalimian

Views: 32,771

Keywords: Dr. Masud Salimian, Industrial Engineering, Morgan State University, Operations Research, Sequencing and Scheduling Problems, Job Shop scgeduling Problem, Flow Shop Scheduling Problems, Johnson's Algorithm

Id: DH0S8CRmsp4

Length: 16min 14sec (974 seconds)

Published: Fri Feb 27 2015