Multiprocessor Scheduling Problem
Shaharuddin Salleh, Albert Y. Zomaya, Stephan Olariu, Bahrom B. Sanugi · 2005
Chapter 9 discusses the task scheduling problem which is a component of the parallel and distributed computing system. The problem is about mapping a set of tasks from a task graph onto a set of processors in a parallel computing system with the objective of achieving the minimum schedule length. The tasks have precedence relationship determined from the directed links in the task graph with communication costs. A method called the path maximum magnitude (PMM) has been introduced for scheduling the tasks based on a priority list. This list consists of the sorted tasks based on the distance of the tasks from their root. Results from scheduling are displayed using the Gantt charts which show the starting time, completion time and length of each task. The model can be extended to include parameters that affect the machine performances, such as the initial startup cost, the transmission rate, the contention rate and the cabling mechanism