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 M1, M2, M3, ………Mn-1 , Mn in the order M1, M2, M3 …… Mn-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. aij for all j = 1,2,3,…..m-1 i i
  •        Min aim ≥ Max aij 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 = ai2 ai3 ………. 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 M1, M2, M3 and M4 in the order M1 M2 M3 M4 .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.