SKEDSOFT

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₁, M₂, M₃, ………M_n-1 , Mn in the order M₁, M₂, M₃ …… 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₁, M₂, M₃ and M₄ in the order M₁ M₂ M₃ M₄ .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.