×

On the complexity of multiprocessor task scheduling. (English) Zbl 0844.68019

Summary: The problem addressed here is the complexity of scheduling multiprocessor tasks, i.e. tasks which may require more than one processor simultaneously. This model seems natural for many parallel applications, however, is different than the standard approach in the scheduling theory. In this paper, we analyze both cases when the task requires a number of processors simultaneously, and when the task requires a set of processors simultaneously. In the former case the problem of preemptive scheduling is NP-hard in general. Next, we show that the problem of non-preemptive scheduling on four processors, when tasks can be executed on any subset of processors, is solvable in pseudo-polynomial time in the absence of uni-processor tasks.
Finally, the problem of non-preemptive scheduling multiprocessor tasks, requiring a set of processors simultaneously for \(L_{\max}\) criterion, is shown to be strongly NP-hard even for two processors.

MSC:

68N25 Theory of operating systems
68M99 Computer system organization
PDFBibTeX XMLCite