pianificazione dei processi efficienti con in calo i profitti su più macchine

Question

Problema: Si consideri il problema di pianificazione di posti di lavoro n su macchine M dove ogni lavoro ho un tempo di elaborazione p _i e dà un profitto g _i (t) se completato da tempo t. Tutti i lavori vengono rilasciati al momento 0. Tutti i _i (t) sono funzioni non crescenti. Per semplicità, possiamo supporre che le macchine non siano preventive.

Per M = 1 e funzioni di profitto in diminuzione lineare. questo problema può essere risolto in O (n) usando l'algoritmo greedy. Ma per le funzioni generali è NP-completo.

Sono interessato al caso generale. Per favore dammi qualsiasi link di documenti o materiali di risorse per il problema. Ho cercato su internet ma non ho trovato nulla di interessante per M> 1, sebbene ci sia un lavoro precedente sull'approssimazione dei limiti per M = 1.

Si prega di notare che non mi aspetto di risolvere questo problema, ma solo di avere un lavoro precedente sui problemi simili, se presenti. E se hai qualche idea che possa aiutarti, sentiti libero di condividere.

Desidero sapere quali limiti sono noti per questo problema con m macchine e n lavori con stesse date di rilascio e funzioni di profitto generali non crescenti. Ho trovato una carta verso quella direzione

http://arxiv.org/pdf/1008.4889v1.pdf

hanno dato un O (1) ravvicinamento quando tutti i lavori hanno tempi di rilascio identici. Voglio trovare una documentazione simile per il problema e quali idee hanno usato per risolvere il problema.

Answer 1

È possibile iniziare con una "soluzione golosa" utilizzando una regola di spedizione che, ad es. minimizza

g _i (t + p _i)/p _i

sulla prima macchina vuota (i esegue i lavori fuori tutto non ancora programmate, t è il ora, dove la prima macchina è vuota).

Quindi questa soluzione può essere migliorata utilizzando Meta-Euristica come Simulated Annealing. Una soluzione può essere rappresentata come una tupla di sequenze di lavoro (una sequenza di lavoro per ogni macchina). Un punto cruciale è, a quali "mosse" è permesso cambiare una soluzione. Forse per questo problema si possono già trovare buone soluzioni con le due mosse fondamentali:

• Prendere un lavoro da una macchina e trovare un nuovo posto per inserirlo.
• Scambia due lavori nelle sequenze di lavoro delle macchine.