Abstract
The buffer allocation problem (BAP) aims to determine the optimal buffer configuration for a production line under the predefined constraints. The BAP is an NP-hard combinatorial optimization problem and the solution space exponentially grows as the problem size increases. Therefore, problem specific heuristic or meta-heuristic search algorithms are widely used to solve the BAP. In this study two population-based search algorithms; i.e. Combat Genetic Algorithm (CGA) and Big Bang-Big Crunch (BB-BC) algorithm, are proposed in solving the BAP to maximize the throughput of the line under the total buffer size constraint for unreliable production lines. Performances of the proposed algorithms are tested on existing benchmark problems taken from the literature. The experimental results showed that the proposed BB–BC algorithm yielded better results than the proposed CGA as well as other algorithms reported in the literature.
Similar content being viewed by others
References
Alatas, B. (2011). Uniform big bang-chaotic big crunch optimization. Communications in Nonlinear Science and Numerical Simulation, 16(9), 3696–3703. https://doi.org/10.1016/j.cnsns.2010.12.025.
Altiparmak, F., Dengiz, B., & Bulgak, A. A. (2002). Optimization of buffer sizes in assembly systems using intelligent techniques. Winter Simulation Conference Proceedings. https://doi.org/10.1109/wsc.2002.1166373.
Amiri, M., & Mohtashami, A. (2012). Buffer allocation in unreliable production lines based on design of experiments, simulation, and genetic algorithm. International Journal of Advanced Manufacturing Technology. https://doi.org/10.1007/s00170-011-3802-8.
Biradar, S., Hote, Y. V., & Saxena, S. (2016). Reduced-order modeling of linear time invariant systems using big bang big crunch optimization and time moment matching method. Applied Mathematical Modelling, 40(15–16), 7225–7244. https://doi.org/10.1016/j.apm.2016.03.006.
Bӓck. T. (1993). Optimal mutation rates in genetic search. In: Fifth international conference on genetic algorithms—ICGA (vol. 5, pp. 2–8). Morgan Kaufmann.
Camp, C. V., & Huq, F. (2013). CO2 and cost optimization of reinforced concrete frames using a big bang–big crunch algorithm. Engineering Structures, 48, 363–372. https://doi.org/10.1016/j.engstruct.2012.09.004.
Chuang, L. Y., Yang, C. H., Li, J. C., & Yang, C. H. (2012). A hybrid BPSO-CGA approach for gene selection and classification of microarray data. Journal of Computational Biology, 19(1), 68–82. https://doi.org/10.1089/cmb.2010.0064.
Costa, A., Alfieri, A., Matta, A., & Fichera, S. (2015). A parallel tabu search for solving the primal buffer allocation problem in serial production systems. Computers & Operations Research, 64, 97–112. https://doi.org/10.1016/j.cor.2015.05.013.
Cvetković, D., & Parmee, I. C. (2002). Preferences and their application in evolutionary multiobjective optimization. IEEE Transactions on Evolutionary Computation, 6(1), 42–57. https://doi.org/10.1109/4235.985691.
Dallery, Y., David, R., & Xie, X. L. (1988). An efficient algorithm for analysis of transfer lines with unreliable machines and finite buffers. IIE Transactions (Institute of Industrial Engineers), 20(3), 281–283. https://doi.org/10.1080/07408178808966181.
Demir, L., Tunal, S., & Eliiyi, D. T. (2012). An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines. Computers & Operations Research. https://doi.org/10.1016/j.cor.2011.08.019.
Demir, L., Tunali, S., & Eliiyi, D. T. (2014). The state of the art on buffer allocation problem: A comprehensive survey. Journal of Intelligent Manufacturing, 25(3), 371–392. https://doi.org/10.1007/s10845-012-0687-9.
Demir, L., Tunali, S., & Løkketangen, A. (2011). A tabu search approach for buffer allocation in production lines with unreliable machines. Engineering Optimization, 43(2), 213–231. https://doi.org/10.1080/0305215X.2010.481022.
Desai, S. R., & Prasad, R. (2013). A novel order diminution of LTI systems using big bang big crunch optimization and routh approximation. Applied Mathematical Modelling, 37(16–17), 8016–8028. https://doi.org/10.1016/j.apm.2013.02.052.
Dolgui, A., Eremeev, A., Kolokolov, A., & Sigaev, V. (2002). A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines. Journal of Mathematical Modelling and Algorithms, 1(2), 89–104. https://doi.org/10.1023/A:1016560109076.
Dolgui, A., Eremeev, A. V., & Sigaev, V. S. (2007). HBBA: Hybrid algorithm for buffer allocation in tandem production lines. Journal of Intelligent Manufacturing, 18(3), 411–420. https://doi.org/10.1007/s10845-007-0030-z.
Eksin, I., & Erol, O. K. (2001). Evolutionary algorithm with modifications in the reproduction phase. IEE Proceedings - Software, 148(2), 75–80.
Erol, O. K., & Eksin, I. (2006). A new optimization method: Big bang-big crunch. Advances in Engineering Software, 37(2), 106–111. https://doi.org/10.1016/j.advengsoft.2005.04.005.
Fernández-Cabán, P. L., & Masters, F. J. (2018). Hybridizing particle swarm and big bang–big crunch optimization methods to explore then exploit the design domain of large planar frame structures. Computers & Structures, 202, 1–14. https://doi.org/10.1016/j.compstruc.2018.02.014.
Gen, M., & Lin, L. (2014). Multiobjective evolutionary algorithm for manufacturing scheduling problems: State-of-the-art survey. Journal of Intelligent Manufacturing, 25(5), 849–866. https://doi.org/10.1007/s10845-013-0804-4.
Genç, H. M., Eksin, I., & Erol, O. K. (2013). Big bang–big crunch optimization algorithm with local directional moves. Turkish Journal of Electrical Engineering and Computer Sciences, 21(5), 1359–1375. https://doi.org/10.3906/elk-1106-46.
Gershwin, S. B. (1987). An efficient decomposition method for the approximate evaluation of production lines with finite storage space and blocking. Operations Research, 35(2), 291–305. https://doi.org/10.1007/BFb0006317.
Gershwin, S. B., & Schor, J. E. (2000). Efficient algorithms for buffer space allocation. Annals of Operations Research, 93(1–4), 117–144. https://doi.org/10.1023/A:1018988226612.
Guner Goren, H., Tunali, S., & Jans, R. (2010). A review of applications of genetic algorithms in lot sizing. Journal of Intelligent Manufacturing, 21(4), 575–590. https://doi.org/10.1007/s10845-008-0205-2.
Hamdi, M., & Zaied, M. (2019). Resource allocation based on hybrid genetic algorithm and particle swarm optimization for D2D multicast communications. Applied Soft Computing Journal, 83, 105605. https://doi.org/10.1016/j.asoc.2019.105605.
Hasançebi, O., & Kazemzadeh Azad, S. (2012). An exponential big bang–big crunch algorithm for discrete design optimization of steel frames. Computers & Structures, 110–111, 167–179. https://doi.org/10.1016/j.compstruc.2012.07.014.
Hillier, F. S., So, K. C., & Boling, R. W. (1993). Toward characterizing the optimal allocation of storage space in production line systems with variable processing times. Management Science, 39, 126–133.
Ho, Y. C., Eyler, M. A., & Chien, T. T. (1979). A gradient technique for general buffer storage design in a production line. International Journal of Production Research, 17(6), 557–580.
Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: The University of Michigan Press.
Kaveh, A., & Talatahari, S. (2009). Size optimization of space trusses using big bang–big crunch algorithm. Computers & Structures, 87(17–18), 1129–1140. https://doi.org/10.1016/j.compstruc.2009.04.011.
Kaveh, A., & Talatahari, S. (2010). Optimal design of Schwedler and ribbed domes via hybrid big bang–big crunch algorithm. Journal of Constructional Steel Research, 66(3), 412–419. https://doi.org/10.1016/j.jcsr.2009.10.013.
Koenigsberg, E. (1959). Production lines and internal storage: A review. Management Science, 5(4), 410–433. https://doi.org/10.1287/mnsc.5.4.410.
Li, L., Qian, Y., Yang, Y. M., & Du, K. (2015). A fast algorithm for buffer allocation problem. International Journal of Production Research. https://doi.org/10.1080/00207543.2015.1092612.
Liberopoulos, G. (2019). Comparison of optimal buffer allocation in flow lines under installation buffer, echelon buffer, and CONWIP policies. Flexible Services and Manufacturing Journal. https://doi.org/10.1007/s10696-019-09341-y.
Lopes, T. C., Sikora, C. G. S., Michels, A. S., & Magatão, L. (2020). An iterative decomposition for asynchronous mixed-model assembly lines: Combining balancing, sequencing, and buffer allocation. International Journal of Production Research, 58(2), 615–630. https://doi.org/10.1080/00207543.2019.1598597.
Motlagh, M. M., Azimi, P., Amiri, M., & Madraki, G. (2019). An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines. Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2019.112836.
Nahas, N., Ait-Kadi, D., & Nourelfath, M. (2006). A new approach for buffer allocation in unreliable production lines. International Journal of Production Economics. https://doi.org/10.1016/j.ijpe.2006.02.011.
Nahas, N., & Nourelfath, M. (2018). Joint optimization of maintenance, buffers and machines in manufacturing lines. Engineering Optimization. https://doi.org/10.1080/0305215X.2017.1299716.
Nahas, N., Nourelfath, M., & Ait-Kadi, D. (2009). Selecting machines and buffers in unreliable series-parallel production lines. International Journal of Production Research. https://doi.org/10.1080/00207540701806883.
Narasimhamu, K. L., Venugopal Reddy, V., & Rao, C. S. P. (2014). Optimal buffer allocation in tandem closed queuing network with single server using PSO. Procedia Materials Science, 5, 2084–2089. https://doi.org/10.1016/j.mspro.2014.07.543.
Niyomubyeyi, O., Sicuaio, T. E., Díaz González, J. I., Pilesjö, P., & Mansourian, A. (2020). A comparative study of four metaheuristic algorithms, AMOSA, MOABC, MSPSO, and NSGA-II for evacuation planning. Algorithms, 13(1), 16. https://doi.org/10.3390/a13010016.
Pedrielli, G., Matta, A., Alfieri, A., & Zhang, M. (2018). Design and control of manufacturing systems: A discrete event optimisation methodology. International Journal of Production Research. https://doi.org/10.1080/00207543.2017.1412532.
Romero-Silva, R., & Shaaban, S. (2019). Influence of unbalanced operation time means and uneven buffer allocation on unreliable merging assembly line efficiency. International Journal of Production Research, 57(6), 1645–1666. https://doi.org/10.1080/00207543.2018.1495344.
Sedighizadeh, M., Ahmadi, S., & Sarvi, M. (2013). An efficient hybrid big bang–big crunch algorithm for multi-objective reconfiguration of balanced and unbalanced distribution systems in fuzzy framework. Electric Power Components and Systems, 41(1), 75–99. https://doi.org/10.1080/15325008.2012.732658.
Smith, J. M. G. (2018). Simultaneous buffer and service rate allocation in open finite queueing networks. IISE Transactions, 50(3), 203–216. https://doi.org/10.1080/24725854.2017.1300359.
Talbi, E. G. (2009). Metaheuristics: From design to implementation. Metaheuristics: From Design to Implementation. https://doi.org/10.1002/9780470496916.
Tang, H., Zhou, J., Xue, S., & Xie, L. (2010). Big bang–big crunch optimization for parameter estimation in structural systems. Mechanical Systems and Signal Processing, 24(8), 2888–2897. https://doi.org/10.1016/j.ymssp.2010.03.012.
Tasan, S. O., & Tunali, S. (2008). A review of the current applications of genetic algorithms in assembly line balancing. Journal of Intelligent Manufacturing, 19(1), 49–69. https://doi.org/10.1007/s10845-007-0045-5.
Thierens, D. (2002). Adaptive mutation rate control schemes in genetic algorithms. In Proceedings of the 2002 congress on evolutionary computation, CEC 2002 (Vol. 1, pp. 980–985). https://doi.org/10.1109/CEC.2002.1007058.
Weiss, S., Matta, A., & Stolletz, R. (2018). Optimization of buffer allocations in flow lines with limited supply. IISE Transactions, 50(3), 191–202. https://doi.org/10.1080/24725854.2017.1328751.
Weiss, S., Schwarz, J. A., & Stolletz, R. (2019). The buffer allocation problem in production lines: Formulations, solution methods, and instances. IISE Transactions. https://doi.org/10.1080/24725854.2018.1442031.
Xi, S., Chen, Q., MacGregor Smith, J., Mao, N., Yu, A., & Zhang, H. (2019). A new method for solving buffer allocation problem in large unbalanced production lines. International Journal of Production Research. https://doi.org/10.1080/00207543.2019.1685709.
Xuemei, L., Huan, S., Rui, Z., Yongqi, J., & Aiping, L. (2017). Collaborative optimization of transfer line balancing and buffer allocation based on polychromatic set. Procedia CIRP, 63, 213–218. https://doi.org/10.1016/j.procir.2017.02.045.
Yelkenci Kose, S., & Kilincci, O. (2018). A multi-objective hybrid evolutionary approach for buffer allocation in open serial production lines. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-018-1435-6.
Zandieh, M., Joreir-Ahmadi, M. N., & Fadaei-Rafsanjani, A. (2017). Buffer allocation problem and preventive maintenance planning in non-homogenous unreliable production lines. International Journal of Advanced Manufacturing Technology. https://doi.org/10.1007/s00170-016-9744-4.
Acknowledgements
This research was done during the PhD study of the first author at the Graduate School of Natural and Applied Sciences, Pamukkale University. The authors would like to thank the anonymous reviewers for their constructive comments that improve the paper significantly.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix: DDX algorithm
Appendix: DDX algorithm
The decomposition method is proposed by Gershwin (1987). This method is based on a decomposition of the line into a set of K − 1 two machine lines L(i), for i = 1, …, K − 1. Line L(i) is composed of an upstream machine Mu(i), and a downstream machine Md(i) and buffer B(i) which has the same capacity as buffer Bi in line L, Ni. Machines Mu(i) and Md(i) are defined by their failure and repair rates βu(i), ru(i), and βd(i), rd(i), respectively. The purpose of the method is to determine these parameters so that the behavior of the material flow in buffer B(i) in line L(i) closely matches that of the flow in buffer Bi of line L (see Fig. 8).
To determine the unknown parameters of each two-machine subline, Gershwin (1987) developed a set of non-linear equations as follows:
Equation 8 calculates the isolated efficiency of the machine i. Equation 9 is related to conservation of flow. Equation 10 calculates the throughput of each subline. In Eq. 10, \( p_{s} \left( i \right) \) is the probability of starvation of \( M_{u} \left( i \right) \) and \( p_{b} \left( i \right) \) is the probability of blockage of \( M_{d} \left( i \right) \).
Flow rate-idle time is given Eq. (11). Equation (12) is obtained by stating that a failure occurring from at least one of the upstream machines (Mi-1, Mi-2,…) caused a starvation of the machine Mi or which is occurred the failure of the Mi machine represents the failure in the upstream machine \( M_{u} \left( i \right) \). In a similar way, Eq. (13) can be calculated by considering the failure of machine \( M_{d} \left( i \right) \).We state the quantities \( I_{u} \left( i \right) \) and \( I_{d} \left( i \right) \) defined by Eq. (14):
The set of equations established by Gershwin (1987), the quantities obtained from Eq. (14) and using the above equations can be expressed as follows:
where \( X = \frac{{p_{s} \left( {i - 1} \right)}}{{I_{u} \left( i \right)Th\left( {i - 1} \right)}} \)
where \( Y = \frac{{p_{b} \left( {i + 1} \right)}}{{I_{d} \left( i \right)Th\left( {i + 1} \right)}} \).
Dallery et al. (1988) developed an algorithm, called DDX algorithm, to solve the nonlinear equations given above. As it is stated by the authors, the computational complexity of the DDX algorithm is O(K2), where K is the number of the machines. The DDX algorithm is given in Algorithm 3.
Rights and permissions
About this article
Cite this article
Koyuncuoğlu, M.U., Demir, L. A comparison of combat genetic and big bang–big crunch algorithms for solving the buffer allocation problem. J Intell Manuf 32, 1529–1546 (2021). https://doi.org/10.1007/s10845-020-01647-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-020-01647-1