Johnson's rule

The Johnson algorithm is an optimization method for queues, which was presented in 1954 by S. M. Johnson. It found inter alia in the sequencing to determine the minimum cycle time in the production management application.

The Johnson algorithm provides an optimum in terms of cycle time sequence of indeterminate many jobs to be processed on each of exactly two machines in turn. The algorithm can be generalized to more than two machines by auxiliary problems are generated.

The algorithm

There is a stack with indefinite contracts to many, to be processed in an optimal order with respect to the cycle time exactly two machines / processors Mj in sequence.

For example, five jobs with different processing times on the machines M1 and M2 to be processed cycle time - optimal. The following table indicates how much time ( in PA) an order Ai on a machine Mj needed.

Alternative 1

The problem can be solved with the following iterative procedure:

  • If j = 1: Arrange the order of Ai as far forward as possible in the order
  • If j = 2: Arrange the order Ai as far back as possible in the order

The Johnson algorithm now searches for the shortest order, so A1 with 4 ZE. Since A1 to M2 ( j = 2) takes the least time, it is classified in the new order as far back as possible.

The next- shortest order is A3 with 7 ZE. Since A3 to M1 takes the least time, it is classified in the new order as far forward as possible, etc.

Example for the iterative implementation

Example:

Start condition:

State1:

State2:

State3:

Zustand4:

Zustand5:

Zustand6 ( final state a):

Note: Here, the algorithm would be theoretically comes to an end, in one implementation, however, another state due to various element size check can still be displayed.

Zustand7 ( final state b ):

There is in this example thus 2 correct results.

Alternative 2

  • Order this group in ascending order after the Processing Time on machine 1
  • Sort them in descending order by the processing time on machine 2

The orders A2 (M1 = 12), A3 (M1 = 7), A5 (M1 = 11) form the first group. Sorting according to the shortest processing time on the machine M1 yields the first part of the solution: A3 → A5 → A2.

The second group contains the orders A1 (M2 = 4 ), A4 (M2 = 9). Sorting by the longest processing time on machine M2 yields the second part of the solution: A4 → A1.

The continuous time optimal sequence for this example is therefore: A3 → A5 → A4 → A2 → A1. The figure " Optimal machine allocation" is the optimal solution graphical form

443631
de