# MB0044 : Explain the steps involved in Johnson’s Algorithm and CDS Algorithm.

Posted October 18, 2011

on:**MB0044 : Explain the steps involved in Johnson’s Algorithm and CDS Algorithm. **

**Answer** :** Johnson’s algorithm of sequencing**

Johnson’s algorithm is used for sequencing of n jobs through two work centres. The purpose is to minimise idle time on machines and reduce the total time taken for completing all the jobs.

As there are no priority rules since all job have equal priority, sequencing the jobs according to the time taken may minimise the idle time taken by the jobs on machines. This reduces the total time taken.

The algorithm can be fulfilled in the following steps.

**Step 1:**Find the minimum among the time taken by machine 1 and 2 for all the jobs.**Step 2a:**If the minimum processing time is required by machine 1 to complete the job, place the associated job in the first available position in the final sequence. Then go to step 3. (If it is a tie you may choose either of them, for applying the above rule.)**Step 2b:**If the minimum processing time is required by machine 2 to complete the job, place the associated job in the last available position in final sequence. Then go to step 3. (If it is a tie you may choose either of them, for applying the above rule.)**Step 3:**Remove the assigned job from consideration and return to step 1 until all the positions in the sequence are filled.

**CDS algorithm for n jobs on m machines**

CDS algorithm was given by Campbell, Dudek and Smith. It is used to find the optimal sequence of the jobs to be followed when there are m numbers of machines. We do this by converting the m number of machines to 2. This is done by considering different combinations – like 1 and m, then 1+2 and (M-1)+M, then 1+2+3 and (M-2)+(M-1)+M, and so on. This gives m-1 sequences and we can choose the most optimal among them by calculating the time taken by each of the obtained m-1 sequences.

The sequence that takes the minimum time will be the most optimal job order sequence according to the CDA algorithm. This process is useful, when the number of machines is small but more than 2.

In order to calculate the time taken by each of the sequences obtained, we have to calculate the time-in and time-out of the jobs in the sequence for each machine. In order to calculate this, consider the sequence in case let 1 and follow the following steps.

Remember that except for M1, other machines may have to wait to start their operations, until the previous operation is over. You have to include idle times at the beginning, middle or the end. So the initial value, which is the time-in under machine 1 for the first job in the sequence, will be zero. The time-in for the further jobs will be Maximum of (the time-out of the previous job in the sequence under the same machine, the time-out of the next job in the sequence under the previous machine).

Time-out of a machine = Time-in of that machine (from the previous step) + The original time taken by the job under the respective machine.

## Leave a Reply