Learning Curve…

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

Posted on: October 18, 2011

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Author

Learning days (Calendar)

October 2011
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

Knowledge Bank (Archives)

I am on Twitter

Blog Stats

  • 503,999 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 43 other followers

%d bloggers like this: