ENGINEERING RESEARCH INSTITUTE THE UNIVERSITY OF MICHIGAN ANN ARBOR Quarterly Progress Report N6. 5 DEVELOPMENT OF MATHEMATICAL PROCEDURES AND MULTIPLE CRITERIA FOR ASSEMBLY OF LARGE WORK GROUPS July 16, 1956 O- ctober 15, 1956 ~',..;, U. S. AIR FORCE October 1956 October 1956

H' NBctc Vt;l. v

The University of Michigan ~ Engineering Research Institute 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: Operator Laboratory, Field Unit No. 1 ATTN: Dr. Robert L. French, Air Force Personnel and Training Research Center, Lackland Air Force Base, San Antonio, Texas Principal Investigator: Dr. Paul S. Dwyer Period: July 16, 1956 to October 15, 1956 _ ii

The University of Michigan * Engineering Research Institute PERSONNEL Portion of Name Title Time Devoted to Contract Work Dwyer, Paul S. Professor of Mathematics Variable1 Consultant in Statistical Research Laboratory Galler, Bernard A. Instructor in Mathematics Variable1 Mathematics Consultant Graves, Patricia Assistant in Research Half Time Locker, John2 Assistant in Research 14 hours per week'During the summer months, Dr. Dwyer and Dr. Galler worked full time on the project. Since September 15 each has worked full time on his university duties so his work on the project was limited to 40 hours per monith. 2Mr. Locker began working on the project on October 8, 1956. ii

The University of Michigan * Engineering Research Institute ABSTRACT This report provides information about the progress of the work on the project during its fifth quarter. It presents: 1. A statement of the general objectives as indicated in the specifications of the contract and as amplified during the July, 1955, conference with Dr. Roby; 2. A statement of the objectives of the work of the fifth quarter; 3. A discussion of the procedure used in carrying out the work of the quarter; 4. A statement of the general results obtained during the quarter; 5. A general discussion of the work on the contract to date with plans for the remaining term of the contract; 6. A summary statement. iv

The University of Michigan ~ Engineering Research Institute 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, 1955, conference with Dr. Roby. These include: 6. A revision of substantial portions of the 14-chapter report of the pervious contract, necessitated by the development of improved techniques and theory in the later period 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 - - - - -

The University of Michigan * Engineering Research Institute 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 work of this quarter, like that of the previous quarter, was related to objectives 3, 4, 5, 7, and 8 stated above. More explicitly, the objectives of this quarter were lo. The treatment of problems mathematically equivalent to or related to the group-assembly problem; 2. The investigation of the feasitility of employing multiple criteria of classification simultaneously; 3 The determination of appropriate approximate solutions when the group scores are fallible and subject to error; 4. The preparation of the following programs for use with the IBM Type 704 electronic digital computer: a, a program for the method of reduced matrices, b. a program for approximate solutions based on the deviate matrix; 5, The preparation of results for addresses and publication. III. PROCEDURE The procedure during this quarter was similar to that.of the pre-. vious ones. Dr. Galler has been working on. the translation of. the general results into programs for the IBM Type 704 electronic digital computers Mrs. Graves and the project.supervisor have been working on.the other explicit objectives of this quarter indicated above. During the latter part of the quarter, the work has.been largely the preparation of reports of the results

The University of Michigan ~ Engineering Research Institute of our research on these objectives. The services of Mr. Locker were recently obtained to help in the checking and preparation of these final reports. IV. RESULTS The chief results of this quarter are summarized below. 1. The group-assembly problem is mathematically similar to several other practical and mathematical problems. For example, a general Hitchcock transportation (distribution) problem is mathematically identical with the group-assembly problem, except that minimization replaces maximization. Alternative general transportation problems can be solved by an extended method of reduced matrices which we have developed. The interesting mathematical problem of finding the permutation subset of a k-dimensional matrix can be solved by forming a related problem in k + 1 dimensions and solving this by the method of reduced matrices. The solution of this mathematical problem makes possible the solution of certain special cases of the traveling-salesman problem. Thus.the methods we have worked out for.solving the group-assembly problem are useful in solving many additional problems. 2. Several interesting facts resulted from the study of multiple criteria. In the important case in which there is a preferred criterion, the concept of efficiency of an approximate solution and the use of the finally reduced matrix lead to a measure.of the adequacy of the solution of the preferred criterion matrix as applied to the other criterion matrices. The finally reduced matrix and the concept of efficiency are also useful in determining a most representative criterion and in determining acceptable weights for a composite criterion matrix. A method featuring the joint use of multiple criteria requires the solution of a problem in k + 1 dimensions. 3. Alternative techniques are now available for determining appropriate approximate solutions when the elements of the assembly matrix are subject to error. If the errors are known, the finally reduced matrix may be adjusted and the corrected solution can be obtained therefrom. If the errors are very small, they need not be considered. If the errors are unknown but bounded, the method of reduced matrices may be modified to give solutions which are almost optimal or possibly optimal. These modifications commonly reduce the length of the method of reduced matrices since the set S has a larger number of elements at each iteration than does the set S of the unmodified method. Also, approximate solutionsbased on deviates can be obtained on the IBM Type 704 electronic digital computer in a very short time. Considering the speed with which these approximations can be.obtained, they seem to.be quite acceptable. Better approximate solutions, also based on the deviates, can be obtained by an additional solution of a linear system.,

The University of Michigan ~ Engineering Research Institute 4. The program for the adaptation of the method of reduced matrices, through the determination of a positive solution on the IBM Type 704, is at the checking stage. Problems of small size have been solved quickly with this method on the machine but some final adjustments in the program are necessary for the solution of the very, very large problems. 5. The program for the approximate method based on deviates, as worked out for the Type 704, appears very satisfactory. The method gives a solution which seems to have an efficiency of better than 90% in a very, very short time. For example, the approximate solution of the k = 2 problem of Table 7.2 of Research Report 3 was obtained in 25 seconds after the problem was placed in the machine. Because of the nature of the method, the time for minimization problems is essentially the same as that for maximization problems and depends, for the most part, on the size of the matrix rather than on the values of the elements in the matrix. The approximate solution of the k = 7 problem of Table 7.3 of Research Report 3 was obtained in 12 seconds. This was also the time required to obtain the approximate solution of the k = 4 problem of Table 7.4. V. DISCUSSION The bulk of the research work on the contract is now complete and the major work remaining is the preparation of papers and reports. In addition to the papers mentioned above, the following reports are being prepared. 1. Research Report 4. "The solution of problems mathematically equivalent to or related to the group-assembly problem." This deals with the results mentioned in IV-l above. Two copies of a preliminary version of this report have been sent to Dr. French for suggestions. 2. Research Report 5. "The use of multiple criteria of classification." This deals with the results mentioned in IV-2 above. The body of this report is being prepared for reproduction. 3. Research Report 6. "The use of appropriate approximate solutions when the group-assembly matrix consists of fallible group scores." The research work on this report is complete and the body of this report is now being written. 4. Research Report 5. "Adaptation of the method of reduced matrices to electronic digital computers." A preliminary version of this report was submitted last spring. As a result of our experience with the IBM Type - ~~~~~~4

The University of Michigan ~ Engineering Research Institute 704, a revised version of this report will be prepared. This revision should be delayed as long as possible, within the term of the extended contract, so that we can incorporate knowledge gained with use of the Type 704 machine. The revised report will also cover the use of the approximation method based on deviates as applied to electronic digital computers. It will include the programs for the IBM Type 704.. 5. The paper, "Translating the method of reduced matrices to machine computation," will be prepared during the next month. This paper, which will be submitted to AFPTRC for clearance for publication in Naval Research Logistics Quarterly, may be considered to be a supplement to Research Report 3 We are in process of obtaining approximate solutions for additional problems, some of large size. On the basis of our present results it appears that good approximate solutions can be obtained very quickly. It appears probable that one using the simplex method, which demands some feasible soluin the beginning, might do well to start with this approximate -solution as the feasible solution so that the simplex method will converge quickly. 6. Some papers and addresses have resulted. These include: a. tThe method of reduced matrices for a general transportation problem," a paper prepared by Dr. Dwyer and Dr. Galler and presented by Dr. Galler at the Los Angeles meeting of the Association for Computing Machinery, August 29, 1956. b. "Translating the method of reduced matrices to machine computation," a talk prepared by Dr. Dwyer and Dr. Galler and presented by Dr..Galler at the RAND conference.on linear programming on August 31, 1956. We are preparing a paper on this talk to be included in the Proceedings of the Conference which will be published in a special issue of the Naval Research Logistics Quarterly. c. "A theorem on the multi-index transportation problem" (Preliminary Report), to be given by title at the October 27 meeting of the American Mathematical Society at Cambridge, Mass., by Dr. Dwyer. The abstract will appear in the Bulletin of the Society. 7. The final research report will summarize the work of the contract.: I~~~~~~~~

The University of Michigan ~ Engineering Research Institute VI. SUTMMARY STATEMENT With the research work on the contract essentially complete, we are- still convinced that the method of reduced matrices is.the most effective method for solving the group-assembly problem. Also, extensions of and modifications of the method are available for. solving many related problems. The method is useful in handling problems with multiple criteria and problems with fallible data. This method, at least as far as the determination of positive solutions, can be adapted to modern high-speed computers. ____ ___ ___ ___ ___ ___ ___ ___ ___ ___6

UNIVERSITY OF MICHIGAN 13 9015 02656 644111111111 3 9015 02656 6441