Aplicació d’un algorisme genètic per la resolució del problema de seqüenciació d’una màquina amb temps de preparació dependents de família i seqüència

Aquest projecte es centra en la resolució d’un problema de seqüenciació mitjançant un procediment metaheurístic. El problema plantejat i que es resol en aquest projecte és el “Problema de seqüenciació d’una màquina amb temps de preparació dependents de família i seqüència”. L’índex d’eficiència que s’utilitzarà per mesurar la qualitat de la seqüència dels productes o de les peces és el de minimitzar la suma dels temps de retard ponderat de producció d’aquests. Per tant, l’objectiu del problema és planificar la seqüència òptima de productes o peces que han de ser processades en una única màquina donant preferència a una sèrie de productes segons la seva importància i les dates contractuals. El procediment metaheurístic que s’ha utilitzar per resoldre el problema objecte del projecte és un algorisme genètic, que és un mètode basat en l’evolució de les espècies animals i vegetals. En els algorismes genètics es parteix d’una població de possibles solucions on cada solució està formada per una seqüència de peces amb el seu valor d’aptitud o fitness, i partir d’aquests solucions inicials de la població se’n van generant de noves que prenen les característiques de les millors solucions anteriors. En el present projecte s’han analitzat un total de 48 combinacions de paràmetres i operadors genètics. S’ha estudiat l’eficiència de les diferents combinacions de l’algorisme mitjançant la comparació dels resultats obtinguts utilitzant els paràmetres i operadors genètics combinats, a partir de l’execució d’una mostra de instàncies. Cada instància conté un joc de dades del problema. Finalment s’han seleccionat les tres millors configuracions de paràmetres des de tres punts de vista diferents. La primera configuració estarà formada pels paràmetres que individualment hagin obtingut millors resultats alhora de calcular la mitjana de la suma dels temps de retard ponderat, la segona configuració utilitzarà els paràmetres que individualment han obtingut millor percentatge de millors solucions i la tercera configuració serà la combinació de paràmetres que ha obtingut una millor mitjana de retards ponderats a la mostra d’instàncies de manera combinada. Aquestes tres configuracions de paràmetres de l’algorisme genètic s’han testejat en una experiència computacional amb 1920 instàncies de referència generades aleatòriament. Amb els resultats obtinguts s’ha estudiat el comportament evolutiu de l’algorisme creat, i s’ha determinat la millor configuració de paràmetres d’aquest. La configuració de paràmetres de l’algorisme genètic que ha donat millors resultats és el que utilitza un encreuament Order Crossover, una població inicial de 50 solucions i té una probabilitat de mutació del 10%, i el paràmetre que té més influència en el resultat 0 i en l’evolució de les solucions ha estat la població inicial. En l’algorisme genètic estudiat, les configuracions de paràmetres amb menor població tot i començar amb “pitjors” solucions inicials acaben generant millors solucions al llarg de les 500 regeneracions proposades. Aquest fet és degut a que permeten una exploració més intensa del domini de solucions amb els temps reduïts de càlcul