v úloze sekvenování problém cílem je najít posloupnost pracovních míst, která je dokončena v jejich lhůtách a dát maximální zisk.
je-li zadána sada n pracovních míst, která jsou spojena s termíny a zisk je získán a práce je dokončena do jejího termínu. Tyto práce je třeba objednat tak, aby byl maximální zisk.
Vezměme si jeden příklad. 1.1 je uvedena řada pracovních míst, kde má každé pracovní místo termín a související zisk, pokud je pracovní místo dokončeno před termínem. Je také dáno, že každé zaměstnání trvá jednu jednotku času, takže minimální možný termín pro jakoukoli práci je 1. Jak maximalizovat celkový zisk, pokud lze naplánovat pouze jednu práci najednou.
jednoduchým řešením je generovat všechny podmnožiny dané sady úloh a zkontrolovat jednotlivé podmnožiny pro proveditelnost úloh v této podmnožině. Sledujte maximální zisk mezi všemi proveditelnými podmnožinami. Časová složitost tohoto řešení je exponenciální.Tento problém můžeme také vyřešit pomocí chamtivé metody, která je optimálnější než jednoduché řešení.Takže umožňuje vyřešit tento problém pomocí chamtivé metody.
Chcete-li vyřešit problém sekvenování úlohy pomocí chamtivé metody, postupujte takto:
- Seřadit všechny úlohy v sestupném pořadí zisku.
- inicializujte výslednou sekvenci jako první úlohu v tříděných úlohách.
- proveďte následující pro zbývající N-1 úlohy.
- pokud se aktuální úloha vejde do aktuální sekvence výsledků bez zmeškání termínu, přidejte k výsledku aktuální úlohu. Jinak ignorujte aktuální práci.
jak můžete vidět na obrázku 1.1 pracovní místa jsou již v sestupném pořadí zisku.Zde job 1 má nejvyšší zisk a lhůta je 3, takže nastavte tuto práci mezi 2-3, jak je znázorněno na obrázku 1.2.Job 2 má druhý nejvyšší zisk a termín je 4, takže nastavte tuto práci mezi 3-4 a udělejte to samé pro všechny jobs.So konečná sekvence je J4-J3-J1-J2 a celkový zisk je 110.
můžete preferovat kód pro tento algoritmus na https://www.geeksforgeeks.org/job-sequencing-problem.
časová složitost tohoto řešení je O(n2). může být optimalizována disjunktní datovou strukturou.
doufám, že se vám článek líbí.Děkuji:)
