Periodic Job Scheduling in a Distributed Processor System

This investigation considers the problem of the nonpreemptive scheduling of a set of independent periodic jobs in a computer system characterized by a collection of processors, memories, and interconnection mechanisms. Such a collection of resources can be used to perform the functions of a process control environment as are found, for example, in the avionics of a military or commercial aircraft. The distribution of these resources permits weight, volume, power, cost, and reliability requirements to be satisfied. Each periodic job is characterized by its frequency and its execution time. The inverse of the frequency, the period, is assumed to be an integer, and the initiation time and the completion time of job must be strictly met. An optimal algorithm is developed for a job set whose members are related by a binary frequency distribution. That is, if the jobs in the set are ordered in terms of decreasing job execution frequency, then fi = 2fi+1. The optimal result is generalized to include conditions in which the jobs are related by fi = kfi+1, where k is an integer.