Bilancio del carico. Perché non utilizzare code di priorità?

Question

Recentemente ho imparato a conoscere i vari algoritmi randomizzati per il bilanciamento del carico. Il modello è sempre che ci sono $ M $ palle e $ n $ bidoni e le palle arrivano uno alla volta. Il compito è quello di ridurre al minimo il carico massimo di ogni bin. Tuttavia c'è qualcosa che non capisco.

Perché non solo a mantenere una coda di priorità dei carichi di bidoni e allocare qualsiasi nuovo pallone per il bidone con il carico di corrente più basso? Questo sembra dare il carico ottimale senza complicazioni.

Answer 1

Lei ha ragione che utilizzando una coda di priorità è una buona idea. Non dà una risposta ottimale però. (Supponendo che ciò che si sta cercando di ottimizzare sia il tempo che le ultime finiture processore di eseguire l'ultimo lavoro). Questo problema scheduling è NP-completo, e il metodo basato coda con priorità dà una risposta che si trova all'interno di un fattore 2 di ottimale. Si veda, ad esempio, http: // www. cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf . Il href="http://en.wikipedia.org/wiki/Job_shop_scheduling" rel="nofollow"> pagina dà anche alcune informazioni.