w job sequencing problem celem jest znalezienie sekwencji zadań, która jest zakończona w ich terminach i dać maksymalny zysk.
jeśli podano zestaw N miejsc pracy, które są związane z terminami i zysk jest osiągnięty, a praca jest zakończona w terminie. Te miejsca pracy muszą być uporządkowane w taki sposób, aby uzyskać maksymalny zysk.
weźmy jeden przykład. Jak pokazano na rysunku 1.1 tablica miejsc pracy jest podana, gdzie każda praca ma termin i związany z nim zysk, jeśli praca jest zakończona przed terminem. Przyjmuje się również, że każde zadanie zajmuje jedną jednostkę czasu, więc minimalny możliwy termin dla każdej pracy to 1. Jak zmaksymalizować całkowity zysk, jeśli tylko jedna praca może być zaplanowana na raz.
prostym rozwiązaniem jest wygenerowanie wszystkich podzbiorów danego zbioru zadań i sprawdzenie poszczególnych podzbiorów pod kątem wykonalności zadań w tym podzbiorze. Śledź maksymalny zysk wśród wszystkich możliwych podzbiorów. Złożoność czasowa tego rozwiązania jest wykładnicza.Możemy również rozwiązać ten problem za pomocą metody greedy, która jest bardziej optymalna niż proste rozwiązanie.Więc rozwiążmy ten problem metodą chciwości.
aby rozwiązać problem sekwencjonowania zadania za pomocą chciwej metody wykonaj następujące kroki:
- Sortuj wszystkie prace w kolejności malejącej zysku.
- Inicjalizuj sekwencję wyników jako pierwsze zadanie w posortowanych zadaniach.
- wykonuj następujące czynności dla pozostałych N-1.
- jeśli bieżące zadanie może zmieścić się w bieżącej sekwencji wyników bez pominięcia terminu, dodaj bieżące zadanie do wyniku. W przeciwnym razie zignoruj bieżące zadanie.
jak widać na rysunku 1.1 Miejsca pracy są już w malejącej kolejności zysku.Tutaj Zadanie 1 ma najwyższy zysk, a termin wynosi 3, więc ustaw zadanie między 2-3, Jak pokazano na rysunku 1.2.Zadanie 2 ma drugi najwyższy zysk, a termin to 4, więc ustaw zadanie między 3-4 i zrób to samo wszystkim jobs.So ostatnia Sekwencja to J4-J3-J1-J2, a całkowity zysk to 110.
kod dla tego algorytmu możesz wybrać pod adresem https://www.geeksforgeeks.org/job-sequencing-problem.
złożoność czasowa tego rozwiązania to O(n2).można ją zoptymalizować za pomocą rozproszonej struktury danych.
mam nadzieję, że artykuł ci się spodoba.Dziękuję:)
