Solution For Sequencing Problems
Solution for sequencing problem: ‘N’ Jobs on ‘M’ Machines
Though we may not get accurate solution by generalizing the procedure of ‘n’ jobs and 3- machine problem to ‘n’ jobs and ‘m‘ machine problem, we may get a solution, which is nearer to the optimal solution. In many practical cases, it will work out.
The procedure is :
- A general sequencing problem of processing of ‘n’ jobs through ‘m’ machines M_{1}, M_{2}, M_{3}, ………M_{n}_{-1 }, Mn in the order M_{1}, M_{2}, M_{3} …… M_{n}_{-1, }Mn can be solved by applying the following rules.
- If aij where I = 1,2,3…..n and j = 1, 2, 3……….m is the processing time of i th job on j th machine, then find Minimum ai1
- Min. aim (i.e. minimum time element in the first machine and I I minimum time element in last Machine) and find Maximum aij of intermediate machines i.e 2 nd machine to m-1 machine. i
- The problem can be solved by converting it into a two-machine problem if the following conditions are satisfied.
- Min ai1 ≥ Max. a_{ij} for all j = 1,2,3,…..m-1 _{i i}
- Min aim ≥ Max a_{ij} for all j = 1, 2,3 …….m-1 _{i i}
- At least one of the above must be satisfied. Or both may be satisfied. If satisfied, then the problem can be converted into 2- machine problem where Machine G = ai1 ai2 ai3 …………. ai m-1 and
- Machine G = a_{i2} a_{i3} ………. aim. Where i = 1,2,3,….n. Once the problem is a 2- machine problem, then by applying Johnson Bellman algorithm we can find optimal sequence and then workout total elapsed time as usual.
Example: There are 4 jobs A, B, C and D, which is to be, processed on machines M_{1}, M_{2}, M_{3} and M_{4} in the order M_{1} M_{2 }M_{3} M_{4} .The processing time in hours is given below. Find the optimal sequence.
Solution From the data given, Min a i1 is 12 and Min a i4 is 12.Max a i2 = 5 and Max ai3 = 10.As Min a i1 is > than Two-machine problem is:
Applying Johnson and Bellman rule, the optimal sequence is:
Total Elapsed time = 79 hours.