Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

Abstract

In this article we consider the problem of scheduling unit processing time multiprocessor tasks on dedicated processors with repetition and availability constraints. W present collected results of complexity of this problem for different types of instances and scheduling criteria. To describe the problem we use the model of edge coloring of hypergraphs. W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.