ENGINEERING RESEARCH INSTITUTE THE UNIVERSITY OF MICHIGAN ANN ARBOR Quarterly Progress Report No. 2 DEVELOPMENT OF MATHEMATICAL PROCEDURES AND MULTIPLE CRITERIA FOR ASSEMBLY OF LARGE WORK GROUPS October 16, 1955 to January 15, 1956 U. S. AIR FORCE AIR RESEARCH AND DEVELOPMENT COMMAND CONTRACT NO. AF 1(7 Jaur 1956} O

,- A-: 1~ 4-1 "-i 7;r i,. " / -WI

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN Contract No.: AF 41(657).-9 Budget Project No.: 7-7713 Contract Title: Development of Mathematical Procedures and Multiple Criteria for Assembly-of Large Work Groups Issuing Office: The Air Research and Development Command Contractor: The Regents of The University of Michigan Monitoring Agency: Director, Crew Research Laboratory, Air Force Personnel and Training Research Center, Randolph Field, Texas Principal Investigator: Dr. Paul S. Dwyer Period: October 16, 1955 to January 15, 1956 ii

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN PERSONNEL Portion of Name Title Time Devoted to Contract Work Dwyer, Paul S. Professor of Mathematics, Up to 40 hours Consultant in Statistical per month' Research Laboratory Graves, Patricia Assistant in Research Half time Galler, Bernard A. Mathematics Consultant Up to 40 hours per month2 During this quarter, Dr. Dwyer worked full time on his university duties and his work on the project was limited to 40 hours per month. 2Dr. Galler, an Instructor in Mathematics, began working on the project November 2, 1955. During this quarter Dr. Galler worked full time on his university duties and his work on the project was limited to 40 hours per month, except for an additional 20 hours allowed him during the Christmas vacation. iii

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN ABSTRACT This report provides information about the progress of the work on the project during its second quarter. It presents: 1. A statement of the general objectives as indicated in the specifications of the contract and as amplified during the July conference with Dr. Roby; 2. A statement of the objectives of the work of this quarter; 3. A discussion of the procedure used in carrying out the work of this quarter; 4. A statement of the general results obtained during this quarter; 5. A general discussion of the work on the contract to date with plans for the third quarter; 6. A summary statement. iv

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN I. OBJECTIVES The general objectives of the work on this contract are the development of mathematical procedures for assembling individuals in large work units and employing multiple criteria for assembly. More specific objectives indicated in the contract include: 1. The extension of results obtained for 3- to 5-man group assemblies so as to secure the optimal assignment of individuals to groups of larger sizes; 2. The development of economical means of accomplishing data transformations and practical simplifications of the problem encountered in reducing grouped matrices; 3. The translation of these procedures into programs suitable for use with electronic digital computers; 4. The use of appropriate approximate solutions when the criteria for assembly are based on fallible scores and consideration should be given to errors in group scores; 5. The feasibility of simultaneously employing multiple criteria of classification such as may be desirable if both technical qualifications and social factors are to be considered in forming work groups. Additional specific objectives were agreed on during the July conference with Dr. Roby. These include: 6. A revision of substantial portions of the 14-chapter report of the previous contract, necessitated by the development of improved techniques and theory in the later periods of the contract which were not incorporated in the draft presented; 7. Additional work directed toward the further analysis and improvement of the reduced grouped matrix transformations; 8. The identification of the basic mathematical problem in group assembly with the basic mathematical problem of other applied problems such as the general transportation problem; 1

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN 9. The determination of the extent of the relationship existing between the group-assembly problem and other related problems in linear programming; 10. An investigation of the effects of coarser groupings. Objective 7 is closely related to objectives 1 and 2. II. OBJECTIVES OF THE WORK OF THIS QUARTER In general, the objectives of the work of this quarter were related to general objectives 1, 2, 3, 6, and 7 stated above, although some consideration has been given to such other objectives as 4 and 8. Since general objective 1 must be attained largely through the more specific techniques resulting from the attempt to meet objectives 2, 3, 6, and 7, the work of this quarter was closely associated with these latter objectives. More explicitly, the objectives of the work of this quarter, in the order of time spent (with the exception of 5), were: 1. The continued improvement of the basic mathematical theory needed for the method of reduced matrices; 2. The development of economical means of accomplishing data transformations and practical simplifications of the problem encountered in reducing grouped matrices; 3. The translation of these procedures to programs suitable for use with electronic digital computers; 4. A revision of additional chapters of the 14-chapter report of the previous contract; 5. Preparation of papers describing the results. III. PROCEDURE The procedure used during this period may be indicated by the following facts: 1. The work on objectives 1, 2, and 4 was carried on by Mrs. Graves and the project supervisor. They not only worked on the development of an improved theory, but they used equipment in the Statistical Research Laboratory in 2

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN translating the improved theory of the method of reduced matrices to suitable practical techniques. 2. The services of Dr. Galler were secured to help with the translation of the procedures to techniques suitable for automatic digital computers. It was originally planned to use a half-time graduate student for this work, but it was impossible to secure a graduate student with the necessary qualifications who was willing to take this much time from his studies. We were fortunate in securing the services of Dr. Galler who came this year to The University of Michigan as a full-time instructor in mathematics, since he is especiallyinterested in working with electronic digital computers. During the academic year he can work only 40 hours each month, but his services have been secured for full-time work during the period June 15 -- August 15. IV. RESULTS The chief results of the work of this quarter are summarized below. The main topics in this summary correspond to the objectives of the work of the quarter stated in Section'II. 1. The most important contribution of this quarter was the continued improvement of the basic mathematical theory needed for the method of reduced matrices. Although some additional refinements in this general theory are still expected, the indication is that the basic theory is now available for improved hand and machine techniques. A great deal of effort was spent in consideration of the problem with many zeros. In a problem of this type, the selection of a permutation set of zeros becomes difficult because there are so many zeros from which to select. Although this situation is not common in actual problems, it is quite easy to construct problems of this type and the theory must be adequate for handling them in a reasonable length of time. The theory as it now appears provides the set of all possible solutions (using parameters), if that is desired, or, as is commonly preferred, it provides some one solution. The mathematical theory is a continued improvement of the theory appearing in the first quarterly report. The equations of condition are applied to the zero terms of the reduced matrix. A formal method of reduction to triangular or echelon form is applied (which is easy for the group-assembly problem and other problems leading to equations with coefficients O or 1) and the reduction shows either that the equations are consistent and so have an algebraic solution or it reveals Qne or more independent, indecomposable, inconsistent, linear forms of specific rows and columns of the reduced matrix. Any one of these linear forms can be used as the basis off a transf atation which will maintain all the zero terms and introduce at least one more zero teri. |

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN The linear form indicates the sign of the element to be subtracted from each row, column, layer,.... Then the element can be determined, as is explained in previous descriptions of the method of reduced matrices, so that at least one additional zero term will be introduced without the introduction of any negative terms. The process continues until an algebraic solution is found. Alternately, the inconsistent linear forms can be obtained from the solution of a system of homogeneous equations having a coefficient matrix which is the transpose of the coefficient matrix described above. (This is used in the calculation process Dr. Galler is preparing for use on MIDAC.)| A desirable aspect of the improved theory is that it can be applied directly to the reduced matrix. This then eliminates the necessity of making reductions to reduced grouped matrices. While the reduction first to reduced grouped matrices is useful in many k = 2 problems when worked by hand, the new methods are a great improvement for all problems worked by machine and for k > 2 problems worked by hand. The attainment of consistency as shown by the existence of an algebraic solution does not necessarily yield a satisfactory answer, since at least one element of the proposed solution may be negative. The theory is now developed for this situation. The equations leading to this negative element always can be translated to the next transformation. Since this transformation always results in the elimination of the zero which has been given a negative assignment, we also can determine a next transformation by (a) eliminating this zero element from the subset, and then (b) applying the equations of condition to this new subset. This latter method is the one which has been adopted for machine use. We have learned just recently how to modify the subset of independent, indecomposable, inconsistent linear forms associated with one iteration into the set associated with the next iteration, so that it is not necessary to solve sets of equations for each iteration. Alternatively, we have learned how to incorporate the different solutions associated with the different iterations into a single solution process. 2. As is suggested above, the improvement of the mathematical theory has led to more economical means of accomplishing the transformations and hence to practical simplification of the method of reduced matrices. In general, the theoretical description of the method is now precise enough so that it can be translated to techniques for MIDAC. Though the problems sometimes can be worke more easily by the less formal methods described in the report of the previous project (particularly for the simpler problems such as those with k = 2), the more formal methods and extended results make possible abbreviated solutions of the more complex problems. In particular, the elimination of the transformations leading to reduced grouped matrices may reduce the work of the solution to a fraction of its former size. For example, the solution of Table 11.5.1 of the extended report of the previous project took 19 transformations, and

ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN allied calculations necessary to test if the matrix was reduced grouped, in addition to the two extreme transformations applied first. A recent solution of this problem using the improved theory required but 3 iterations to obtain an algebraic solution from the reduced matrix and but 5 more iterations to obtain a solution featuring positive integers. Also, the work of determining the transformations associated with the 6 iterations can be arranged in compact form. The replacement of the solution with 21 iterations by a solution with 8 iterations indicates an improvement of about 60%. 3. These procedures are being translated to programs suitable for use with MIDAC. It will be recalled that we have provided MIDAC techniques for obtaining reduced grouped matrices for problems with the product of the numbers of rows, columns, and layers < 200. We now apply the equations of condition directly to the reduced matrix without taking the time to compute the reduced grouped matrix, and reduce to echelon form. The MIDAC program for k = 2 is now essentially complete and we are starting on the k = 3 case. Programs for k > 3 should follow readily, the primary limitation being a limitation of machine capacity. This problem of storage capacity is a serious problem with MIDAC and it may be that we will want to shift to UNIVAC or to one of the 700-series IBM machines for the really big problems if such a machine is available to us. We will have access to an IBM 650, which the University is installing in the Statistical Research Laboratory in March, but theri is doubt that its capacity will be adequate for some of the problems with large k. 4. The work of revising the research report of the previous contract was continued during this quarter with the revision of Chapters VIII, IX, and X. Since the material involved in the improved method has become more extensive than was anticipated at the time of the preparation of the first quarterly report, it seems proper not to attempt to include it in the revision (as suggested on page 3 of the first quarterly report), but to present it in research reports appropriate to the present project. Accordingly, the revision of Chapters VIII-X has not been a major one, but has consisted of critical examination of the previous version for the purpose of eliminating mistakes and typographical errors and changing any statements which need modification in the light of our present knowledge. In particular, we have changed certain statements in Chapter I and Chapter VII dealing with the simplex method and the method of reduced matrices. These methods, though they differ in design and in operation, have basic general theory in common. The fact that the simplex method does not lead, in every problem with k > 2, to a solution with positive integers resulted in an overemphasis on the fact that the simplex method is inapplicable. In a sense, too, the method of reduced matrices is subject to this same limitation, though we are perfecting an extension of the method which should yield integral solutions. In any case, particularly with the improvements in the method of reduced matrices now available, the evidence continues to mount that the method of reduced matrices is in general superior to the simplex method and that the superiority increases with the increasing. complexity of the problem. _ - - 5~~~~~~~~~

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN The revised Chapters I - X of the research report of the previous contract will be sent to Dr. Roby soon. Included will be some rewritten sheets for his original copy and a duplicate copy of all the material in these chapters. 5. Though this second quarter has been spent primarily on the development of new theory and techniques rather than in writing, two papers were writ-. ten. These were: a. The Problem of Optimum Group Assembly; b. The Solution of the Hitchcock Transportation Problem with the Method of Reduced Matrices (Version of December, 1955). The first of these papers was prepared in late October for publication in the Proceedings of the National Research Council Symposium (held in Washington in November). It is a short nontechnical presentation describing the nature of the problem, the mathematical statement of the problem, the solution of the problem with the method of reduced matrices, the implications for the Air Force, and the scientific significance of the results. An appendix shows the application of a k = 3 problem with frequencies. The second of these papers is a revision of a paper written in June, 1955. This version is substantially a new paper, since it applies the results of the research of this quarter to the k = 2 case. (A copy of this paper has been sent to Dr. Roby.) V. DISCUSSION The results of this quarter, like those of the first quarter, seem to lead to the desired goals. A greatly improved theoretical basis of the reduced matrix transformations has been developed and the theory -leads to techniques which are capable of complete mechanization. Simultaneously, Chapters VIII - X of the research report of the previous contract have been revised. The translation of the techniques when k = 2 and k = 3 to suitable MIDAC programs has been underway since November. The work on the k = 2 case for mn < 200 is essentially complete and the work on the corresponding k = 5 case is started. The work of the third quarter will feature: 1. The revision of Chapters XI - XIV of the earlier report; 2. Development of refinements in the theory of reduced matrices when k is large; E ~~~~~~~~~~~6

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN 3. The development of calculational methods for work groups of larger size; 4. The preparation of a draft research report to cover the results of the first three quarters of the project; 5. Preliminary studies of additional topics, such as those of general objectives 4 and 5, which are scheduled for detailed study during the last two quarters of the contract. VI. SUMMARY STATEMENT It thus appears that, in the main, the objectives set for this quarter have been attained. A somewhat larger time than was anticipated was needed to derive the theory of the improved method of reduced matrices, but the results give improvements in the method, especially applicable to the case of large k, which are beyond our previous expectations. Since November we have been making progress on the use of MIDAC. This progress should continue during the coming months and will be speeded up during the summer, when both Dr. Galler and the project supervisor will be working full time on the project. A machine having more capacity than MIDAC may be needed for the more general techniques. All in all., we feel that the work on the project is progressing in a satisfactory manner. 7

I

UNIVERSITY OF MICHIGAN 3 9~01111111111111111ii1111111150028 3 9015 02082 8078