In job sequencing problema l’obiettivo è quello di trovare la sequenza di posti di lavoro,che viene completato entro le loro scadenze e dare il massimo profitto.
Se un insieme di n posti di lavoro sono dati che sono associati con scadenze e profitto è guadagnato e un lavoro è completato entro la sua scadenza. Questi lavori devono essere ordinati in modo tale che ci sia il massimo profitto.
Facciamo un esempio. Come mostrato nella figura 1.1 viene fornita una serie di lavori in cui ogni lavoro ha una scadenza e un profitto associato se il lavoro è terminato prima della scadenza. È anche dato che ogni lavoro richiede una singola unità di tempo, quindi la scadenza minima possibile per qualsiasi lavoro è 1. Come massimizzare il profitto totale se è possibile pianificare un solo lavoro alla volta.
Una soluzione semplice consiste nel generare tutti i sottoinsiemi di un determinato insieme di lavori e verificare la fattibilità dei singoli sottoinsiemi in quel sottoinsieme. Tieni traccia del massimo profitto tra tutti i sottoinsiemi fattibili. La complessità temporale di questa soluzione è esponenziale.Possiamo anche risolvere questo problema usando il metodo greedy che è più ottimale della soluzione semplice.Quindi consente di risolvere questo problema tramite il metodo greedy.
Per risolvere il problema di sequenziamento del lavoro tramite il metodo greedy seguire questa procedura:
- Ordina tutti i lavori in ordine decrescente di profitto.
- Inizializza la sequenza dei risultati come primo lavoro nei lavori ordinati.
- Segui i lavori n-1 rimanenti.
- Se il lavoro corrente può essere inserito nella sequenza di risultati corrente senza perdere la scadenza, aggiungere il lavoro corrente al risultato. Altrimenti ignorare il lavoro corrente.
Come si può vedere nella figura 1.1 i posti di lavoro sono già in ordine decrescente di profitto.Qui il lavoro 1 ha il profitto più alto e la scadenza è 3 quindi imposta quel lavoro tra 2-3 come mostrato in figura 1.2.Il lavoro 2 ha il secondo profitto più alto e la scadenza è 4 quindi imposta quel lavoro tra 3-4 e fai lo stesso con tutti jobs.So la sequenza finale è J4-J3-J1-J2 e il profitto totale è 110.
Puoi preferire il codice per questo algoritmo a https://www.geeksforgeeks.org/job-sequencing-problem.
La complessità temporale di questa soluzione è O (n2).Può essere ottimizzata dalla struttura dati disgiunta.
Spero che ti piaccia l’articolo.Grazie:)
