×

Scheduling multiprocessor tasks to minimize schedule length. (English) Zbl 0604.68040

The problem considered in this paper is the deterministic scheduling of tasks on a set of identical processors. However, the model presented differs from the classical one by the requirement that certain tasks need more than one processor at a time for their processing. This assumption is especially justified in some microprocessor applications and its impact on the complexity of minimizing schedule length is studied. First the authors concentrate on the problem of non-preemptive scheduling. In this case, polynomial-time algorithms exist only for unit processing times. We present two such algorithms of complexity O(n) for scheduling tasks requiring an arbitrary number of processors between 1 and k at a time where k is a fixed integer. The case for which k is not fixed is shown to be NP-complete. Next, the problem of preemptive scheduling of tasks of arbitrary length is studied. first an algorithm for scheduling tasks requiring one or k processors is presented. Its complexity depends linearly on the number of tasks. Then, the possibility of a linear programming formulation for the general case is analyzed. The paper creates a new direction in scheduling theory.
Reviewer: R.Słowinski

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI