Miglior lavoro di pianificazione

Question

Ho lavorato a questa domanda e non riesco a trovare la risposta giusta. Qualcuno può aiutarmi per favore con questo?

Ci vengono dati N lavori [1,..,N]. Otterremo uno stipendio S(i) >= 0 per ottenere un lavoro i completato e una detrazione D(i) >= 0 che si somma per ogni giorno che passa.

Avremo bisogno di T(i) giorni per completare il lavoro i. Supponiamo che il lavoro i sia fatto il giorno d, riceverai S(i) - d.D(i) in ricompensa. La ricompensa può essere negativa se d è troppo grande. Siamo in grado di passare i lavori nel processo e lavorare sui lavori in qualsiasi ordine, ovvero se iniziamo il lavoro 1 che richiede 5 giorni al giorno 1, non dobbiamo passare 5 giorni consecutivi sul lavoro 1.

Come possiamo decidere il miglior programma di lavoro, in modo che possiamo completare tutti i lavori e ottenere il massimo dello stipendio?

Answer 1

Penso che shapiro abbia ragione. È necessario determinare una formula di costo ponderata appropriata per ogni attività. Deve tenere conto dei giorni rimanenti, della deduzione giornaliera e della deduzione totale.

Una volta ottenuto il costo ponderato, è possibile ordinare l'elenco delle attività in base al costo ponderato ed eseguire un giorno di lavoro sulla prima attività nell'elenco (dovrebbe essere quella che avrà un costo maggiore se non completata). Quindi ricalcolare il costo ponderato per tutte le attività ora che è trascorso un giorno, ordinare l'elenco e ripetere fino al completamento di tutte le attività.

Generalmente quando si stanno ottimizzando gli orari nel mondo reale, questo è l'approccio. Individua quale attività deve essere lavorata per prima, lavoraci sopra, quindi ricalcola per vedere se è necessario cambiare attività o continuare a lavorare su quella corrente.

Answer 2

Dopo la discussione di cui sopra:

Per ogni lavoro i, calcolare il un giorno di ritardo costo come X(i) = D(i)/T(i) e ordinare i posti di lavoro da essa. Forse anche solo ordinare da D(i) dal momento che quando si sceglie un lavoro si è non scegliere gli altri - quindi ha senso scegliere quello con la detrazione più costosa. Esegui i lavori con questo ordine per minimizzare le spese di detrazione.

Anche in questo caso, si presume che S(i) sia un premio fisso per ciascun lavoro, indipendente dal giorno esatto in cui è stato completato, e che tutti i lavori debbano essere eseguiti.

Answer 3

Prima dimenticarsi di S (i). Stai facendo tutti i lavori che ottieni comunque tutti i premi.

Secondo, non c'è motivo di interrompere un'attività e passare a un'altra. Diciamo che hai lavori A e B. La deduzione che ottieni per quella che finisce per ultima è la stessa (prenderà T (A) + T (B) per finirlo indipendentemente da come pianifichi). La detrazione per l'altro lavoro può aumentare solo se si cambia perché ci vorrà più tempo per terminarlo. Quindi sei meglio se lasci cadere l'interruttore.

Ora il problema è ordinare le attività in modo da ottenere un ammontare minimo di penalità. Non sono sicuro di cosa sia il prossimo. È possibile selezionare il primo lavoro per ridurre a icona T (x) * sum (d) (dato che si esegue il commit su dong job x ogni cosa incorrerà in T (x) giorni di ritardo). Oppure puoi scegliere l'ultimo lavoro dato che sai che pagherai la somma (T) * d (x) (sai quando finirà). Uno dice ordine per T (x) l'altro dice ordine per d (x) e sono entrambi sbagliati.

Probabilmente la soluzione è una programmazione dinamica in questo spazio, ma al momento mi sfugge.