în problema secvențierii locurilor de muncă,obiectivul este de a găsi secvența de locuri de muncă, care este finalizată în termenele limită și oferă profit maxim.
dacă sunt date un set de n locuri de muncă care sunt asociate cu termenele limită și se câștigă profit și un loc de muncă este finalizat până la termenul limită. Aceste locuri de muncă trebuie comandate astfel încât să existe un profit maxim.
să luăm un exemplu. După cum se arată în figura 1.1 este prezentată o serie de locuri de muncă în care fiecare loc de muncă are un termen limită și un profit asociat dacă lucrarea este terminată înainte de termenul limită. De asemenea, fiecare loc de muncă durează o singură unitate de timp, astfel încât termenul minim posibil pentru orice loc de muncă este 1. Cum să maximizați profitul total dacă poate fi programat un singur loc de muncă la un moment dat.
o soluție simplă este de a genera toate subseturile setului dat de locuri de muncă și de a verifica subsetul individual pentru fezabilitatea locurilor de muncă din acel subset. Urmăriți profitul maxim între toate subseturile fezabile. Complexitatea în timp a acestei soluții este exponențială.De asemenea, putem rezolva această problemă folosind metoda greedy, care este mai optimă decât soluția simplă.Deci, vă permite să rezolve această problemă prin metoda greedy.
pentru a rezolva problema de secvențiere a jobului prin metoda greedy, urmați acești pași:
- Sortați toate locurile de muncă în ordinea descrescătoare a profitului.
- inițializați secvența de rezultate ca prima lucrare în lucrări sortate.
- faceți următoarele pentru locurile de muncă N-1 rămase.
- dacă jobul curent se poate încadra în secvența curentă de rezultate fără a pierde termenul limită, adăugați jobul curent la rezultat. Altfel ignora locul de muncă curent.
după cum puteți vedea în figura 1.1 locurile de muncă sunt deja în ordinea descrescătoare a profitului.Aici jobul 1 are cel mai mare profit, iar termenul limită este 3, deci Setați acel job între 2-3, așa cum se arată în figura 1.2.Job 2 are al doilea cel mai mare profit, iar termenul limită este 4, deci Setați acel loc de muncă între 3-4 și faceți același lucru tuturor jobs.So secvența finală este J4-J3-J1-J2, iar profitul total este de 110.
puteți prefera codul pentru acest algoritm la https://www.geeksforgeeks.org/job-sequencing-problem.
complexitatea în timp a acestei soluții este O(n2).se poate optimizat prin structura de date disjuncte.
Sper că vă place articolul.Multumesc:)
