Kolejkowanie zadań na klastrze maszyn niejednorodnych

W tej pracy badamy problem schedulingu zadań on-line na heterogenicznej infrastrukturze chmurowej wyposażonej w różne zasoby. Każde zadanie jest opisane przez czas zgłoszenia, liczbę operacji, wektor opisujący konieczne zasoby i priorytet. Maszyny są opisane popprzez krotkę dostępnych zasobów, które różnią się w zależności od maszyny. Każda maszyna może przetwarzać wiele zadań jednocześnie, pod warunkiem, że dysponuje wystarczającą ilością zasobów, aby spełnić wymagania wszystkich uruchomionych zadań. Niedozwolone jest przerywanie raz rozpoczętych zadań.Naszym celem jest stworzenie algorytmu przypisującego zadania do maszyn i decydującego o kolejności ich wykonania. Ponieważ nie istnieją algorytmy rozwiązujące takie problemy w czasie wielomianowym, został on podzielony na dwie fazy i przybliżony przy użyciu heurystyk. Do wyboru maszyn dla przychodzących zadań, zaprojektowano i nauczono sieć neuronową. Rozwiązanie problemu kolejkowania zadań na jednej maszynie zostało rozwuiązane w oparciu o przybliżenia rozwiązań bin-packingu.Wszystkie prezentowane rozwiązania zostały przetestowane na specjalnie zaprojektowanym symulatorze obliczeń chmurowych. W tym celu wykorzystano również dane na temat prawdziwych zadań liczonych wczesniej na naszych maszynach. Symulator posłużył również do wytrenowania sieci neuronowych.

In this work we investigate a problem of on-line job scheduling on a heterogeneous infrastructure with multiple resources. In this setting, each job is described by the release time, number of operations and a vector of necessary resources. We also allow for prioritization of the jobs. Machines are described by the vector of available resources which differs from one machine to the other. Each machine can process multiple jobs at the same time provided that it has enough resources to satisfy requirements of all jobs simultaneously. The whole considered infrastructure works in the non-preemptive manner.Our goal is to create a scheduling algorithm assigning jobs to machines and deciding an order of execution. Because such scheduling problems are notoriously difficult to solve, or even to approximate the optimal solution, we divided it into two phases and used heuristics to achieve good enough solutions. To handle machine selections for incoming jobs a machine learning model was designed and trained. Approximating the best job execution order on a single machine was done basing on solutions of the bin packing problem.All presented solutions were tested on specially designed cloud computation simulator. For this purpose we also used data about real life jobs parameters from our records. Simulator was also used for training of the machine learning models.