Dynamic job scheduling in a distributed computer network with functionally similar nodes

Abstract

This research examines the operational problem of dynamic job scheduling in a distributed computer network with functionally similar nodes. A distributed computer network is considered to be an interconnection of computer systems (nodes) and communication facilities with general (while not necessarily complete) node-to-node communication links. In a computer network with functionally similar nodes the efficiency of the job scheduler may be critical to the success of the network. Current trends in computing are noted that contribute toward functional compatibility across a wide range of computer systems. The general philosophy of the proposed scheduler is one of periodic review, in which jobs are submitted to the network and an allocation decision is made periodically. At each decision point all jobs currently in the network are assigned by the algorithm so that some objective function is improved and all problem constraints are met. Objective functions that can be considered include maximizing throughput, minimizing turnaround time, and minimizing cost. The concept of an affinity matrix is introduced into the scheduling algorithm. The affinity values reflect the relative value of scheduling a particular job on a particular node and may be based on processing times, costs, processing characteristics, user induced bias, and any other pertinent data. A tradeoff for jobs between nodes will occur as a result of these values. Determination of these tradeoff values within the operational constraints of dynamic network job allocation is a major problem in the scheduling research. A solution procedure is described, a computer coded implementation of that procedure is given, and computational results are presented.