A Task Scheduling Algorithm for Minimum Busiest Procesor Idle Time

This paper provides a heuristic to minimize the idle time of the busiest processor in a system in which the number of modules to be executed by every processor has been predetermined for a given precedence graph. Except for the busiest processor, the assignment of modules to the other processors is done as evenly as possible. Each of the modules involved is of unit size. An exhaustive enumeration solution of the problem is of NP-complete complexity. The heuristic presented in this paper is of polynomial time.