Planowanie rezerwacji (nie restauracji) z pytonem

Question

Piszę aplikację python, która używa OpenStack, aby zapewnić studentom dostęp do ograniczonej liczby maszyn wirtualnych.

Studenci mogą rezerwować, teraz lub w przyszłości.

Muszę ograniczyć liczbę maszyn wirtualnych zaplanowanych w dowolnym momencie do X, jednocześnie umożliwiając studentom rezerwowanie vms, jeśli są dostępne miejsca/rezerwacje.

Obiekty rezerwacyjne wyglądają jak poniżej (sqlalchemy). Znałbym czas rozpoczęcia i długość żądanego zastrzeżenia, w którym to momencie muszę przejść przez istniejące zastrzeżenia i sprawdzić, czy w żądanym okresie istnieje zbyt wiele zastrzeżeń. Pola * _job są nazwami zadań APScheduler.

class Reservation(Entity): 
    student = ManyToOne('Student', required=True) 
    class_id = ManyToOne('Class', required=True) 
    image = ManyToOne('Image', required=True) 
    # openstack image id filled in once the instance is started 
    instance_id = Field(UnicodeText) 

    # apscheduler jobs 
    stop_instance_job = Field(UnicodeText) 
    start_instance_job = Field(UnicodeText) 
    warn_reservation_ending_job = Field(UnicodeText) 
    check_instance_job = Field(UnicodeText) 

Jakieś wskazówki, gdzie szukać przykładów algorytmów harmonogramów lub coś w tym stylu? Nie jestem nawet pewien, czego szukać ...

Dzięki.

Answer 1

Powinieneś przejrzeć Harmonogramy oparte na sieci. Zwykle harmonogramy nie znają prawdziwego czasu wykonania (lub czasu użycia zasobów), a skomplikowane heurystyki są używane do odgadnięcia, jak długo potrwa problem (zobacz taką heurystykę w siatce harmonogramu pod adresem: PDF download Describing Scheduling on Grid basis). Prostsze podejście z podstawową siatką do reprezentowania obciążenia w czasie najprawdopodobniej spełni Twoje potrzeby. Python nie ma żadnych niesamowitych bibliotek obiektów gridowych, które znam (kilka wdrożyłem w C++ i Pythonie wcześniej i nie są one zbyt trudne). Powinieneś spojrzeć na pakiet numpy, aby łatwiej interpretować obiekty wielowymiarowe - które mogą z łatwością emulować lub implementować siatki.

Msw wspomniała o algorytmie bankierskim Dijkstry, który jest formą planowania zadań - jednak twój problem dba o stan przyszły bardziej niż bieżący stan i pozwala dokładnie przewidzieć (znać prawdziwą wartość) czasów zadań. W związku z tym wystarczająca może być T (timesteps) przez N (liczba zasobów - może być tylko 1) przez M (maksymalna rezerwacje zasobów), które wypełnia się, gdy zadania są zarejestrowane. Ustalenie, czy określone zadanie może zostać zaplanowane w danej szczelinie czasowej, sprawdza O (task_length * M) w podsekcji siatki (start, stop) x (required_resources) x (1, M) dla pustego gniazda.

Znalezienie odpowiedniego miejsca dla konkretnego zlecenia (wybór czasu rozpoczęcia) jest trudniejszym zadaniem i byłoby osiągnięte przez zmodyfikowany algorytm Dijkstry lub z dowolnego standardowego harmonogramu (komentarz msw jest bardziej przydatny w tym zadaniu niż w przypadku kontrola szczelności czasowej). Zauważ, że wiele treści programu planującego w trybie online jest specyficznych dla harmonogramowania procesów systemu operacyjnego, które dbają bardziej o typ operacji (operacje we/wy lub nie) i kar za dłuższe niż oczekiwano użycie abstrakcyjnego zasobu. Wyszukiwania google dla programistów często dostarczają implementacji harmonogramu Linuksa, a nie technik arbitralnych danych. Spróbuj wyszukać Najkrótsze harmonogramy zadań, które są często prostsze i mniej zależne od zadań systemu operacyjnego, gdy są wyjaśnione.