A Multiplex (Extended) Application of the Johnson Algorithm for the Two-Machine Manufacturing Cell Scheduling Based on Group Technology

Abstract

As is known, the Johnson algorithm is an exact solving method of the twomachine, one-way, no-passing scheduling tasks [1], [6], which serves as a basis for many heuristic algorithms. This paper presents the extension of Johnson's algorithm for Group Technology (GT). The task is as follows: Let us assume that in a two-machine manufacturing cell, in which two machines (A and B) of high automation and environment degree are working together in such a way that machine A is always ready to perform jobs, and machine B is working or waiting according to the timing of the work-pieces transferred from machine A to machine B; the work-pieces are arranged in groups G1, G2,..., G2,..., Gm Because of the similarities of the work-pieces in group Gi retooling and other setups (e. g.: change of equipment) of the machines in the manufacturing cell are not necessary. Consecutive machining of the groups Gi and Gj requires retooling and other setups in the manufacturing cell. An ordering of the groups is to be determined considering all the groups so that the sum of the setup times is to be minimum for all groups. In the paper the authors prove that the solving of this task can be traced back to the extended application of the Johnson algorithm and results an exact, closed-form optimum.