The time buffer approximated buffer allocation problem: a row-column generation approach.

*(English)*Zbl 07157801Summary: One of the main problems in production systems is the buffer sizing. Choosing the right buffer size, at each production stage, that allows to achieve some performance measure (usually throughput or waiting time) is known as Buffer Allocation Problem (BAP), and it has been widely studied in the literature. Due to its complexity, BAP is usually approached using decomposition methods, under very strict system assumptions, or using simulation-optimization techniques. In this paper, the approximated mathematical programming formulation of the BAP simulation-optimization based on the time buffer concept is used. Using this approximation, buffers are modeled as temporal lags (time buffers) and this allows to use Linear Programming (LP) instead of Mixed Integer Linear Programming (MILP) models. Although LP models are easier to solve than MILPs, the huge dimension and the complex solution space topology of the time buffer approximated BAP call for ad hoc solution algorithms. To this purpose, a row-column generation algorithm is proposed, which exploits the theoretical properties of the time buffer approximation to reduce the solution time. The proposed algorithm has been compared with a standard LP solver (ILOG CPLEX) and with a state-of-the-art MILP solver and it proved to be better than the LP solver in most of the cases, and more robust than the MILP solver with respect to computation time. Moreover, the LP model (for flow lines) is able to solve the BAP also for assembly/disassembly lines.

##### MSC:

90B | Operations research and management science |

##### Keywords:

buffer allocation; simulation-optimization; assembly lines; math programming; row and column generation; exact method##### Software:

CPLEX
PDF
BibTeX
XML
Cite

\textit{A. Alfieri} et al., Comput. Oper. Res. 115, Article ID 104835, 14 p. (2020; Zbl 07157801)

Full Text:
DOI

##### References:

[1] | Alfieri, A.; Matta, A., Mathematical programming formulations for approximate simulation of multistage production systems., Eur. J. Oper. Res., 219, 3, 773-783 (2012) · Zbl 1253.90101 |

[2] | Alfieri, A.; Matta, A., Mathematical programming time-based decomposition algorithm for discrete event simulation, Eur J Oper Res, 231, 3, 557-566 (2013) |

[3] | Alfieri, A.; Matta, A.; Pastore, E., A column generation algorithm for the buffer allocation problem approximated by the time buffer concept, Proceedings of the 8th IFAC Conference on Manufacturing Modelling, Management and Control (MIM 2016) (2016) |

[4] | Altiparmak, F.; Dengiz, B.; Bulgak, A. A., Buffer allocation and performance modeling in asynchronous assembly system operations: an artificial neural network metamodeling approach, Appl. Soft Comput., 7, 3, 946-956 (2007) |

[5] | Andradóttir, S., A global search method for discrete stochastic optimization, SIAM J. Optim., 6, 513-530 (1996) · Zbl 0851.60030 |

[6] | Banks, J.; J. S. Carlson, B. N.; Nicol, D., Discrete Event Systems Simulation (2000), Prentice Hall |

[7] | Barnhart, C.; Johnson, E. L.; Nemhauser, G.; Savelsberg, M.; Vance, P., Branch-and-price: column generation for solving huge integer programs, Oper. Res., 46(3), 316-329 (1998) · Zbl 0979.90092 |

[8] | Basu, R., The interstage buffer storage capacity of non-powered assembly lines a simple mathematical approach, Int. J. Prod. Res., 15, 4, 365-382 (1977) |

[9] | Buzzacott, J. A.; Shanthikumar, J. G., Stochastic Models of Manufacturing Systems (1993), Prentice-Hall |

[10] | Castano, F.; Rossia, A.; Sevaux, M.; Velasco, N., A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints, Comput. Oper. Res., 52, 220-230 (2014) · Zbl 1348.90170 |

[11] | Chan, W.; Schruben, L., Optimization models of discrete-event system dynamics, Oper. Res., 56, 5, 1218-1237 (2008) · Zbl 1167.90443 |

[12] | Dallery, Y.; Gershwin, S. B., Manufacturing flow line systems: a review of models and analytical results, Queu. Syst. Theory Appl., 12(1-2), 3-94 (1992) · Zbl 0782.90048 |

[13] | Demir, L.; Tunali, S.; Eliiyi, D. T., The state of the art on buffer allocation problem: a comprehensive survey, J. Intell. Manuf., 25, 3, 371-392 (2014) |

[14] | Dolgui, A.; Eremeev, A.; Kovalyov, M. Y.; Sigaev, V., Complexity of buffer capacity allocation problems for production lines with unreliable machines, J. Math. Modell. Algorithms Oper. Res., 12, 2, 155-165 (2013) · Zbl 1311.90195 |

[15] | Dolgui, A.; Eremeev, A.; Sygaev, V., A problem of buffer allocation in production lines: complexity analysis and algorithms, 3rd International Conference on Metaheuristics and Nature Inspired Computing (2010) |

[16] | Dolgui, A. B.; Eremeev, A. V.; Kovalyov, M. Y.; Sigaev, V. S., Complexity of bi-objective buffer allocation problem in systems with simple structure, International Conference on Optimization Problems and Their Applications, 278-287 (2018), Springer |

[17] | Frangioni, A.; Gendron, B., A stabilized structured dantzig-wolfe decomposition method, Math. Program., 140, 1, 45-76 (2013) · Zbl 1272.90029 |

[18] | Fu, M., Optimization for simulation: theory vs. practice, J. Comput., 14(3), 192-215 (2002) · Zbl 1238.90001 |

[19] | Fu, M.; Glover, F.; April, J., Simulation optimization: a review, new developments, and applications, Proceedings of the 2005 Winter Simulation Conference (2005) |

[20] | Fu, M.; Hu, J., Conditional Monte Carlo: Gradient Estimation and Optimization Applications (1997), Kluwer Academic · Zbl 0874.62093 |

[21] | Gershwin, S., Manufacturing Systems Engineering (1994), Prentice Hall |

[22] | Gershwin, S. B., An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking, Oper. Res., 35, 291-305 (1987) · Zbl 0626.90027 |

[23] | Gershwin, S. B.; Schor, J. E., Efficient algorithms for buffer space allocation, Ann. Oper. Res., 93, 1-4, 117-144 (2000) · Zbl 0953.90018 |

[24] | Harris, J.; Powell, S., An algorithm for optimal buffer placement in reliable serial lines, IIE Trans., 31, 287-302 (1999) |

[25] | Hemachandra, N.; Eedupuganti, S. K., Performance analysis and buffer allocations in some open assembly systems, Comput. Oper. Res., 30, 5, 695-704 (2003) · Zbl 1035.90021 |

[26] | Ho, Y.; Cao, X., Discrete Event Dynamics Systems and Perturbation Analysis (1991), Kluwer Academic |

[27] | Ho, Y.; Cassandras, C.; Chen, C.; Dai, L., Ordinal optimization and simulation, J. Oper. Res. Soc., 51, 490-500 (2000) · Zbl 1055.90579 |

[28] | Hopp, W.; Spearman, M., Factory Physiscs (2011), Waveland Pr Inc |

[29] | Kleijnen, J. P.C., Experimental Design for Sensitivity Analysis, Optimization, and Validation of Simulation Models (1998), John Wiley & Sons |

[30] | Kleijnen, J. P.C., Design and analysis of simulation experiments, International Series in Operations Research & Management science, 111 (2008), Springer · Zbl 1269.62067 |

[31] | Kolb, O.; Göttlich, S., A continuous buffer allocation model using stochastic processes, Eur. J. Oper. Res., 242, 3, 865-874 (2015) · Zbl 1341.90037 |

[32] | Kose, S. Y.; Kilincci, O., Hybrid approach for buffer allocation in open serial production lines, Comput. Oper. Res., 60, 67-78 (2015) · Zbl 1348.90226 |

[33] | Li, J.; Meerkov, S., Production Systems Engineering (2009), Springer · Zbl 1156.90002 |

[34] | Li, L.; Qian, Y.; Du, K.; Yang, Y., Analysis of approximately balanced production lines, Int. J. Prod. Res., 54, 3, 647-664 (2016) |

[35] | Lubbecke, M.; Desrosiers, J., Selected topics in column generation, Oper. Res., 53(6), 1007-1023 (2005) · Zbl 1165.90578 |

[36] | Maher, S. J., Solving the integrated airline recovery problem using column-and-row generation, Transp. Sci., 50, 1, 216-239 (2015) |

[37] | Martin, G., Optimal buffer storage capacity in unpaced lines, Comput. Ind. Eng., 18, 3, 401-405 (1990) |

[38] | Matta, A., Simulation optimization with mathematical programming representation of discrete event systems, Proceedings of the 2008 Winter Simulation Conference (2008) |

[39] | Motlagh, M. M.; Azimi, P.; Amiri, M.; Madraki, G., An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines, Expert Syst. Appl., 138, 112836 (2019) |

[40] | Muter, I.; Birbil, Ş. I.; Bülbül, K., Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows, Math. Program., 1-36 (2013) · Zbl 1282.90098 |

[41] | Myers, R.; Montgomery, D.; Anderson-Cook, C., Response Surface Methodology: Process and Product Optimization Using Designed Experiments (2009), Wiley · Zbl 1269.62066 |

[42] | Nahas, N., Buffer allocation and preventive maintenance optimization in unreliable production lines, J. Intell. Manuf., 28, 1, 85-93 (2017) |

[43] | Papadopoulos, C.; O’Kelly, M.; Vidalis, M.; Spinellis, D., Manufacturing Systems Engineering (2009), Springer-Verlag New York |

[44] | Papadopoulos, C.; O’Kelly, M.; Tsadiras, A., A dss for the buffer allocation of production lines based on a comparative evaluation of a set of search algorithms, Int. J. Prod. Res., 51, 14, 4175-4199 (2013) |

[45] | Papadopoulos, H.; Vidalis, M., Optimal buffer storage allocation in balanced reliable production lines, Int. Trans. Oper. Res., 5(4), 325-339 (1998) |

[46] | Pedrielli, G.; Alfieri, A.; Matta, A., Integrated simulation-optimisation of pull control systems, Int. J. Prod. Res., 53(14), 4317-4336 (2015) |

[47] | Pedrielli, G.; Matta, A.; Alfieri, A.; Zhang, M., Design and control of manufacturing systems: a discrete event optimization methodology, Int. J. Prod. Res., 56, 1-2, 543-564 (2018) |

[48] | Powell, S. G.; Pike, D. F., Buffering unbalanced assembly systems, IIE Trans., 30, 55-65 (1998) |

[49] | Renna, P., Adaptive policy of buffer allocation and preventive maintenance actions in unreliable production lines, J. Ind. Eng. Int., 15, 3, 411-421 (2019) |

[50] | Rubinstein, R. Y.; Shapiro, A., Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method (1993), John Wiley & Sons · Zbl 0805.93002 |

[51] | Sadykov, R.; Vanderbeck, F., Column generation for extended formulations, EURO J. Comput. Optim., 1, 1-2, 81-115 (2013) · Zbl 1305.90312 |

[52] | Schruben, L. W., Mathematical programming models of discrete event system dynamics, Proceedings of the 2000 Winter Simulation Conference (2000) |

[53] | Seo, D.-W.; Lee, H., Stationary waiting times in m-node tandem queues with production blocking, IEEE Trans. Autom. Control, 56, 4, 958-961 (2011) · Zbl 1368.90053 |

[54] | Spall, J. C., Introduction to Stochastic Search and Optimization (2003), Wiley · Zbl 1088.90002 |

[55] | Spinellis, D.; Papadopoulos, C., A simulated annealing approach for buffer allocation in reliable production lines, Ann. Oper. Res., 93, 373-384 (1998) · Zbl 0946.90013 |

[56] | Stolletz, R.; Weiss, S., Buffer allocation using exact linear programming formulations and sampling approaches, IFAC Proc. Volumes, 46, 9, 1435-1440 (2013) |

[57] | Tempelmeier, H., Practical considerations in the optimization of flow production systems, Int. J. Prod. Res., 41, 1, 149-170 (2003) |

[58] | Tolio, T.; Matta, A., A method for performance evaluation of automated flow lines, Ann. CIRP, 47, 1, 373-376 (1998) |

[59] | Venkateshan, P.; Mathur, K., An efficient column-generation-based algorithm for solving a pickup-and-delivery problem, Comput. Oper. Res., 38, 1647-1655 (2011) · Zbl 1215.90015 |

[60] | just-accepted |

[61] | Weiss, S.; Stolletz, R., Buffer allocation in stochastic flow lines via sample-based optimization with initial bounds, OR Spectr., 37, 4, 869-902 (2015) · Zbl 1326.90037 |

[62] | Wolsey, L., Integer Programming (1998), Wiley · Zbl 0930.90072 |

[63] | Yamada, T.; Matsui, M., A management design approach to assembly line systems, Int. J. Prod. Econ., 84, 193-204 (2003) |

[64] | Zabinsky, Z., Stochastic Adaptive Search for Global Optimization (2003), Springer · Zbl 1044.90001 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.