Multi-manned assembly line balancing problem con tiempos de proceso dependientes (MALBP-DTT)

Abstract

(English) The proposed PhD thesis consists in solving the Multi-manned Assembly Line Balancing Problem (MALBP). This type of assembly lines is common in the manufacture of large products, such as automobiles, in which different workers perform different tasks on the same work unit simultaneously. Most of the literature related to MALBP assumes that workers at the same station do not interfere with each other and that task processing times are deterministic and invariant. Nevertheless, few papers propose a variant in which processing times can be increased depending on workers at the station, which allows more realistic situations to be represented. The aim of the PhD thesis is to design exact and heuristic resolution procedures for the Multi-manned Assembly Line Balancing Problem with Dependent Task Times (MALBP-DTT) variant, which may be of interest to the scientific community and which improve the procedures already published in the literature up to now. Firstly, different procedures are developed with the aim of minimising the number of workers and stations to be assigned on the line, given a cycle time (time available at each station to complete the assigned tasks). This problem is mainly encountered in situations where it is required to design a new assembly line in terms of a known external demand. This PhD thesis proposes resolutions on the basis of a mathematical model, two Relax-and-Fix procedures, a heuristic based on solving a partition problem with constraints (named HEUR_PART) and a set of other variants of the HEUR_PART procedure. The computational experiments indicate that HEUR_PART and the HEUR_PART_SGL variant are the proposals that perform best. Furthermore, this PhD thesis applies Empirically Adjusted Greedy Heuristics (EAGH) and presents a new procedure (named EAGH-CKTL), which is based on using EAGH combined with the cocktail of heuristics concept. EAGH and EAGH-CKTL are used to design new priority rules for solving MALBP-DTT through the HEUR_PART steps. In particular, EAGH-CKTL is applied for building new priority rules that have a good performance as part of a cocktail of heuristics. The computational experiments show the efficiency of using both EAGH and EAGH-CKTL in the process of designing efficient priority rules: one of the priority rules designed with EAGH presents a better performance than any other rule proposed in HEUR_PART; while another rule, designed with EAGH-CKTL, evidences a remarkable improvement in the HEUR_PART results when added in its cocktail of heuristics. Moreover, new heuristics that also solve a partition problem with constraints are developed. Two procedures are designed: MULTI_HEUR_PART, based on solving a combined partition problem; and OPWK_PART, based on generating neighbouring stations by means of task swaps and transfers. OPWK_PART is the procedure which obtains the best results, compared both with the other proposed procedures for solving the same problem and with any other procedure that has been published in the literature for this variant up to now. A second problem to be solved for multi-manned assembly lines is to produce the highest number of workpieces using a fixed number of workstations. In the second part of the thesis this kind of problem is addressed for the first time in the literature: the MALBP-DTT with the objective of minimising the cycle time. For this purpose, a mathematical model is presented. Furthermore, two heuristics based on solving a partition problem with constraints are developed: HEUR_CT_PART and OPCT_PART. In particular, OPCT_PART uses a greedy constructive heuristic procedure, named GRDY_DTT2, and combines the resolution of a partition problem with the generation of neighbouring workstations by task swaps and transfers. The computational experiments indicate that OPCT_PART is the proposal that performs best. Additionally, it is shown that OPCT_PART obtains better results than the ones published in the literature for the MALBP with the same objectives.

(Català) La tesi doctoral proposta consisteix a resoldre el problema d'equilibrat de línies de muntatge amb múltiples operaris en una estació, també conegut com Multi-manned Assembly Line Balancing Problem (MALBP). Aquestes línies de muntatge són habituals en la fabricació de productes de grans dimensions, com els automòbils, en els quals diferents operaris fan diferents tasques sobre la mateixa unitat de treball simultàniament. En la majoria de publicacions sobre el MALBP s'assumeix que els operaris d'una mateixa estació no s'interfereixen i que els temps de procés de les tasques són deterministes i invariables. Hi ha un nombre reduït de treballs que proposen una variant en la qual els temps de procés poden veure's incrementats segons el nombre d'operaris en l'estació, la qual cosa permet representar situacions més realistes. L'objectiu de la tesi doctoral és dissenyar procediments de resolució, exactes i heurístics, per a la variant del MALBP amb temps de procés dependents del nombre d'operaris en l'estació (Multi-manned Assembly Line Balancing Problem with Dependent Task Times; MALBP-DTT), que puguin ser d'interès per a la comunitat científica i que millorin els procediments publicats en la literatura. En primer lloc, es desenvolupen diferents procediments amb l'objectiu de minimitzar el nombre de treballadors i estacions a assignar en la línia, donat un temps de cicle. Es proposen resolucions basades en un model matemàtic, dos procediments que utilitzen la matheurística de Relaxar i Fixar, una heurística basada en la resolució d'un problema de partició amb restriccions ("HEUR_PART"), i un conjunt d'altres variants del procediment HEUR_PART. Els experiments computacionals indiquen que HEUR_PART i la variant HEUR_PART_SGL són les propostes que millor funcionen. A continuació, s'aplica el procediment Empirically Adjusted Greedy Heuristics (EAGH) i es presenta una nova variant ("EAGH-CKTL"), que utilitza EAGH combinada amb el concepte de còctel d'heurístiques. EAGH i EAGH-CKTL s'utilitzen per a dissenyar noves regles de prioritat per a resoldre el MALBP-DTT usant HEUR_PART. En particular, EAGH-CKTL s'aplica per a construir noves regles de prioritat que tinguin un bon rendiment en un còctel d'heurístiques. Els experiments computacionals realitzats mostren l'eficàcia de EAGH i EAGH-CKTL en el disseny de regles de prioritat eficients. Així mateix, es desenvolupen noves heurístiques que també resolen problemes de partició amb restriccions. Es dissenyen dos procediments: MULTI_HEUR_PART, que resol problemes de partició combinats; i OPWK_PART, que genera estacions veïnes mitjançant intercanvis i transferències de tasques. OPWK_PART és el procediment que obté els millors resultats comparat tant amb els altres procediments proposats com amb qualsevol dels procediments publicats en la literatura. Un segon problema de línies de muntatge a resoldre consisteix a produir el major nombre d'unitats de producte utilitzant un nombre fix d'estacions. En la segona part de la tesi doctoral s'estudia, per primera vegada a la literatura, aquesta classe de problema: el MALBP-DTT amb l'objectiu de minimitzar el temps de cicle. Per a això, es presenta un model matemàtic i es desenvolupen dues heurístiques basades a resoldre d'un problema de partició amb restriccions: HEUR_CT_PART i OPCT_PART. En particular, OPCT_PART utilitza un procediment heurístic constructiu greedy, denominat GRDY_DTT2, i combina la resolució d'un problema de partició amb la configuració d'estacions veïnes mitjançant intercanvi i transferència de tasques. Els experiments computacionals indiquen que OPCT_PART és la proposta que millor funciona. A més, es mostra que OPCT_PART obté millors resultats que qualsevol dels procediments publicats en la literatura que resolen el MALBP amb els mateixos objectius.

(Español) La tesis doctoral propuesta consiste en resolver el problema de equilibrado de líneas de montaje con múltiples operarios en una estación, también conocido como Multi-manned Assembly Line Balancing Problem (MALBP). Estas líneas de montaje son habituales en la fabricación de productos de gran tamaño, como automóviles, en los que diferentes operarios realizan distintas tareas sobre la misma unidad de trabajo simultáneamente. En la mayoría de publicaciones sobre el MALBP se asume que los operarios de una misma estación no se interfieren y que los tiempos de proceso de las tareas son deterministas e invariables. Hay un número reducido de trabajos que proponen una variante en la que los tiempos de proceso pueden verse incrementados según el número de operarios en la estación, lo cual permite representar situaciones más realistas. El objetivo de la tesis doctoral es diseñar procedimientos de resolución, exactos y heurísticos, para la variante del MALBP con tiempos de proceso dependientes del número de operarios en la estación (Multi-manned Assembly Line Balancing Problem with Dependent Task Times; MALBP-DTT), que puedan ser de interés para la comunidad científica y que mejoren los procedimientos publicados en la literatura. En primer lugar, se desarrollan diferentes procedimientos con el objetivo de minimizar el número de trabajadores y estaciones a asignar en la línea, dado un tiempo de ciclo. Se proponen resoluciones basadas en un modelo matemático, dos procedimientos que utilizan la matheurística de Relajar y Fijar, una heurística basada en la resolución de un problema de partición con restricciones ("HEUR_PART"), y un conjunto de otras variantes del procedimiento HEUR_PART. Los experimentos computacionales indican que HEUR_PART y la variante HEUR_PART_SGL son las propuestas que mejor funcionan. A continuación, se aplica el procedimiento Empirically Adjusted Greedy Heuristics (EAGH) y se presenta una nueva variante ("EAGH-CKTL"), que utiliza EAGH combinada con el concepto de cóctel de heurísticas. EAGH y EAGH-CKTL se utilizan para diseñar nuevas reglas de prioridad para resolver el MALBP-DTT usando HEUR_PART. En particular, EAGH-CKTL se aplica para construir nuevas reglas de prioridad que tengan un buen rendimiento en un cóctel de heurísticas. Los experimentos computacionales realizados muestran la eficacia de EAGH y EAGH-CKTL en el diseño de reglas de prioridad eficientes. Asimismo, se desarrollan nuevas heurísticas que también resuelven problemas de partición con restricciones. Se diseñan dos procedimientos: MULTI_HEUR_PART, que resuelve problemas de partición combinados; y OPWK_PART, que genera estaciones vecinas mediante intercambio y transferencia de tareas. OPWK_PART es el procedimiento que obtiene los mejores resultados comparado tanto con los otros procedimientos propuestos como con cualquiera de los procedimientos publicados en la literatura. Un segundo problema de líneas de montaje a resolver consiste en producir el mayor número de unidades de producto utilizando un número fijo de estaciones. En la segunda parte de la tesis doctoral se estudia, por primera vez en la literatura, esta clase de problema: el MALBP-DTT con el objetivo de minimizar el tiempo de ciclo. Para ello, se presenta un modelo matemático y se desarrollan dos heurísticas basadas en resolver de un problema de partición con restricciones: HEUR_CT_PART y OPCT_PART. En particular, OPCT_PART utiliza un procedimiento heurístico constructivo greedy, denominado GRDY_DTT2, y combina la resolución de un problema de partición con la configuración de estaciones vecinas mediante intercambio y transferencia de tareas. Los experimentos computacionales indican que OPCT_PART es la propuesta que mejor funciona. Además, se muestra que OPCT_PART obtiene mejores resultados que cualquiera de los procedimientos publicados en la literatura que resuelven el MALBP con los mismos objetivos.