Johnson algorithm

This article explains one optimization technique. For the algorithm from graph theory, see Johnson's algorithm (graph theory) .

The Johnson algorithm is a queue optimization method that was introduced in 1954 by S. M. Johnson . It is used, among other things, in sequence planning to determine the minimum cycle time in production management .

In terms of cycle time, the Johnson algorithm delivers an optimal sequence of an indefinite number of orders that are to be processed on exactly two machines one after the other. The algorithm can be generalized to more than two machines by creating auxiliary problems.

The algorithm

Optimal machine occupancy

There is a stack with an indefinite number of jobs that are to be processed in an optimal sequence in terms of cycle time on exactly two machines / processors one after the other. ${\displaystyle A_{n}}$ ${\displaystyle M_{j}}$

Example: Five jobs with different processing times should be processed first on the machine and then on the machine , with optimal cycle times . The following table shows how much time (in TU) an order A _i needs on a machine . ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle M_{j}}$

	A 1	A 2	A 3	A 4	A 5
M 1	14th	12	7th	13	11
M 2	4th	13	8th	9	14th

Alternative 1

Description of the iterative rule

The problem can be solved with the following iterative rule:

1. Find job A _i with the absolutely shortest processing time
2. Decide:
   • If : Arrange the order as far forward as possible in order to ${\displaystyle j=1}$ ${\displaystyle A_{i}}$
   • If : Put the order as far back in the sequence as possible ${\displaystyle j=2}$ ${\displaystyle A_{i}}$
3. continue with 1. until each order is assigned.

The Johnson algorithm now looks for the shortest job, i.e. with 4 TUs. Since it takes up the least amount of time, it is placed as far back as possible in the new order. ${\displaystyle A_{1}}$ ${\displaystyle A_{1}}$ ${\displaystyle M_{2}(j=2)}$

The next shortest order is with 7 TU. Since it takes up the least amount of time, it is placed as far ahead as possible in the new order, etc. ${\displaystyle A_{3}}$ ${\displaystyle A_{3}}$ ${\displaystyle M_{1}}$

Example for iterative implementation

The algorithm is demonstrated below using an example. The formatting has the following meaning:

value identified as the shortest running time

order already sequenced

The start state includes a random order sequence:

x	A1	A2	A3	A4	A5	A6	A7	A8
M1	12	7th	4th	3	10	5	6th	7th
M2	8th	6th	9	6th	2	8th	9	7th

State 1:

x	A1	A2	A3	A4	A6	A7	A8	A5
M1	12	7th	4th	3	5	6th	7th	10
M2	8th	6th	9	6th	8th	9	7th	2

State 2:

x	A4	A1	A2	A3	A6	A7	A8	A5
M1	3	12	7th	4th	5	6th	7th	10
M2	6th	8th	6th	9	8th	9	7th	2

State 3:

x	A4	A3	A1	A2	A6	A7	A8	A5
M1	3	4th	12	7th	5	6th	7th	10
M2	6th	9	8th	6th	8th	9	7th	2

State 4:

x	A4	A3	A6	A1	A2	A7	A8	A5
M1	3	4th	5	12	7th	6th	7th	10
M2	6th	9	8th	8th	6th	9	7th	2

State 5:

x	A4	A3	A6	A7	A1	A2	A8	A5
M1	3	4th	5	6th	12	7th	7th	10
M2	6th	9	8th	9	8th	6th	7th	2

State 6 (final state a):

x	A4	A3	A6	A7	A1	A8	A2	A5
M1	3	4th	5	6th	12	7th	7th	10
M2	6th	9	8th	9	8th	7th	6th	2

Note: The algorithm would theoretically come to an end here, but with an implementation, another state can be displayed due to various element size checks.

State 7 (final state b):

x	A4	A3	A6	A7	A8	A1	A2	A5
M1	3	4th	5	6th	7th	12	7th	10
M2	6th	9	8th	9	7th	8th	6th	2

In this example there are 2 correct results.

Alternative 2

1. Create a group of orders with processing times that are shorter on the first machine than on the second.
   • Sort this group in ascending order according to the processing time on machine 1.
2. Create a second group with remaining assignments.
   • Sort them in descending order according to the processing time on machine 2.

The orders form the first group. Sorting by the shortest processing time on the machine M ₁ gives the first part of the solution: . ${\displaystyle A_{2}(M_{1}=12),A_{3}(M_{1}=7),A_{5}(M_{1}=11)}$ ${\displaystyle A_{3}\to A_{5}\to A_{2}}$

The second group contains the orders . Sorting by the longest processing time on the machine results in the second part of the solution: . ${\displaystyle A_{1}(M_{2}=4),A_{4}(M_{2}=9)}$ ${\displaystyle M_{2}}$ ${\displaystyle A_{4}\to A_{1}}$

The throughput time optimal sequence for this example is therefore: . The illustration "Optimal machine allocation" graphically represents the optimal solution. ${\displaystyle A_{3}\to A_{5}\to A_{2}\to A_{4}\to A_{1}}$

literature

• SM Johnson. Optimal two- and three-stage production schedules with setup times included . In: Naval Research Logistics Quarterly , vol.1, iss.1, 1954

Web links

• ielm.ust.hk