Technical Report No. 144 4967-2-T SCHEDULING WITH RANDOM ARRIVALS AND LINEAR LOSS FUNCTIONS by DPW. Fife. Approved. By: ______ -: —.:B. F..^ Barton-i COOLEY ELEGRTBQNICSi.L.,4AB,0RATORY Department o'Electrical.Engijneerling The Univitrs-it y'of Mi'higan.s ArA.rn-rtoi. Project 04967 Contract No. AF 30(602)-2661 Rome Air Development Center Griffiss Air Force Base New York April 1964

~ s ", "I,J I e' 8, >X. ^'-^ Ic.,

TABLE OF CONTENTS Section Page Summary................ o o o o........ 1 Introduction o o o. o.. o o o o. o.o o o 3 2 Decision Problem With Random Arrivals.. o.o.. 5 3 An Equivalent Criterion... e o....o.. o o o 7 4 Optimum Nonpreemptive Scheduling........... 11 5 Concluding Remarks..... o.... o... 15 References o. o o.o o. o.. o o..o. o 16 Distribution List o..............o o iin

SUMMARY The problem under consideration involves scheduling of the processing of an initial queue of jobs and subsequent Poisson arrivals on a single processor. Each job to be processed incurs a loss which increases linearly with its waiting time. The scheduling algorithm is sought which minimizes the average rate of expected loss over infinite time. It is shown that if statistical equilibrium exists for the total loss of an individual arrivals the optimal schedule minimizes the expected total loss of a single arrival, and is given by the scheduling rule which applies when there are no additional arrivalso 1

1 INTRODUCTION A scheduling model which has attracted continued interest since its appearance is that introduced by McNaughton (Refo 5)o In this model, there is a finite set of jobs which must be processed in a facility composed of one or more identical processorsO Each job can be finished in a single stage of processing by one processor, and the required processing time for job i is denoted by a.o Assuming that the number of jobs in the set is larger than the number of processors, all jobs cannot be processed simultaneously and the elapsed time to completion for the jobs which must wait will be larger than the required processing timeo It is assumed that if the time of completion of job i occurs after a deadline time, di, a loss is incurred for job i which depends upon the amount of delay beyond.d. The loss generally reflects a penalty for failure to finish the job before the deadline, so it is assumed that no loss is incurred if completion occurs before d..o The amount of loss for job i, if completion occurs at time t after the deadline, is given by a loss function L.o(t), assumed to be monotonic nondecreasingo A schedule for processing the set of jobs gives the order in which to admit jobs to the processing facility. The total loss of a schedule is given by the sum of the losses which result for individual jobs in the set It is assumed that the processing time, deadline time, and loss function of any job are unaffected by their position in a scheduleo The problem of interest here is to determine an optimum schedule which has a minimum value of total tos s McNaughton (Refo 5) and Smith (Refo 8) have determined the optimum schedule in the special case of a single processor facility, with all jobs having linearly increasing, unbounded loss functions and deadlines which have passed when scheduling beginso The loss function is characterized simply by the loss rate, denoted pi for job i. The optimum schedule is achieved by selecting jobs for processing in an order for which the corresponding sequence of values, 3

.Pi/aia is monotonic nonincreasingo This procedure will henceforth be.referred to as the single processor scheduling ruleo Schild and Fredman (RefSo 6 and 7) have recently developed scheduling algorithms for the single processor facility when some jobs can be completed before their deadlines, or when loss functions are nonlinearo The more general case of linear loss functions and a facility consisting of several identical processors in parallel is much more difficulto If all processing times a. are equal and all d. = 0, the schieduling rule given above for the single processor facility is sufficient to obtain an optimum schedule for the parallel facilityo However, for unequal a.i one can only show that every subset of jobs processed on the same processor in the optimum schedule must be ordered according to the single processor ruleo No rule is known for optimally partitioning the set into subsets to be done on the same processor. Lacking an optimum algorithm, one is strongly tempted to use the single processor scheduling rule to obtain a schedule for the parallel facilityo The resulting total loss appears to closely approximate the optimum when the maximum single job processing time is much less than the total time to complete all obs0 This conjecture has not been conclusively verified howevero Partial results on the parallel processor problem have been given by McNaughton (Refo 5), and recently by Lawler (Refo 4)o The purpose of this paper is to extend the applicability of the single processor scheduling rule to a case in which additional jobs to be scheduled may arrive at random before a schedule is completedo Specifically, we consider Poisson arrivals of jobs to be processed on a single processor with the jobs having linearly increasing loss functions and deadlines occurring at the time of arrivalo The total loss incurred in any time interval of operation is now a random variable, and Is unbounded when the Interval becomes arbitrarily largeo Hence, the objective considered is to minimize the average rae of expected loss over an arbitrarily large time intervalo 4

With nonpreemptive processing, in which processing of any job cannot be interrupted once it has begun, arrivals occurring while the processor is occupied cannot be scheduled until the job in process is completed. Thus the possibility exists that significant losses are incurred because the queue cannot be rescheduled when arrivals occur. Conceivably, a more complex scheduling procedure than the single processor scheduling rule might allow hedging against such losses. The scheduling decisions which must be considered in nonpreemptive processing are described in the next section. Then, it is shown that the optimum nonpreemptive scheduling policy gives a rule for selecting from the queue the next job to be processed when the processor is idle, and that the optimum rule is to select the job in queue having the largest value of the ratio of loss rate to processing time. Thus, the optimum rule for scheduling the single processor with Poisson arrivals is identical to that with no additional arrivals, under the constraint of nonpreemptive processing. The proof uses a general result from priority queueing theory, and is therefore interesting as a synthesis of this area with the rather distinct area of scheduling theory. The case of preemptive-resume processing, in which processing of any job can be instantaneously interrupted and later resumed without increase of total processing time, cannot be treated by the method used here. But as a concluding remark, we express our conjecture as to the optimum scheduling rule which applies. Our interest in this problem, as McNaughtonVs, stems from its application to the scheduling of a data processing machine. 2. DECISION PROBLEM WITH RANDOM ARRIVALS First, we discuss the single processor scheduling decision problem in general, leading to a definition of the alternatives which must be considered in seeking the optimum scheduling ruleo 5

The stochastic process of interest is {C(T), 0 < T < o, the total loss incurred in service of independent Poisson arrivals in the time interval 0 <t < T according to a specified scheduling algorithm. An optimal scheduling algorithm minimizes the asymptotic average rate of expected loss, V lim E(C(T)/T) (1) T-aoo where E( ) denotes the expectation over the ensemble of arrival sequences. As we will show, there is at least one policy for which V exists. The underlying sample space of the stochastic arrival process in an ensemble of sequences a>( 7n P, a), n = 1, 22,.} where T is the time interval between the seunc n n P n n (n - l)th and nth arrival. For n = 1 the term r is defined to be the time of the first arrival measured from t 0. The terms tn- p n and a are independent, nonnegative random variables for all N. The arrival process is assumed stationary, so the probability distribution functions of Tn pn and a do not change with n. n The expectations are denoted E(T), E(p), and E(a), all assumed finite. In particular, E(T) = 1/X where X is the mean arrival rate. We assume that p and a can have only a finite number of different values. n Thus these random variables naturally divide the population of arrivals into a number R of what are called description classes; all jobs of a given description classes; all jobs of a given description class have the same values of loss rate p and processing time a. (All results here hold also if the number of classes is countably infinite, as when p and a assume only rational values,) Since we n n assume that all deadlines occur upon arrival, jobs of the same description class in queue are indistinguishable. Because all jobs must eventually be processed, and because processing is assumed to be nonpreemptive, all scheduling decisions occur when the queue is not empty, and can be characterized as among the following: (a) Select any job of description class j, and begin processing it (j- 1, 2, 3^- o i R). 6

(b) Leave theprocessor idle until a specified time T has elapsed (0 < T < oo), (c) Leave the processor idle until the next arrival occurs. Of course, one cannot decide to process a class j job if none are available at the decision time. This information is provided by knowledge of the state of the system, which at any decision time is given by a vector, s = (n^ n", n3. n) 1 n2 n3, R where n. is the number of uncompleted class j jobs present (n. > 0 for all j), A J J scheduling policy is then defined when the decision to be made from among the available alternatives is specified for every observable state and time at which a decision may occur. We will limit consideration to stationary policies, for which the decision in any state is independent of the time at which the decision is made. Such a restriction is often desirable because of the difficulty of implementing a nonstationary policy. Furthermore, although we cannot show it, the optimal policy may indeed be stationary. 3. AN EQUIVALENT CRITERION The criterion for optimality of a scheduling policy is that it minimizes V defined in (1). Whenever statistical equilibrium exists for the loss of an individual arrival as T - oo, another criterion is applicable. We now show that this equivalent criterion is to minimize the expected loss of a single arrival taken over the population of arrivals when equilibrium has been reached. Later results are obtained by considering only policies to which this equivalent cri-. terion may be applied. In order to establish equivalence of the two criteria, the scheduling process must be treated with greater detail. Let 5 denote the state of the system at t = 0, and assume the number of jobs in queue is finite, and all have finite loss rates and processing time values. For any arrival sequence, the integer random variable N(T, 5) is defined to be the total number of jobs appearing for scheduling during the interval 0 < t < T 7

as random arrivals and as members of the initial queue, when the initial state is 4, Clearly this variable is unaffected by the scheduling policyo Let a particular scheduling policy be denoted by 17 and define the continuous random variable i.(T, 4TT ) to be the loss over the interval O < t < T of the ith job appearing for scheduling with any arrival sequence. Without loss of generality, the jobs initially in queue are considered as "arriving" at t = 0 and indexed arbitrarily, with later arrivals subsequently numbered in order of time of arrival. Because the loss of any job during its processing time a. is unaffected by sched-..... uling, this constant loss term can be neglected in seeking the policy minimizing Vo So, defining ta )(g) as the time of arrival of the ith job, and t (i), ) as the a s time of the start of its processing, we obtain fi(T. ) ( 4 in tm - )(iT 4) - t i)(4) T - t (i)(4 (2) 1 a; ~ is a -.a where 0 < t (() < To Neither the loss rate pi(g) nor arrival time t (i) is dea a i pendent upon the policy a. Then, N(T,) C(T, 7rT )- f li(T9 ) (3) inl is the total loss incurred in O < t < T with policy T and initial state 4. For every interval T, policy f, and initial state, there is assumed to exist a probability measure on values of N(T, ), denoted Pn' and a conditional probability measure on values of the set {E i(T9, r9 4)9 i = 1 2 o o N(T, 4) for a specified value of N(T, 4)o Let Qn(xi, x2 o o. xn) denote the latter. Suppressing the arguments denoting conditionality on T, r, 49 we can write E() 1 p dQ (C x ) ETy T XL n x 4 7 idQn(X. x) n n i=l By introducing a conditional expectation we can set 8

n n i. xidQn(xl. x) = E(.iIn) n i=l i=l where E(1iln) is the expected loss of job i over the interval [0, T], given N(T, ~) = n. Then, E() Pn L E( iln). (4) 4T 211in n i n i=l As defined in (1), Vis the limit as T - co of the expression in Eq. 4. We assume that V exists and has the same value for every initial state. Both P and E(. In) are continuous functions of T for every value of n. So, assuming E(% In) is bounded for all i, n, ~, and T, V can be expressed as V= n ]P n n I= ~-Pn 1n V= y lim lim Fy E(lin) (5) T-oco T T-0oo L- n _ JL i=l From the stationarity of the Poisson arrival process and the restriction to finite initial states, N(T, 5)/T X with probability one as T - oo. The left limit in (5) is therefore nonzero only for n oo. Thus V=X lim lim E(. n). (6) n-oo T-oo n i-=1 Now define ci(ar, () as the total loss of job i as T - oo. Corresponding to (2) is the definition ci(, ) =- pi(.)Wi(7ij. ) (7) where w. (ir, ) is the total waiting time of job i before start of processing. Then lim lim E( lIn)= E(c.) n-oo T-oo and 9

V X lim E(ci) (8) i=l Finally, assume that E(c.) converges to a common value E(c) as i- oo for every initial state ~o Then it follows that V = XE(c) for every state.o To minimize V, one must minimize E(c), which can be interpreted as the expected total loss of a single arrival as T -oo Summarizing, the expected loss E(c) will serve to evaluate any scheduling policy, whenevero (a) The expected total loss of any job is bounded for every initial state. (b) The expected total loss of a single arrival at T - oo converges to a value independent of the initial state. Both properties hold when all jobs are processed and a stationary probability distribution, independent of the initial state, exists for the total loss of a single arrival at T - oo. The latter describes the condition of statistical equilibrium, familiar in queueing theoryo Thus, an example of a policy satisfying these conditions is the'first come, first served" queue discipline. In this case, condition (a) above is satisfied if XE(a) < 1. Because the waiting time, w.i(, ) is independent of pi(t) E(ci) E(pi)E(wi) For i sufficiently large that the ith job is a random arrival, rather than one of the initial queue members, E(Pi) = E(p)o Thus one has only to show convergence of E(wi) for every initial state to demonstrate condition (b)o A detailed proof of that has been given by Kiefer and Wolfowitz (Refo 3). Using subscripts to identify description classes' one can write, for any policy for which equilibrium exists, 1Ro Syski, Introduction to Congestion Theory in Telephone Systems, Oliver and Boyd, London, 1960, po 179. 10

R E(c) =- pjqjE(wj) j=1 where q. is the probability that an arrival is a class j job. Then it easily follows that R 21 pj E(n.) = XE(c) + constant (10) j=l where the constant is independent of the policy. The left side is the expected total loss rate in equilibrium, which is therefore minimized by the optimal policy. 4. OPTIMUM NONPREEMPTIVE SCHEDULING Confining consideration now to policies for which statistical equilibrium exists, we proceed to a specification of the optimal nonpreemptive scheduling policyo In doing so, we use some general results on nonpreemptive priority queues obtained by Cobham (Ref. 1) and Holley (Ref. 2). First, it can easily be argued that no decision which leaves the processor idle when jobs are waiting to be processed is included in an optimal policy. Let E(wj), j = 1, 2,.. R, in (9) denote the values obtained by a policy in which the processor is not left idleo A decision to leave the processor idle must reduce E(wj) for some j if it is to be an optimal decision. We can consider w. as J J composed of two parts: w' the time a job waits after its arrival until any job then in process is completed; and w'j, the subsequent time spent waiting for processing of other jobs in queue before its admission to the processing facilityo If all jobs are to be eventually processed and equilibrium exists, any decision to leave the processor idle whenthe queue is not empty cannot change the expected fraction of time the processor is occupied processing jobs of any class. There11

fore, E(w.) is unaffected by these decisions for any j. In fact, following Cobham's discussion (Ref. 1), one can show that E(wj)= E(To)= aj qj j=l for all jo On the otherhand, w"j will be unchanged or increased for every j by a policy which allows the processor to be idle when jobs are waiting. Thus E(wj) cannot be reduced for any j by such a policy. The decisions to be determined are now seen to occur at the times of job completions where the queue is not empty, and constitute a selection of the class of the job to be processed next from the description classes represented in the queueo Because the optimum scheduling rule for the single processor without ~additional arrivals remains the same for any state, and because the random arrival process here is independent of the state of the system, it is sufficient to consider a selection criterion applicable to any state and achieved by assigning priorities to the description classes based on the loss rate, arrival rate, and processing time values of eacho The next job to be processed is any job from the highest priority class present in queue, and without introducing any restriction we can assume the earliest arrival is choseno Hence, we seek the rule for assigning nonpreemptive priorities which minimizes E(c)o Let subscripts on pi, ai, and qi now refer to the values for the description class assigned to priority i in an R priority class system, where priorities are numbered i = 1, 29... R from highest to lowesto To evaluate E(c) for any priority assignment requires an expression for the expected waiting time of a priority i arrival in statistical equilibrium. From Cobham (Refo 1) and Holley (Refo 2), the required result, specialized to the case where the processing time for each priority class is a known constant, is 12

E(T ) l) (E(w) (12) - X qaj.l qja j= l E(To) is defined in (11). Withpi = aqi.a the condition for equilibrium to exist is R P<1. (13) E Pi < 1.(13) i=l Then, for an arbitrary priority assignment, R p.q.E(T ) E -( 1- (14 =1 j=l The optimum priority assignment can be obtained from an arbitrary initial assignment by successively interchanging classes assigned to adjacent priority levels, each interchange reducing the loss measure E(c). The conditions under which an interchange of any pair reduces loss can be determined by a comparison of E(c) with the loss measure E (c) of the assignment in which the two classes m assigned to levels m, m + are interchanged (m = 1, 2 o., R - 1)o When the subscripts identifying classes by their priority level before the interchange, are maintained, p qmE(To) E(c)- Em(C) m-1 Pm1 1E(TO) Pmm+ E( T) m \ m+l \ / m-l.. / m-1\ i- p i- p 1 - p -3 ji j-1 j-

p q E(To) From (15) one can show Em(c) < E(c) if l 1- pPm+l ~Pj - Pm p+ j1 j1i where p =p q + p q O Then m m m+1 m+1q pq + 1- Mm _ Pm+) Pm holds whenever m <m~1 (17) am amp -m m+l But, (17) is also required in order for where p p pmqm + P qmflo Then p q assignments does not affect E(c) and hence the two description classes can be assigned to one priorityo By a succession of interchanges and combinations of classes having equal ratios, p/a, one arrives at a priority system of some number K of levels, with epP14

( >)1 ( > P The optimum schedule for a single processor without additional arrivals or with Poisson arrivals is therefore obtained by the same scheduling rule. 5. CONCLUDING REMARKS Cobham's result, from which (12) is obtained, holds also in the more general case where the processing time of any job in the description class assigned to priority i is not known with certainty, but has a probability distribution function F.i(T) with expected value i.o In this case, R 0 (T 2 qj'r dF (F) J = follows from the preceding discussion that the optimal scheduling policy is to assign description classes to priority levels so that P1 P2 PR ~> ->... > 1 "2 R The expected processing time is the only parameter of the processing time probability distribution that need be known to achieve optimal scheduling. The constraint of nonpreemptive service is rather severe in terms of the resulting average expected loss rate. In some applications, it may be possible to preempt any job in process and begin processing of another with negligible'. ~....... -. delay and without losing any of the processington the processing time acomplhed oneempted jobo Intuitively, it seems that since random arrivals did not introduce any modification of the single processor scheduling rule with nonpreemptive processing, the optimal preemptive-resume policy would require that at any time the queue was not empty the job which has the largest ratio of loss rate 15

to remaining processing time should be the one in service. It does not appear feasible to establish this rigorously by the method employed here, for it requires that the priority of a job be continuously changing while it is in processo A priority queueing model with such generality would be very difficult to solve. REFERENCES 1o Ao Cobham, "Priority Assignment in Waiting Line Problems,'' Operations Research, 2, 70-76, 1954. 2. Jo Holley, "Waiting Line Subject to Priorities," Operations Research, 2, 341-343, 1954o 3. J. Kiefer and JO Wolfowitz, "On the Characteristics of the General Queueing Process with Applications to Random Walk," Annals of Mathematical Statistics, 27, 147-161, 1956o 4. E. Lawler, "Computational Techniques for Scheduling Problems with Deferral Costs,' Cooley Electronics Laboratory TR-140, The University of Michigan, Ann Arbor, Michigan, July, 1963. (Also presented at the National meeting of the Association for Computing Machinery, Denver, Colorado, August 27-30, 1963)o 5. Ro McNaughton, "Scheduling with Deadlines and Loss Functions,' Management Science,, 1-12, 19590 6. A. Schild and Io Fredman, "On Scheduling Tasks with Associated Linear Loss Functions," Management Science, 7, 280-285, 1961o 7o Ao Schild and I. Fredman, vScheduling Tasks with Deadlines and Non-linear Loss Functions,? Management Science, 9 1962. 8o Wo Eo Smith, "Various Optimizers for Single Stage Production,"? Naval Research Logistics Quarterly, 3, 59-66, 1956, 16

DISTRIBUTION LIST 1. John McLean, EMIIF (1) RADC Griffiss AFB Rome, New York 2. Lt. L. W. Odell, EMIICA (2) RADC Griffiss AFB Rome, New York 3. Pat Langendorf, EMIIT (1) RADC Griffiss AFB Rome, New York 4. Fred Dion, EMIIT (1) RADC Griffiss AFB Rome, New York 5. Rome Air Development Center Griffiss AFB Rome, New York Attn: RAT (1) RAALD (1) RAAPT (1) RAL (1) RALC (1) RALS (1) RALT (1) RAO (1) RAD (1) RAS (1) RASG (1) ROAMA (ROAEPP-1) (4) EMIIH (5) EMIIT (5) EMIIF (5) EMIID (5) RASH (1) RASS (1) RAU (1) RAUA (1) RAUE (1) RAUM (1) RAUO (1) RAWC (1) RAWE (1) RAWI (1) RAYA (1) RAI (1)

DISTRIBUTION LIST (Continued) 6. GEEIA Griffiss AFB Rome, New York Attn: ROZMA (1) ROZMC (1) ROZME (1) ROZMN (1) ROZMCAT (1) 7. RAOL (Maj. Shields) (1) Griffiss AFB Rome, New York 8. RAOL (S/ L Tanner) (2) Griffiss AFB Rome, New York 9. AFSC Andrews AFB Washington 25, D. C. Attn: SCSE (1) SCLDE (1) SCFRE - (1) 10. Redstone Scientific Information Center (2) U. S. Army Missile Command Redstone Arsenal, Ala. Attn: Chief, Document Section 11. Bureau of Naval Weapons (2) Main Navy Building Washington 25, D. C. Attn: Tech. Lib. DL1-3 12. Chief, Bureau of Ships (1) Code 454 F Main Navy Building Washington 25, D. C. 13. Central Intelligence Agency (1) 2430 E Street NW Washington 25, D. C. Attn: OCR Mail Room 14. U. S. Army Material Command (1) Harry Diamond Laboratories Washington 25, D. C. Attn: AMXDO-TIB 15. Scientific and Technical Information Facility (2) P. O. Box 5700 Bethesda, Maryland Attn: NASA Representative (S-AK/DL) 18

DISTRIBUTION LIST (Continued) 16. Director (1) National Security Agency Ft. George G. Meade, Maryland Attn: C3/TDL 17. Commander (1) Naval Missile Center Tech Library (Code No. 3022) Pt. Mugu, California 18. Commanding Officer and Director (1) U. S. Navy Electronic Lab (Lib) San Diego 52, California 92152 19. Office of Chief of Naval Operations (Op-723 E) (1) Rm. 1602 Building T-3, Navy Department Washington 25, D. C. 20. Office of Naval Research (1) Chief Scientist (Code 427) Washington 25, D. C. 21. The Rand Corp. (Tech Lib) (1) 1700 Main Street Santa Monica, California 22. Hq TAC (DORQ-S) (1) Langley AFB Virginia 23. Hq TAC (OA) (1) Langley AFB Virginia 24. Commander, TAC Comm Region (1) Langley AFB Virginia 25. USAFSS (ECD) (1) San Antonio Texas 26. Commanding General (2) US Army Electronic Proving Ground Attn: Tech Library Fort Huachuca, Arizona 27. Commanding Officer (1) US Army Electronics RandD Lab Attn: SELRA/ADT Ft. Monmouth, New Jersey 19

DISTRIBUTION LIST (Continued) 28. Institute of Technology Library (1) MCLI-LIB, Bldg 125 Area "B" Wright-Patterson AFB Ohio 29. NAFEC Library (1) Bldg. 3 Atlantic City, New Jersey 30. Commandant (1) US Army War College (Lib) Carlisle Barracks, Pa. 31. Commanding Officer (1) US Army Electronic Research Unit P 0 Box 205 Mountain View, California 32. Electronic Defense Labs (1) Attn: Library P 0 Box 205 Mountain View, California 33. U S Naval Avionics Facility (Library) (1) Indianapolis 18 Indiana 34. Commander US Naval Air Dev Cen (NADC Lib) (1) Jo hnsville, Pa. 35. Director (2) US Naval Research Lab (Code 2027) Washington 25, D. C. 36. Hq USAF Attn: AFRSTE (1) AFRDPC (2) AFGOA (1) Washington 25, D. C. 37. National Aeronautics and Space Admin (3) Langley Research Center Langley Station Hampton, Virginia Attn: Librarian 38. RTD (RTH) (1) Bolling AFB 25 D. C. 39. Federal Aviation Agency (1) Information Retrieval Br Hq-630 Washington 25, D. C. 20

DISTRIBUTION LIST (Continued) 40. RTD (RTHR/Capt. K. O. Malkemes (2) BollingAFB, D. C. 20332 41. OSD (DDR and E/Mr. Willie Moore (2) Washington D C 20330 42. Hq USAF (AFRST/ Lt. Col.. A. H. Grinsted, Jr.) (1) Washington D C 20330 43. Advanced Research Projects Agency (1) Command and Control Research (Dr. J. C. R. Licklider) Washington, D. C. 44 National Security Agency (1) Engineering Research Div, Code R42 (Mr. O. H. Bartlett, Jr.) Fort Meade, Maryland 21

UNIVERSITY OF MICHIGAN 3 9015 02826 3666