Problemi di scheduling di campioni biologici su macchine parallele

Prima ancora di parlare di veri e propri algoritmi euristici, è interessante fare alcune osservazioni sull’utilizzo di Cplex per ottenere delle soluzioni che, nonostante non siano sempre ottime, vi si avvicinano moltissimo.
Durante i test sulle configurazioni nel capitolo 4 si notato che in tutti i casi analizzati Cplex riusciva a determinare tutte le soluzioni ammissibili del problema in pochissimi secondi, compresa quella ottima. Tuttavia il tempo necessario a Cplex per fornire la soluzione ottima risultava spesso essere molto elevato. Questo a causa del fatto che prima di affermare con certezza (errore dello 0%) quale sia l’ottimo del problema, Cplex deve analizzare tutti possibili nodi generati dall’algoritmo di Branch and Bound sfruttato dal software per risolvere il problema.
L’idea è quindi impostare i parametri di Cplex così da far terminare la ricerca dell’ottimo entro un tempo limite, o quando si raggiunge un certo gap dalla soluzione ottima. Cplex fornirà così la migliore soluzione nota fino al momento dell’interruzione.
In tabella 3 si riporta un esempio in cui si sono presi come dati di input quelli della Configurazione 5 con un numero n=110 di campioni. In un caso si è lasciato al compilatore tutto il tempo necessario per trovare l’ottimo con errore nullo, nell’altro si è impostato un tempo limite di 30 secondi di esecuzione. Dettagli dell’output della simulazione con time limit in appendice (A.5).
Questo metodo di calcolo di una soluzione approssimata risulta quindi essere molto efficiente, tuttavia il pregio di un’euristica è anche quello di essere scritta in un linguaggio di programmazione eseguibile anche in abiti in cui non si dispone di software appositi e complessi come Cplex. Nel seguito quindi andremo ad analizzare alcune euristiche realizzate tramite degli script Matlab.