The John on algorithm is a procedure for the sequence order in the ranges production economy and technical computer science and goes back on David Johnson, 1976. The mathematical beginning bases on the graph theory.

Problem

It exists a pile with indefinitely many orders A_n, which are to be worked on in an optimal order concerning the turn-around time on exactly two machines/processors, M_j.

The algorithm

The problem can be solved with the following iterative regulation.

1. Look for the order A_i with the absolutely shortest operating time
2. Decisions:

• If j=1: Arrange the order A_i as far in front as possible in row due to
• If j=2: Arrange the order A_i as right at the back as possible in row due to

1. drive away with 1. to each order is assigned so long.

Result

The John on algorithm supplies the turn-around time-optimal order of the orders.

Example

Five orders with different operating time on the machines M_1 and M_2 are to be worked on turn-around time-optimally.

The following table indicates, how much time (in CPU) needs an order A_i on a machine M_j.

{|

! ! align= " center " |A_1! align= " center " |A_2! align= " center " |A_3! align= " center " |A_4! align= " center " |A_5 | -! valign= " middle " | M_1 |align= " centers " | 14 |align= " centers " | 12 |align= " centers " | 7 |align= " centers " | 13 |align= " centers " | 11 | -! valign= " middle " | M_2 |align= " centers " | 3 |align= " centers " | 27 |align= " centers " | 8 |align= " centers " | 9 |align= " centers " | 30 | - |} 

The John on algorithm looks for itself now the shortest order, thus A_1 with 3 CPU. There to few time needed A_1 on M_2 (j=2), he is in the back arranged in the new order as far as possible.

The next-shortest order is A_3 with 7 CPU. Since A_3 on M_1 needs time to few, he is arranged as far in front in the new order as possible.

Etc.

The turn-around time-optimal sequence for this example therefore is:

A_3 - > A_5 - > A_2 - > A_4 - > A_1 

Related links

http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html

Articles in category "John on algorithm"

We found here 2 articles.

Related Websites

We found here 3 related websites.

• John Gamble / Algorithm-Networksort - search.cpan.org
  John Gamble > Algorithm-Networksort ... Algorithm-Networksort-1.04 -- 14 Dec 2003 ... Algorithm::Networksort, Create inline comparisons for sorting. 1.05 ...


• John Gamble / Algorithm-Networksort-1.05 - search.cpan.org
  All, Modules, Distributions, Authors. John Gamble > Algorithm-Networksort-1.05 ... Algorithm::Networksort, Create inline comparisons for sorting. 1.05 ...


• John Nolan / Algorithm-Cluster-1.17 - search.cpan.org
  John Nolan > Algorithm-Cluster-1.17 ... Algorithm::Cluster, perl interface to Michiel Jan Laurens de Hoon's C clustering library, 1.17 ...