A sample-based branch-and-bound algorithm for the server allocation problem in stochastic serial-parallel production lines

The Server Allocation Problem (SAP) consists in determine the minimum number of machines to allocate in a manufacturing system so that a threshold KPI is achieved. This is a typical problem of early design of production lines and its importance resides in the high cost of machineries. Another issue of manufacturing systems is to minimize the average system time, which is the time span from material availability at the first processing operation to completion at the last operation. Reductions in system time generates several benefits, including lower work-in-process, improved quality, and less forecasting errors. This work proposes an optimization procedure to solve the SAP, minimizing the total number of machines such that the mean system time achieved does not exceed a target value. No similar works were found in literature. The optimization procedure consists in a sample-based branch-and-bound algorithm using discrete event simulation to evaluate the mean system time of the S-PPL. This algorithm recursively solves several simplified versions of the original server allocation problem in order to reduce the cardinality of the search space, and, consequently, the computational time. The proposed branch-and-bound is a sample-path exact algorithm, and the computation time increases exponentially as the stage number. Thus, to solve SAP for long lines in a reasonable time, an approximated approach is also proposed. Numerical analysis show that the sample-based branch-and-bound algorithm obtains the same optimal solution of an alternative approach, but in a consistent less time. The approximated algorithm was compared with the exact one and returned the same optimal solution but, once again, in less time. The proposed approaches were applied to extensive experiments where the S-PPLs are characterized by different: number of stages; buffer capacity; target system time; mean and variance of processing time. Numerical studies show that stages with high mean and/or variance of processing time should be equipped with higher number of machines. Furthermore, when stages containing high variable machines are positioned in the middle of the line, the system requires higher number of machines than the cases in which these stages occupy the first and last position of the line. The proposed approximate approach can also be applied to assembly lines with parallel machines. Numerical studies show that the convergent section of an assembly line should be allocated with more machines. The algorithms were also applied to an industrial case. Both algorithms were able to solve the SAP in thirty minutes ca.

Il Server Allocation Problem (SAP) consiste nel determinare il numero minimo di macchine da allocare in un sistema di produzione in modo da ottenere un KPI soglia. Questo è un problema tipico del pre-dimensionamento delle linee di produzione e la sua importanza risiede nell’alto costo dei macchinari. Un altro problema dei sistemi manufatturieri è quello di minimizzare il lead time, cioè l’intervallo di tempo tra la prima e l’ultima lavorazione all’interno di un processo produttivo. La riduzione del lead time produce diversi vantaggi, tra cui la riduzione del work-in-process e minori problemi di qualità. Questo lavoro propone una procedura di ottimizzazione per risolvere il SAP, minimizzando il numero totale di macchine in modo che il lead time medio non superi un valore target. In letteratura non è stato trovato nessun approccio simile a tale problema. La procedura di ottimizzazione consiste in un algoritmo branch-and-bound che utilizza la simulazione ad eventi discreti per valutare il lead time della linea. Questo algoritmo risolve ricorsivamente diverse versioni semplificate del problema originale al fine di ridurre la cardinalità dello spazio di ricerca e, di conseguenza, il tempo computazionale. L’algoritmo branch-and-bound è esatto secondo i numeri casuali generati e il tempo di calcolo aumenta esponenzialmente con numero di stadi della linea. Pertanto, per risolvere il SAP per linee con molti stadi in tempi ragionevoli, viene proposto anche un algoritmo approssimato. L’analisi numerica dimostra che l’algoritmo branch-and-bound ha ottenuto la stessa soluzione ottimale di un approccio alternativo, ma in un tempo inferiore. L’algoritmo approssimato è stato confrontato con quello esatto e ha restituito la stessa soluzione ottimale ma, ancora una volta, in un tempo inferiore. Entrambi gli algoritmi proposti sono stati utilizzati per risolvere il SAP in linee seriali parallele caratterizzate da diverso: numero di stadi; dimensione dei buffer; target lead time; media e varianza del tempo di processo dei macchinari. Gli studi numerici dimostrano che il numero ottimale di macchine è maggiore nei casi in cui gli stadi contengono macchine con alta media e/o varianza dei tempi di lavorazione. Inoltre, nei casi di macchine con alta variabilità, se lo stadio che le contiene è posizionato al centro della linea, il numero ottimale di macchine richiesto è più elevato rispetto alle posizioni laterali. L’approccio approssimativo proposto può essere applicato anche alle linee di assemblaggio con machine in parallelo. Lo studio numerico ha dimostrato che la sezione convergente di una catena di assemblaggio necessita più macchine. Entrambi gli algoritmi sono stati applicati anche ad un caso industriale e sono stati in grado di risolvere il SAP in trenta minuti circa.