Optimal scheduling of homogeneous job systems

Homogeneous job systems are systems in which all of a finite set of jobs to be processed by the system have exactly the same processing requirements. This paper assumes that each job first executes an input task requiring an input unit (channel or controller) for some amount of time T_c along with a memory unit. Then it executes a computational task requiring a processing unit and the memory for some amount of time T_p. Under these assumptions, it is possible to derive some inequalities concerning the relative number of memory, input, and processor units which can be efficiently used by the system as a function of T_c and T_p. The scheduling problem is to order tasks and assign resources to them in such a way as to minimize some cost function. The cost functions considered in this paper are job set finishing time and dwell time. Some theorems are stated and proved which yield closed form expressions for the minimum finishing time in batch and in time-shared systems as a function of the number of jobs, memories, processors, input units, and T_c and T_p. The purpose of this study is to derive some general results which aid in the efficient utilization of multiprocessor computer systems. Although this study is directed toward a specific type of homogeneous system, it is shown that the results are applicable to other systems (e.g., systems with output).