Analysis of multiprocessor task scheduling

This paper considers the problem of scheduling multiprocessor tasks on a non-pre-emptive m-processor environment in which the processors are assumed to be identical and the multiprocessor tasks being scheduled are independent. The main difference between the multiprocessor task scheduling problem and the conventional task scheduling problem is that the 'multiprocessor tasks' can require more than one processor, while the 'conventional tasks' require only one processor at a time. The complexity of determining an optimal schedule in the multiprocessor tasks scheduling problem is NP-hard. A largest width with largest processing time first (LWLPT) scheduling algorithm is proposed. For comparison, the worst performance bounds of the list scheduling (LS) algorithm and the LWLPT scheduling algorithm are derived, respectively.