Massimizza il profitto nelle attività dell'unità di pianificazione con dipendenze

Question

Problema Ho n lavori da pianificare in P secondi su un numero illimitato di macchine con dipendenze tra i lavori, ad es. per ogni lavoro c'è una serie di lavori che devono essere programmati solo dopo che questo lavoro è finito. Il profitto per la pianificazione del lavoro i ^th in j ^th secondo su qualsiasi macchina è f (i, j), che è positivo.
E il mio obiettivo è massimizzare il profitto totale pianificando ogni lavoro esattamente una volta al massimo P secondi.

Possiamo presumere che tutti i lavori possano essere programmati in P secondi sempre.

Tutto è noto in anticipo, ovvero un problema non in linea.

Anche 0 < = f (i, j) < = B. per tutto io, j.

e il numero di dipendenze è di O (n).

È questo problema facile? [Può essere causa di vincoli finiti]

Il mio approccio
Per semplicità, in primo luogo supporre che per un lavoro il suo profitto non dipende dal tempo.
Questo è f (i, j) è indipendente da j per tutti i e dipende solo da i.
Quindi funzionerà qualsiasi ordinamento topologico che si adatti a P secondi.
Se non c'è dipendenza, anche noi scegliamo il tempo di guadagno più alto per ogni lavoro e anche questo è facile.

Ma il problema è quando il profitto per un lavoro varia nel tempo con le dipendenze, in questo caso, non riesco a pensare ad alcun algoritmo generale.

Ho problemi a gestire le dipendenze tra i lavori. Esistono risorse per gli algoritmi di pianificazione delle attività dipendenti delle unità online?

Si prega di condividere qualsiasi idea che può aiutare ...

Aggiornamento: ho aggiunto i limiti per i vari parametri in quanto potrebbero essere necessari per l'analisi del problema.

Answer 1

Questo è un problema di programmazione dinamica. Supponiamo per semplicità che tutti i profitti siano non negativi.

Definire F(i, j) essere il massimo profitto da effettuare dalla pianificazione del i 'th lavoro e tutte le cose che dipendono da esso (in modo ricorsivo verso il basso) pari o successiva alla j' th secondo o -1 in caso di impossibilità .

Poi F(i, j) è -1 se F(i_1, j+1) è -1 per qualsiasi dipendenza i_1 di i. Altrimenti è il più grande di (f(i, j) più la somma di F(i_1, j+1)) o F(i, j+1).

E quindi la tua risposta è la somma di F(i, 0) per tutti i lavori i senza dipendenze.

(Senza macchine illimitate questo problema sarebbe diventato NP-hard ...)

---

Ecco un esempio di come utilizzare il vostro problema per modellare MAX-SAT equazioni in cui ogni clausola ha tutti i termini non negati o tutti i termini negati.

Supponiamo di avere 4 variabili booleane A, B, C e D. Ad esempio, supponiamo di voler ottenere la massima soddisfazione per l'equazione (A && B) || (!A && !C) || (!B && !C && !D) || (C && D). (Dove ! significa non, && mezzi e, e || mezzi o.)

Usiamo la notazione J1 > J2 per i lavori in cui J1 ha da eseguire prima J2. E distribuire tra parentesi in modo che J1 > (J2, J3) significhi che J1) is a dependency for both J2 and J3`.

Ora per modellare i booleani impostiamo 12 lavori. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3 e D1 > D2 > D3. Quindi i lavori A2, B2, C2, D2 devono essere eseguiti al momento 2 o 3 e il valore booleano A è la verità dell'affermazione "A2 avviene all'ora 2". E allo stesso modo per gli altri booleani.

Tutti questi lavori hanno un profitto di 1 indipendentemente dall'orario di esecuzione. Abbiamo introdotto 3 volte tanti lavori booleani, ma finora questo è semplice.

Ora aggiungiamo lavori per le clausole. Ognuno di questi lavori avrà un profitto di 11 se viene eseguito in secondi 2 o 3 e 1 in caso contrario. Il tuo massimo profitto sarà quindi raggiunto quando trovi le impostazioni per i tuoi valori booleani che massimizzano il numero di clausole che sono vere.

(A2, B2) > J1 modelli la verità di (A && B).

J2 > (A2, C2)) modelli la verità di (!A && !C).

J3 > (B2, C2, D2) modelli la verità di (!B && !C && !D).

(C2, D2) > J4 modelli la verità di (C && D).

Questa è ancora una trasformazione semplice, con il numero di lavori aggiunti uguale al numero di clausole.

Quindi stiamo modellando i problemi MAX-SAT con la pianificazione. Ma non possiamo modellarli tutti. In particolare, non abbiamo modo di modellare le clausole con la negazione mista come (A && !B). Quindi, anche se MAX-SAT è NP-difficile, è possibile che questa versione limitata non lo sia. Tuttavia, altre versioni limitate di MAX-SAT, ad esempio MAX-2SAT, tendono ad essere NP-hard, ed è mia intuizione che anche questa sarà la stessa.

Ma per una dimostrazione o confutazione di tale intuizione, si dovrebbe chiedere su un forum più appropriato. Mi piace https://cs.stackexchange.com/.