Bilanciamento di una linea di assemblaggio Two-sided utilizzando un algoritmo genetico

6 
 
 
 
Introduzione 
Lo studio presentato si focalizza sull’analizzare un problema già noto nel campo dell’industria: 
il bilanciamento di una linea di assemblaggio. Si definisce assemblaggio il processo tramite il 
quale vari componenti vengono uniti fra loro in modo da formare un prodotto finito. Questo 
processo è caratterizzato dai materiali utilizzati e dal lavoro necessario a combinarli fra loro. Il 
lavoro è composto da tutte le operazioni di unione dei vari componenti, quali montaggio, 
avvitamento, saldatura, ecc. I materiali sono indispensabili e fanno sì che il lavoro possa 
svolgersi senza interruzioni. Essi possono venire movimentati verso il prodotto per essere 
assemblati, oppure il prodotto stesso può muoversi (tramite sistema di trasporto) verso i 
materiali. Nel primo caso si ha l’assemblaggio a postazione fissa, tipico per esempio dei cantieri, 
mentre nel secondo caso si ha la creazione delle cosiddette linee di assemblaggio, i cui materiali 
sono disposti nelle stazioni di assemblaggio. Entrambe le tipologie elencate sono diffuse, ma 
nell’elaborato ci si focalizza solamente sulla seconda configurazione.  
Il concetto di moderna linea di assemblaggio fu sviluppata e brevettata da Ransom Olds 
[1]
. La 
vecchia Dash fu la prima automobile di produzione di massa ad essere costruita in una linea di 
assemblaggio da Olds Motor Vehicle Company nel 1901. Questo raggiungimento è di solito 
oscurato dal fatto che Henry Ford migliorò la linea di assemblaggio dell’Olds installando un 
nastro trasportatore. Grazie a questo miglioramento, si dice che, nel 1913, la Ford Motor 
Company potesse produrre le sue Ford T in novantatré minuti. Da allora, le linee di 
assemblaggio si sono evolute e sono diventate più flessibili con l’aggiunta di molte 
caratteristiche, vincoli e/o differenti layout. Le moderne linee di assemblaggio sono una 
tipologia di sistema produttivo ampiamente diffuso e si addicono maggiormente a prodotti di 
facile manovrabilità, dove i volumi richiesti sono sufficientemente elevati. 
Ogni sistema di assemblaggio richiede un elevato investimento per la sua progettazione e sua 
successiva realizzazione. Occorre valutare già nelle fasi iniziali quale tipologia di linea sia la 
più adatta a creare il prodotto da vendere. È inoltre necessario domandarsi se essa è in grado di 
soddisfare tutte le esigenze future, nel caso in cui occorre progettarla dal principio, oppure 
decidere eventuali modifiche, se la linea è già presente e si è obbligati a dover modificare il
7 
 
 
 
layout corrente. Quando si implementa o riconfigura una linea di assemblaggio, un problema 
decisionale nasce: esso prende il nome di bilanciamento della linea di assemblaggio o Assembly 
Line balancing problem (ALBP). La configurazione di una linea di assemblaggio include la 
determinazione della capacità del sistema (tempo ciclo, numero di stazioni, attrezzature e vari 
altri strumenti necessari alla lavorazione) nonché la definizione del lavoro tramite 
l’assegnamento dei tasks e la definizione della sequenza delle operazioni da effettuare. Chi 
risolve tale problema si dà l’obiettivo di distribuire efficacemente il carico di lavoro totale 
necessario all’assemblaggio di un prodotto tra le diverse stazioni di lavoro lungo la linea di 
assemblaggio. 
Il problema del bilanciamento di una linea di assemblaggio e la sua risoluzione tramite una 
tecnica metaeuristica detta algoritmo genetico sono gli argomenti fondamentali di questo 
elaborato.  
Nel primo capitolo si effettua una breve descrizione del problema di bilanciamento di una linea 
di assemblaggio (Assembly Line Balancing Problem, o più brevemente, ALBP) e una 
classificazione di queste problematiche viene descritta. Siccome la letteratura riguardante i 
problemi di bilanciamento di una linea di assemblaggio risulta per la quasi totalità in lingua 
inglese, si è deciso di utilizzare tale notazione per esprimere la terminologia delle problematiche 
analizzate, spiegando in ogni caso a cosa essa si riferisce.  
Nel secondo capitolo si definisce il problema specifico della linea di assemblaggio a due 
postazioni (detta Two-Sided Assembly Line) e se ne mostra un modello matematico.  
Nel terzo capitolo viene presentato un richiamo alla ricerca operativa e alla complessità 
computazionale in quanto risultano elementi chiave per capire adeguatamente quanto svolto in 
seguito. Successivamente viene enunciata la metodologia più usata dagli autori per risolvere il 
problema esposto al capitolo due e si affrontano le tecniche di risoluzione che stanno avendo un 
maggiore utilizzo ai giorni nostri.  
Nel quarto capitolo viene esposto lo schema generale di un algoritmo genetico, il suo 
funzionamento e i campi di applicabilità. Esso permette di trovare un’ottima (o buona) soluzione 
al problema studiato.
8 
 
 
 
Nel quinto capitolo, infine, è descritto il funzionamento dell’algoritmo creato e si presentano le 
soluzioni ottenute nei diversi problemi ricavati dalla letteratura.  
L’elaborato termina con un paragrafo conclusivo e con la relativa bibliografia.
9 
 
 
 
1. Assembly Line Balancing Problem (ALBP) 
Nel presente capitolo si fornisce una breve descrizione di un problema ALBP, fornendo le 
principali definizioni chiave necessarie a comprenderne al meglio il problema e si provvede ad 
effettuare una classificazione delle tipologie di linee di assemblaggio più studiate dagli autori. 
Una linea di assemblaggio è formata da un insieme di stazioni di lavoro (indicate con la lettera 
k che va da 1 a m) dislocate secondo una precisa forma che sono disposte in prossimità di un 
nastro trasportatore o di una attrezzatura meccanica di gestione dei materiali. Ogni pezzo viene 
lavorato in sequenza per un determinato periodo di tempo su ogni stazione della linea. 
L’intervallo di tempo disponibile per ogni ciclo di lavoro su una stazione è detto tempo ciclo 
(ed è indicato con la lettera c). Esso solitamente è pari al reciproco del tasso di produzione 
(produttività) della linea e viene fissato in base ai volumi di domanda previsti che si vuole 
soddisfare in un dato orizzonte temporale. Il tempo ciclo è maggiore del massimo tempo di 
processamento delle attività ed è minore della somma di tutti i tempi di processamento delle 
attività stesse. Superato tale tempo ciclo, il pezzo viene portato alla stazione successiva per 
essere lavorato ulteriormente e così via per tutte le stazioni componenti la linea. Alla fine delle 
lavorazioni si otterrà il semilavorato o prodotto finito che verrà lavorato in altri processi 
produttivi o venduto sul mercato. 
La produzione di un prodotto in una linea di assemblaggio richiede la suddivisione del lavoro 
totale necessario in un insieme di operazioni elementari chiamate task (indicati con la lettera i 
che va da 1 a n). Un’operazione è un task, un task è detto anche attività: per questo motivo, in 
questo studio il nome task, attività e operazione saranno considerati come sinonimi.  
Sia n l’insieme dei tasks, e sia i un task compreso tra 1 e n. Svolgere un task i-esimo richiede 
un tempo detto task time ti e richiede certe attrezzature, macchine ed un certo tipo di 
preparazione da parte dei lavoratori che andranno ad eseguire l’operazione. È di fondamentale 
importanza collegare le attività tra loro e attribuire vincoli di precedenza tra i diversi tasks per 
stabilire l’ordine logico di lavorazione di ogni attività. Questi vincoli sono poi schematizzati in 
un grafo delle precedenze, il quale mostra brevemente come il lavoro è organizzato (si veda in 
proposito la figura 1). Ogni nodo rappresenta un’attività, mentre le frecce, o archi, indicano i
10 
 
 
 
vincoli di precedenza. L’attività è rappresentata dal valore numerico interno al nodo mentre il 
task time è rappresentato dal valore numerico appena esterno al nodo (ne rappresenta le unità di 
tempo necessario a svolgere l’attività stessa, che di solito vengono stabilite in minuti o secondi). 
A volte l’attività può essere anche espressa in lettere. 
Figura 1: Diagramma delle precedenze 
    5            5      4   
    
  5 
     3  5             6            5            1 
 
  3     3  3     
 
 
 
Nell’esempio in figura 1 abbiamo 11 tasks (n=11). Il task 1 e 2 hanno tempi di processamento 
pari a 5 e 3 unità di tempo rispettivamente. Questi due tasks non hanno predecessori immediati. 
Ciò vuol dire che verranno eseguiti per primi. Infatti, un task non può essere eseguito finché 
tutte le sue attività precedenti, sia dirette che indirette, siano completate. Per esempio, il task 7 
non può essere eseguito finché i suoi predecessori diretti (task 3 e task 4) e indiretti precedenti 
(task 1 e task 2) sono stati eseguiti. Allo stesso tempo, finire il processamento del task 7 è una 
condizione necessaria per il suo diretto successore (task 9) e indiretti successori (task 10 e 11) 
per iniziare. 
Il problema di bilanciamento di una linea di assemblaggio (ALBP) consiste nel trovare un 
assegnamento fattibile di tasks alle stazioni di lavoro che rispetti: 
• Le precedenze tra i tasks riportate nel diagramma delle precedenze relativo; 
• Il tempo della stazione t(Sk), inteso come il tempo necessario per eseguire tutti i tasks (i) 
assegnati alla stazione stessa k. Esso non può essere maggiore del tempo ciclo. La 
11 10 9 
2 
5 
1 
4 
3 
7 
6 8
11 
 
 
 
differenza tra il tempo di ciclo e il tempo della stazione è detto Idle Time, o tempo di 
inattività (I k = c – t(Sk)). In simboli il tempo della stazione è espresso dalla 1.1. 
 
t(Sk) = 
∑ �� �� �� �� �� �� (1.1) 
 
Il bilanciamento di una linea di assemblaggio è una decisione di medio e lungo termine che, di 
solito, richiede elevati capitali di investimento e ha un grande impatto sul rateo di produzione e 
sui costi manifatturieri. Per questa ragione, obiettivi di costo e profitto dovrebbero essere 
considerati quando si cerca una soluzione per ALBP. Ad esempio, come vedremo in seguito, un 
buon assegnamento prevede di bilanciare il più omogeneamente possibile il carico di lavoro di 
una linea, inteso come le operazioni che devono essere svolte in una stazione al fine di 
massimizzarne l’efficienza. Un altro obiettivo di bilanciamento è quello di minimizzare il 
numero di stazioni utilizzate dato in input il tempo ciclo, oppure ci si può prefiggere di ridurre 
il tempo ciclo di una linea di assemblaggio dando come input il numero di stazioni utilizzate. 
Non esiste una soluzione univoca, è importante scegliere l’obiettivo secondo le proprie esigenze 
e necessità.  
Vediamo ora una classificazione dei problemi ALBP.  
1.1. Classificazione ALBP 
La letteratura degli ALBP è studiata da ormai più di cinquant’anni, quando Salveson nel 1955 
ne diede una prima formulazione matematica. Col passare degli anni molteplici studi sono stati 
sviluppati e considerati per trovare una buona applicabilità anche nel mondo reale.  
Inizialmente si è cercato di comprendere quali problemi di bilanciamento di una linea di 
assemblaggio esistono e sono stati già affrontati. Si è utilizzato il database Scopus per effettuare 
una prima ricerca. Esso rappresenta una banca dati in cui sono disponibili un’enorme quantità 
di pubblicazioni effettuate da professori, dottorandi e ricercatori. Si sono ricavati gli articoli più 
interessanti e citati da altri autori sulla problematica in questione e si è provveduto a farne una 
classificazione dettagliata in modo da comprendere al meglio le tipologie di problemi esistenti. 
Dopo una prima analisi, si è riscontrato che di classificazioni in letteratura ce ne sono diverse,
12 
 
 
 
 
Simple Assembly Line balancing 
General Assembly Line balancing 
 
Paced Assembly Line  
Un-paced Assembly Line 
 
Deterministico 
Stocastico 
 
Singolo obiettivo 
Multi obiettivo 
 
Single Assembly Line  
Mixed Assembly Line  
Multi Assembly Line  
 
Serial 
U-shaped 
Parallel  
Two-Sided 
 
a seconda degli autori e dall’anno di pubblicazione degli articoli. Viene presentata la più 
esaustiva, che è presente nell’articolo “A survey on Assembly Lines and its types – Saif ” 
[2]
, 
riportata in figura 2. 
Come si può notare, le linee di assemblaggio sono suddivise in base alle caratteristiche 
principali, alle caratteristiche del flusso di lavoro, alle caratteristiche del prodotto, alle 
caratteristiche dei tasks, agli obiettivi che si vuole raggiungere e alle caratteristiche di layout.  
Figura 2: Classificazione delle linee di assemblaggio 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Linea di Assemblaggio 
Caratteristiche principali 
 
Caratteristiche flusso di lavoro 
 
Caratteristiche task time 
 
Obiettivi 
 
Caratteristiche layout 
 
Caratteristiche prodotto
13 
 
 
 
1.1.1. Caratteristiche principali 
Tra le tipologie ALBP troviamo più frequentemente il Single Assembly Line Balancing Problem 
(SALBP) e il General Assembly Line Balancing Problem (GALBP). Il primo è descritto dagli 
autori Scholl and Becker 
[3]
 tramite le seguenti caratteristiche: 
• Produzione di massa di un solo prodotto omogeneo; 
• Il processo di produzione è noto e dato (non esistono processi alternativi); 
• Paced line con tempo ciclo fisso c secondo una quantità di output desiderata; 
• Tempo deterministico del task time; 
• Serial Layout con m stazioni senza considerare linee di alimentazione o elementi 
paralleli; 
• Nessun altro vincolo di assegnamento oltre al vincolo di precedenza; 
• Tutte le stazioni sono equipaggiate ugualmente con rispetto delle macchine e lavoratori; 
• Un task non può essere assegnato a due o più stazioni. 
Il modello SALBP prevede la produzione di un singolo prodotto, con processo produttivo già 
noto e definito in cui ogni stazione ha un tempo limitato di lavorazione, il tempo ciclo c. Esso 
deve essere rispettato per garantire il bilanciamento della linea, e per evitare di non completare 
le operazioni necessarie. Il vincolo del tempo ciclo è una caratteristica chiave delle linee 
cosiddette paced, in cui ogni stazione muove i prodotti lavorati alla prossima stazione dopo la 
loro effettiva lavorazione. Di solito in queste linee di assemblaggio, un nastro trasportatore si 
muove periodicamente o continuamente tra le stazioni per trasferire le parti concluse da una 
all’altra.  
Riguardo alle caratteristiche dei tempi di processamento (task times) ogni attività deve essere 
compiuta con tempo fisso, deterministico, uguale ogni volta e deve essere minore della durata 
del tempo ciclo. Risulta chiaro che nella realtà, specialmente nel caso di linee di assemblaggio 
manuali, in cui è l’uomo a dover compiere prevalentemente l’operazione di assemblaggio, è 
particolarmente difficile fare rispettare questa condizione. Esistono infatti molte variabili che 
possono modificare la durata dell’operazione quali tra cui la motivazione, l’umore, la ripetitività
14 
 
 
 
dell’operazione, fattori che si devono tenere conto nel definire la durata del task time delle varie 
operazioni. 
La tipologia di layout SALBP è di tipo serial, cioè le stazioni sono ordinate con un andamento 
rettilineo lungo il nastro trasportatore. Il vincolo di precedenza tra le attività è l’unico 
considerato, e nessun altro vincolo di assegnamento è preso in considerazione.  
La linea è suddivisa equamente in risorse macchina e lavoratori, in modo da evitare carichi di 
lavoro squilibrati che ridurrebbero l’efficienza della linea stessa. Infine, ogni task deve essere 
assegnato solamente ad una stazione di lavoro in quanto non può duplicarsi ed essere presente 
in più di una. 
Nella realtà molti autori non considerano tutte le precedenti caratteristiche per definire il 
problema del SALB, semplicemente perché nella pratica è difficile trovarle tutte evidenti. 
Avremo a che fare con una generalizzazione del problema SALB. Una distinzione che però è 
accettata e condivisa dalla maggior parte di essi è una suddivisione dei SALBP (mostrata in 
figura 3) in 4 diversi tipi: 
1) SALB-1: presuppone che il tempo di tutte le stazioni per le lavorazioni sia uguale. Ha 
l’obiettivo di minimizzare il numero di stazioni da utilizzare nella linea con valore 
noto pari al tempo ciclo, che è equivalente a minimizzare il tempo di inattività (Idle 
time) delle stazioni. È ragionevole affermare che maggior stazioni di lavoro si usano, 
maggor numero di lavoratori, strumenti, spazio, ecc. è richiesto. Quindi, ciò si conduce 
a un criterio indiretto per minimizzare i costi. Si tende a considerarlo quando è 
necessario sviluppare una nuova linea di assemblaggio; 
2) SALB-2: ha l’obiettivo di minimizzare il tempo ciclo conoscendo il numero di stazioni 
(che è fisso) nella linea di assemblaggio. Essendo il rateo di produzione l’inverso del 
tempo ciclo, questo criterio consiste nel massimizzare il rateo di produzione. 
Condizioni necessarie sono che ogni task i risulti assegnato a solo una singola stazione 
e che le stazioni rispettino i vincoli di precedenza dei tasks. 
3) SALB-E: si focalizza sul massimizzare l’efficienza della linea E, valore ottenibile dal 
totale del tempo delle attività di tutti i task (Tsum) rapportato al prodotto del numero di 
stazioni e il tempo ciclo. Questo indicatore è specialmente usato quando sia tempo