Generalization of the Problem of Creating a Multiprocessor Schedule with Interrupts

Abstract

We consider the problem of creating a multiprocessor schedule for a set of jobs that allow interruptions and switching from one processor to another. It is assumed that processing interrupts and switches requires time overhead. This condition transfers the problem from the class of polynomially solvable to the class of NP-hard ones. An algorithm has been developed based on the methodology of V.S. Tanaev for compiling a multiprocessor schedule without taking into account the costs of interruptions and switching. The technique includes a packing procedure for the case when jobs have a common deadline, as well as a procedure for reducing the original problem to a network flow problem for the case of arbitrary deadlines. In this case, the well-known pseudo-polynomial algorithm for creating an admissible multiprocessor schedule for continuous jobs with a common deadline is also used.