Task scheduling in multiprocessing systems

This paper addresses the task scheduling problem in many of its variations and surveys the major solutions. It concerns scheduling program tasks on parallel and distributed systems. The tasks are the consumers, and they are represented via directed graphs called task graphs. The processing elements are the resources, and their interconnection networks are represented via undirected graphs. The scheduler generates a schedule in the form of a timing diagram called the Gantt chart, which is used to show the allocation of the parallel program tasks onto the target machine processors and the execution order of the tasks. Models are provided for representing parallel programs, parallel systems, and communication cost. Several algorithms are presented for solving the scheduling problem in some special cases.