Abstract:
|
[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas
paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales.
El objetivo del problema es minimizar el tiempo ...[+]
[ES] En este trabajo se pretende resolver el problema de secuenciación de máquinas
paralelas no relacionadas con ajustes entre trabajos y recursos limitados adicionales.
El objetivo del problema es minimizar el tiempo de finalización del último trabajo en ser
procesado (makespan). Este makespan puede ser determinante para cualquier
empresa con una cadena de producción a la hora de cumplir plazos de entrega o
mejorar la productividad. Para abordar este problema se diseñarán e implementarán
heurísticas que estarán formadas por dos fases: una fase constructiva donde se
obtendrá una primera solución del problema, y una fase de reparación donde se
arreglará la solución obtenida en la fase anterior si se supera el número de recursos
permitidos. Además, para conseguir una mayor diversidad de soluciones, se
aleatorizará parte de la fase constructiva, convirtiendo las heurísticas en
metaheurísticas. Más adelante se realizará una extensa fase de experimentos y
posterior análisis, en el que se probarán diferentes versiones de las heurísticas y
metaheurísticas variando diferentes factores. A continuación, se compararán los
resultados obtenidos por los algoritmos propuestos, con los logrados previamente para
el mismo problema por un modelo de programación lineal entera (MILP, por sus siglas
en inglés Mixed Integer Linear Program). La conclusión principal de estos
experimentos es que, con un tiempo de proceso muy inferior, se pueden casi igualar y
en algunos casos mejorar los resultados de este modelo utilizando los algoritmos
heurísticos y metaheurísticos propuestos.
[-]
[EN] This project aims to solve the unrelated parallel machines scheduling problem with
adjustments between jobs and additional limited resources. The goal of this problem is
to minimize the completion time of the last ...[+]
[EN] This project aims to solve the unrelated parallel machines scheduling problem with
adjustments between jobs and additional limited resources. The goal of this problem is
to minimize the completion time of the last job (makespan). This makespan can be
decisive for any business with production chains when it comes to respect deadlines or
improving productivity. To engage this problem, design and implementation of
heuristics and metaheuristics will be done, and they will be split in two phases: a
constructive phase where a first solution will be obtained, and a repair phase where
this solution will be fixed in case of exceeding the resources limit. Furthermore, to
achieve a major diversity of solutions, part of the construction phase will be
randomized, transforming heuristics into metaheuristics. Later, an extensive
experiments phase will be done with a proper analysis, where different versions of the
heuristics and metaheuristics will be tested varying different factors. Next, the results
obtained will be compared with the ones achieved for the same problem by an integer
linear programming model (MILP). The main conclusion of these experiments is that,
with much less processing time, the results obtained with the model are similar or in
some instances even worse, compared to the ones achieved with the proposed
heuristic and metaheuristic algorithms.
[-]
[CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines
paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals.
L’objectiu del problema es minimitzar el temps ...[+]
[CA] En aquest treball es tracta de resoldre el problema de seqüenciació de màquines
paral·leles no relacionades amb ajustos entre treballs i recursos limitats adicionals.
L’objectiu del problema es minimitzar el temps de finalització de l’últim treball a ser
processat (makespan). Este makespan pot ser determinant per a qualsevol empresa
amb una cadena de producció a l’hora de complir terminis de lliurament o millorar la
productivitat. Per a abordar aquest problema es dissenyaran e implementaran
heurístiques que estaran formades per dues fases: una fase constructiva on s’obtindrà
una primera solució del problema, i una fase de reparació on s’arreglarà la solució
obtinguda en la fase anterior si es supera el nombre de recursos permitits. A més, per
a aconseguir una major diversitat de solucions, s’aleatoritzarà part de la fase
construcitva, convertint les heurístiques en metaheurístiques. Més endavant es
realitzarà una extensa fase d’experiments i posterior anàlisi, en el qual es provaran
diferents versions de les heurístiques i metaheurístiques variant diferents factors. A
continuació, es compararan els resultats obtinguts pels algorismes proposats, amb els
reeixits prèviament per al mateix problema obtinguts amb un model de programació
lineal sencera (MILP, per les seues sigles en anglés Mixed Integer Linear Program). La
conclusió principal d’aquests experiments és que, amb un temps de procés molt
inferior, es poden quasi igualar i en alguns casos millorar els resultats d’aquest model
utilitzant els algorismes heurístics i metaheurístics proposats.
[-]
|