AbstractsComputer Science

This doctoral thesis tackles an assembly line balancing problem with restricted access to the workpieces that has been entitled AWALBP: the Accessibility Windows Assembly Line Balancing Problem. The problem is described and a general classification for its main optimization levels is proposed. The thesis focuses on a specific case of the optimization level AWALBP-L2. The AWALBP-L2 consists of two subproblems that need to be solved simultaneously: (i) the computation of a feasible movement scheme and (ii) the assignment of each task to one workstation and one stationary stage of the cycle. In the particular case of AWALBP-L2 addressed in this thesis, for each task a single workstation is compatible. The review of the state of the art reveals that relatively few studies have been published concerning the AWALBP. Regarding the solution of the AWALBP-L2, the only available previous work is a mathematical programming model, but the model is not tested or validated. In order to fill this research gap, the aim of this thesis is three-fold: i) to describe the AWALBP and characterize its main optimization levels, ii) to propose exact methods for the case of AWALBP-L2 considered, and iii) to develop solution procedures for the challenging instances that are out of reach of the former methods. Consequently, in this doctoral thesis the AWALBP is characterized and the AWALBP-L2 case is addressed through four main approaches. First, the problem is formalized and solved via two mixed integer linear programming (MILP) models. Second, an approach combining a matheuristic and a MILP model is proposed. The third approach considers hybridizing metaheuristics with mathematical programming models. Finally, the fourth approach proposes sequential combinations of the aforementioned hybrid metaheuristics and a MILP model. The performance of all approaches is evaluated via an extensive computational experiment based on realistic instances, and an optimal solution could be found for a large number of them. Future research work may include additional assumptions on the problem, such as precedence relationships among tasks or several workstations compatible for each task. The methods proposed in this thesis are open in nature and extend perspectives for combining (meta)heuristics and mathematical programming models, either for improving the solution of the AWALBP-L2 or for tackling other combinatorial optimization problems.; Esta tesis doctoral aborda un problema de equilibrado de líneas con acceso limitado a las piezas que ha sido titulado AWALBP: Accessibility Windows Assembly Line Balancing Problem. Se describe el problema y se propone una clasificación general de sus principales niveles de optimización. La tesis se centra en un caso específico del nivel AWALBP-L2. El AWALBP-L2 consta de dos subproblemas que deben ser resueltos simultáneamente: (i) cálculo de un esquema de movimiento factible y (ii) asignación de cada tarea a una estación y a una de las etapas estacionarias del ciclo. En el caso particular de AWALBP-L2 tratado en esta tesis,…