Browse Prior Art Database

Elimination Method of Solving Large Matrix Sequencing Problems Approximately

IP.com Disclosure Number: IPCOM000074064D
Original Publication Date: 1971-Mar-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 3 page(s) / 74K

Publishing Venue

IBM

Related People

Hagan, GR: AUTHOR

Abstract

In optimum sequencing of several product types through a facility where the first product type recurs as type A to B to D to C to A, a recurrent sequence is followed. Where products do not return to the first item, as A to D to C to B, a nonrecurrent sequence is followed as in Tables I-VI as shown in sketch 1.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Elimination Method of Solving Large Matrix Sequencing Problems Approximately

In optimum sequencing of several product types through a facility where the first product type recurs as type A to B to D to C to A, a recurrent sequence is followed. Where products do not return to the first item, as A to D to C to B, a nonrecurrent sequence is followed as in Tables I-VI as shown in sketch 1.

Symmetric matrices are the same for reciprocal intersections as col. A, row B has the same value as col. B, row A. This is true of a matrix of distances between points. In nonsymmetric matrices, as where the cost of going in one sequence does not equal the cost of going in the reverse sequence, col. A row B and col. B row A may not be equal. Four types of arrays include: Non-Recurrent - Non-Symmetric; Recurrent - Non-Symmetric; Non-Recurrent - Symmetric; and Recurrent - Symmetric. This method is directed to nonrecurrent categories. Non- Symmetric Type.

If the first point is given or selected arbitrarily, the column corresponding to this point must be crossed out. Then eliminate the highest remaining entry in the array, the next highest entry, etc., until only one entry remains in any one row or any one column. Take this pair - this consists of row designation - column designation - in that order; and then eliminate that row and column.

In Table I with A as the first point, col. A is eliminated. In Table II values of 11 and above are crossed out. Pair A to C is chosen and row A, col. C are eliminated, to yield Table III. If no other rows or columns contain only one entry eliminate the highest remaining value, the next highest value, etc., until only one value remains in any one row or any one column. Continue as before.

At any matching of a row to a column or any matching of sets of pairs, the row and column entry that would allow a loop in the pair or within the set must be eliminated. Therefore, if BE and ED were chosen, the row D, col. B entry is eliminated to guarantee a solution that will exhaust the set i.e., without closed loops.

Next, if any two row values seek the same column, begin a new matrix consisting of all rows and all columns not yet eliminated; but restore all crossed out values and begin the same process anew.

In Table III row B and row E seek col. D with values above 11 crossed out, which are restored to give Table IV. How, delete values 24 and above, choose pair ED and eliminate row E and col. D to cause deletion of the D to E value. Choose pair DB. Eliminate row D and col. B....