PERIODIC LOADING PROBLEM: FORMULATION AND HEURISTICS.

The periodic loading problem involves the allocation of periodically-occurring tasks to the time-slots of a synchronous server in such a way as to minimize the maximum utilization of any time-slot. It arises when a time-division-multiplex communications bus collects data from a collection of periodically-producing sensors, e. g. , the MIL-STD-1553 protocol. This paper formulates the problem, gives bounds on the solution, and shows it contains the minimum makespan problem, hence is NP-complete. Heuristic procedures are given and their performance illustrated on a (actual) problem for which a solution is found within 1% accuracy. In addition, an empirical study for the heuristic procedures is conducted on an extensive set of artificial problems.