21 |
Meta-heurística baseada em simulated annealing para programação da produção em máquinas paralelas com diferentes datas de liberação e tempos de setup / Metaheuristic based on simulated annealing for production schedule in parallel machines with different release dates and time setupMesquita, Fernanda Neiva 15 December 2015 (has links)
Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2016-10-20T17:39:38Z
No. of bitstreams: 2
Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-10-21T19:23:42Z (GMT) No. of bitstreams: 2
Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-10-21T19:23:42Z (GMT). No. of bitstreams: 2
Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2015-12-15 / This study deals with problems of parallel machines with independent setup times, different dates
of release and minimizing the makespan. The production environment is common in the auto
industry that there may be jobs through the production line, they are added new machines or equal
equipment to expand productive capacity. Any production process requires effective management
by the Production Planning and Control (PCP). This activity includes the planning of production,
so the allocation of resources for task execution on a time basis. The programming activity is one
of the most complex tasks in the management of production because the need to deal with several
different types of resources and concurrent activities. Furthermore, the number of solutions grows
exponentially in several dimensions, according to the number of tasks, operations or machines,
thereby generating a combinatorial nature of the problem. The environment treated in this work
each task has the same processing time on any machine. Considering only the restriction
independently of the task setup time waiting for processing and the presence of release dates
different from zero very practical characteristics in industries. As were found in the literature work
that deals of this work environment, even less that used the meta-heuristic Simulated Anneling, so
we developed the method to the problem, along with the initial solution their disturbance schemes
and the setting of lower bounds for the makespan. / Este estudo trata de problemas de máquinas paralelas com tempos de setup independentes,
diferentes datas de liberação e minimização do makespan. Este ambiente de produção é comum na
indústria automobilística que pode haver postos de trabalho em meio à linha de produção, em que
são adicionadas novas máquinas ou equipamentos iguais para ampliar a capacidade produtiva.
Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e
Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação
de recursos para execução de tarefas em uma base de tempo. A atividade de programação é uma
das tarefas mais complexas no gerenciamento da produção, pois a necessidade de lidar com
diversos tipos diferentes de recursos e atividades simultâneas. Além disso, o número de soluções
cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações
ou máquinas, gerando assim uma natureza combinatória ao problema. O ambiente tratado neste
trabalho cada tarefa tem o mesmo tempo de processamento em qualquer máquina. Considerando a
restrição de tempos de setup independente apenas da tarefa que espera por processamento e a
presença de datas de liberação diferentes de zero características muito práticas nas indústrias.
Como não foram encontrados na literatura trabalho que tratasse desse ambiente de trabalho, ainda
menos que utilizasse a meta-heurística Simulated Anneling, então foi desenvolvido o método para o
problema, juntamente com a solução inicial os respectivos esquemas de perturbação e a definição
de limitantes inferiores para o makespan.
|
22 |
The Distributed and Assembly Scheduling ProblemHatami, Sara 16 May 2016 (has links)
[EN] Nowadays, manufacturing systems meet different new global challenges and
the existence of a collaborative manufacturing environment is essential to face
with. Distributed manufacturing and assembly systems are two manufacturing
systems which allow industries to deal with some of these challenges. This
thesis studies a production problem in which both distributed manufacturing
and assembly systems are considered. Although distributed manufacturing
systems and assembly systems are well-known problems and have been extensively
studied in the literature, to the best of our knowledge, considering
these two systems together as in this thesis is the first effort in the literature.
Due to the importance of scheduling optimization on production performance,
some different ways to optimize the scheduling of the considered problem are
discussed in this thesis.
The studied scheduling setting consists of two stages: A production and an
assembly stage. Various production centers make the first stage. Each of these
centers consists of several machines which are dedicated to manufacture jobs.
A single assembly machine is considered for the second stage. The produced
jobs are assembled on the assembly machine to form final products through a
defined assembly program.
In this thesis, two different problems regarding two different production
configurations for the production centers of the first stage are considered.
The first configuration is a flowshop that results in what we refer to as the
Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP).
The second problem is referred to as the Distributed Parallel Machine and
Assembly Scheduling Problem (DPMASP), where unrelated parallel machines
configure the production centers. Makespan minimization of the product on the
assembly machine located in the assembly stage is considered as the objective
function for all considered problems.
In this thesis some extensions are considered for the studied problems
so as to bring them as close as possible to the reality of production shops.
In the DAPFSP, sequence dependent setup times are added for machines in
both production and assembly stages. Similarly, in the DPMASP, due to
technological constraints, some defined jobs can be processed only in certain
factories.
Mathematical models are presented as an exact solution for some of the
presented problems and two state-of-art solvers, CPLEX and GUROBI are
used to solve them. Since these solvers are not able to solve large sized
problems, we design and develop heuristic methods to solve the problems. In
addition to heuristics, some metaheuristics are also designed and proposed to
improve the solutions obtained by heuristics. Finally, for each proposed problem,
the performance of the proposed solution methods is compared through
extensive computational and comprehensive ANOVA statistical analysis. / [ES] Los sistemas de producción se enfrentan a retos globales en los que el concepto
de fabricación colaborativa es crucial para poder tener éxito en el entorno
cambiante y complejo en el que nos encontramos. Una característica de los sistemas
productivos que puede ayudar a lograr este objetivo consiste en disponer
de una red de fabricación distribuida en la que los productos se fabriquen en
localizaciones diferentes y se vayan ensamblando para obtener el producto
final. En estos casos, disponer de modelos y herramientas para mejorar el
rendimiento de sistemas de producción distribuidos con ensamblajes es una
manera de asegurar la eficiencia de los mismos.
En esta tesis doctoral se estudian los sistemas de fabricación distribuidos
con operaciones de ensamblaje. Los sistemas distribuidos y los sistemas con
operaciones de ensamblaje han sido estudiados por separado en la literatura.
De hecho, no se han encontrado estudios de sistemas con ambas características
consideradas de forma conjunta.
Dada la complejidad de considerar conjuntamente ambos tipos de sistemas
a la hora de realizar la programación de la producción en los mismos, se ha
abordado su estudio considerando un modelo bietápico en la que en la primera
etapa se consideran las operaciones de producción y en la segunda se plantean
las operaciones de ensamblaje.
Dependiendo de la configuración de la primera etapa se han estudiado dos
variantes. En la primera variante se asume que la etapa de producción está
compuesta por sendos sistemas tipo flowshop en los que se fabrican los componentes
que se ensamblan en la segunda etapa (Distributed Assembly Permutation
Flowshop Scheduling Problem o DAPFSP). En la segunda variante
se considera un sistema de máquinas en paralelo no relacionadas (Distributed
Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambas
variantes se optimiza la fecha de finalización del último trabajo secuenciado
(Cmax) y se contempla la posibilidad que existan tiempos de cambio (setup)
dependientes de la secuencia de trabajos fabricada. También, en el caso
DPMASP se estudia la posibilidad de prohibir o no el uso de determinadas
máquinas de la etapa de producción.
Se han desarrollado modelos matemáticos para resolver algunas de las
variantes anteriores. Estos modelos se han resuelto mediante los programas
CPLEX y GUROBI en aquellos casos que ha sido posible. Para las instancias
en los que el modelo matemático no ofrecía una solución al problema se han
desarrollado heurísticas y metaheurísticas para ello.
Todos los procedimientos anteriores han sido estudiados para determinar
el rendimiento de los diferentes algoritmos planteados. Para ello se ha realizado
un exhaustivo estudio computacional en el que se han aplicado técnicas
ANOVA.
Los resultados obtenidos en la tesis permiten avanzar en la comprensión
del comportamiento de los sistemas productivos distribuidos con ensamblajes,
definiendo algoritmos que permiten obtener buenas soluciones a este tipo de
problemas tan complejos que aparecen tantas veces en la realidad industrial. / [CAT] Els sistemes de producció s'enfronten a reptes globals en què el concepte de
fabricació col.laborativa és crucial per a poder tindre èxit en l'entorn canviant
i complex en què ens trobem. Una característica dels sistemes productius
que pot ajudar a aconseguir este objectiu consistix a disposar d'una xarxa de
fabricació distribuïda en la que els productes es fabriquen en localitzacions
diferents i es vagen acoblant per a obtindre el producte final. En estos casos,
disposar de models i ferramentes per a millorar el rendiment de sistemes de
producció distribuïts amb acoblaments és una manera d'assegurar l'eficiència
dels mateixos.
En esta tesi doctoral s'estudien els sistemes de fabricació distribuïts amb
operacions d'acoblament. Els sistemes distribuïts i els sistemes amb operacions
d'acoblament han sigut estudiats per separat en la literatura però, en allò
que es coneix, no s'han trobat estudis de sistemes amb ambdós característiques
conjuntament. Donada la complexitat de considerar conjuntament ambdós
tipus de sistemes a l'hora de realitzar la programació de la producció en els
mateixos, s'ha abordat el seu estudi considerant un model bietàpic en la que
en la primera etapa es consideren les operacions de producció i en la segona es
plantegen les operacions d'acoblament.
Depenent de la configuració de la primera etapa s'han estudiat dos variants.
En la primera variant s'assumix que l'etapa de producció està composta per
sengles sistemes tipus flowshop en els que es fabriquen els components que
s'acoblen en la segona etapa (Distributed Assembly Permutation Flowshop
Scheduling Problem o DAPFSP). En la segona variant es considera un sistema
de màquines en paral.lel no relacionades (Distributed Parallel Machine and
Assembly Scheduling Problem o DPMASP). En ambdós variants s'optimitza
la data de finalització de l'últim treball seqüenciat (Cmax) i es contempla la
possibilitat que existisquen temps de canvi (setup) dependents de la seqüència
de treballs fabricada. També, en el cas DPMASP s'estudia la possibilitat de
prohibir o no l'ús de determinades màquines de l'etapa de producció.
S'han desenvolupat models matemàtics per a resoldre algunes de les variants
anteriors. Estos models s'han resolt per mitjà dels programes CPLEX
i GUROBI en aquells casos que ha sigut possible. Per a les instàncies en
què el model matemàtic no oferia una solució al problema s'han desenrotllat
heurístiques i metaheurísticas per a això. Tots els procediments anteriors han
sigut estudiats per a determinar el rendiment dels diferents algoritmes plantejats.
Per a això s'ha realitzat un exhaustiu estudi computacional en què s'han
aplicat tècniques ANOVA.
Els resultats obtinguts en la tesi permeten avançar en la comprensió del
comportament dels sistemes productius distribuïts amb acoblaments, definint
algoritmes que permeten obtindre bones solucions a este tipus de problemes
tan complexos que apareixen tantes vegades en la realitat industrial. / Hatami, S. (2016). The Distributed and Assembly Scheduling Problem [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64072 / TESIS
|
Page generated in 0.0418 seconds