A bidirectional heuristic for stochastic assembly line balancing

This thesis work is devoted to the development of a new bidirectional heuristic able to solve the single-model, stochastic GALBP-II, that consists in assigning the tasks to a fixed number of workstations of a paced line with the aim of minimizing its cycle time. The GALBP-II should be solved when the number of workstations in the line is fixed and cannot be changed, either because of limitations of the available working space or when an existing line should be rebalanced. According to different authors, the rebalancing problem is more frequent than the design and the balancing of new assembly lines. The presented algorithm represents an improvement of the methodology proposed by Liu et al. (2005); the introduction of a new trade and transfer procedure and of new stopping criteria, together with the proper calibration of the algorithm’s parameters, allowed to obtain a more efficient procedure, as demonstrated by the results obtained from experimentations on 80 different problem instances (percentage improvements up to 12.84%). The use of the Welch-Sattertwhaite approximation has allowed to extend the applicability of the proposed algorithm to cases in which the distribution of taks times is positively skewed and thus can be modelled using a gamma distribution; this is often the case in paced assembly systems (especially if skilled operators are involved). The accuracy of the Welch-Sattertwhaite approximation has been validated by simulation results. To the best of author’s knowledge, no other heuristics have been developed so far to solve the GALBP-II under the assumption of non-normally distributed task times. The performances of the proposed algorithm are compared with the ones of a genetic algorithm specifically developed to solve this kind of problem and with the ones of the commercial software ARENA. In both cases, the proposed algorithm turns out to be better in terms of final solution. Finally, the proposed bidirectional algorithm has been applied to a real case in the context of a project implemented at the premises of VHIT S.p.A, a firm belonging to the Bosch group.

Questa tesi è dedicata allo sviluppo di un nuovo algoritmo euristico bidirezionale in grado di risolvere il single-model, stocastich, GALBP-II, che consiste nell'assegnare i task a un numero fisso di stazioni di una linea paced con l’obiettivo di minimizzarne il tempo di ciclo. Il GALBP-II deve essere risolto quando il numero di stazioni nella linea è fisso e non può essere modificato, o a causa di limitazioni dello spazio disponibile o quando si deve ribilanciare una linea esistente. Secondo diversi autori, il ribilanciamento di linee esistenti è più frequente rispetto alla progettazione e al bilanciamento di nuove linee di assemblaggio. L’algoritmo presentato rappresenta un miglioramento della metodologia proposta da Liu et al. (2005); l’introduzione di una nuova procedura di trade and transfer e di nuove condizioni di arresto, unitamente alla corretta calibrazione dei parametri dell’algoritmo, ha permesso di ottenere una procedura più efficiente, come dimostrato dai risultati ottenuti dalle sperimentazioni su 80 diverse istanze (percentuali di miglioramento fino a 12,84%). L’uso dell’approssimazione di Welch-Sattertwhaite ha permesso di estendere l’applicabilità dell’algoritmo proposto a casi in cui la distribuzione dei task times è positively skewed e quindi può essere modellata utilizzando una distribuzione gamma; questo può accadere spesso nel caso di linee paced (specialmente se sono coinvolti operatori esperti). L’accuratezza dell’approssimazione di Welch-Sattertwhaite è stata validata tramite simulazione. Secondo la conoscenza dell’autore, finora non sono stati sviluppati altri euristici in grado di risolvere il GALBP-II sotto l’ipotesi di task times non distribuiti normalmente. Le performance dell’algoritmo proposto vengono confrontate con quelle di un algoritmo genetico specificamente sviluppato per questo tipo di problema e con quelle del software di simulazione ARENA. In entrambi i casi, l’algoritmo proposto risulta migliore in termini di soluzione finale. Infine, l’algoritmo proposto è stato applicato a un caso reale nel contesto di un progetto implementato presso la sede di VHIT S.p.A, un’azienda appartenente al gruppo Bosch.