×

Trim loss optimization by an improved differential evolution. (English) Zbl 1299.90443

Summary: The “trim loss problem” (TLP) is one of the most challenging problems in context of optimization research. It aims at determining the optimal cutting pattern of a number of items of various lengths from a stock of standard size material to meet the customers’ demands that the wastage due to trim loss is minimized. The resulting mathematical model is highly nonconvex in nature accompanied with several constraints with added restrictions of binary variables. This prevents the application of conventional optimization methods. In this paper we use synergetic differential evolution (SDE) for the solution of this type of problems. Four hypothetical but relevant cases of trim loss problem arising in paper industry are taken for the experiment. The experimental results compared with those of the other techniques show the competence of the SDE to solve the problem.

MSC:

90C90 Applications of mathematical programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. A. Rodríguez and A. Vecchietti, “Enterprise optimization for solving an assignment and trim-loss non-convex problem,” Computers and Chemical Engineering, vol. 32, no. 11, pp. 2812-2822, 2008. · doi:10.1016/j.compchemeng.2007.09.004
[2] H. Dyckhoff, “A typology of cutting and packing problems,” European Journal of Operational Research, vol. 44, no. 2, pp. 145-159, 1990. · Zbl 0684.90076 · doi:10.1016/0377-2217(90)90350-K
[3] G. Wäscher, H. Haußner, and H. Schumann, “An improved typology of cutting and packing problems,” European Journal of Operational Research, vol. 183, no. 3, pp. 1109-1130, 2007. · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047
[4] I. Harjunkoski, T. Westerlund, J. Isaksson, and H. Skrifvars, “Different formulations for solving trim loss problems in a paper-converting mill with ILP,” Computers and Chemical Engineering, vol. 20, no. 1, pp. S121-S126, 1996.
[5] I. Harjunkoski, T. Westerlund, and R. Pörn, “Numerical and environmental considerations on a complex industrial mixed integer non-linear programming (MINLP) problem,” Computers and Chemical Engineering, vol. 23, no. 10, pp. 1545-1561, 1999. · doi:10.1016/S0098-1354(99)00310-5
[6] P. Trkman and M. Gradisar, “One-dimensional cutting stock optimization in consecutive time periods,” European Journal of Operational Research, vol. 179, no. 2, pp. 291-301, 2007. · Zbl 1180.90322 · doi:10.1016/j.ejor.2006.03.027
[7] I. Harjunkoski, T. Westerlund, R. Pörn, and H. Skrifvars, “Different transformations for solving non-convex trim-loss problems by MINLP,” European Journal of Operational Research, vol. 105, no. 3, pp. 594-603, 1998. · Zbl 0955.90095 · doi:10.1016/S0377-2217(97)00066-0
[8] R. E. Johnston and E. Sadinlija, “A new model for complete solutions to one-dimensional cutting stock problems,” European Journal of Operational Research, vol. 153, no. 1, pp. 176-183, 2004. · Zbl 1053.90038 · doi:10.1016/S0377-2217(02)00704-X
[9] M. H. Correia, J. F. Oliveira, and S. Ferreira, “Reel and sheet cutting at a paper mill,” Computers and Operations Research, vol. 31, no. 8, pp. 1223-1243, 2004. · Zbl 1073.90540 · doi:10.1016/S0305-0548(03)00076-5
[10] A. I. Hinxman, “The trim-loss and assortment problems: a survey,” European Journal of Operational Research, vol. 5, no. 1, pp. 8-18, 1980. · Zbl 0442.90072 · doi:10.1016/0377-2217(80)90068-5
[11] P. C. Gilmore and R. E. Gomory, “A linear programming approach to the cutting-stock problem,” Operations Research, vol. 9, pp. 849-859, 1961. · Zbl 0096.35501 · doi:10.1287/opre.9.6.849
[12] R. W. Haessler, “A heuristic programming solution to a non-linear cutting stock problem,” Management Science, vol. 17, pp. 793-802, 1971. · Zbl 0219.90021 · doi:10.1287/mnsc.17.12.B793
[13] I. Coverdale and F. Wharton, “An improved heuristic procedure for a nonlinear cutting stock problem,” Management Science, vol. 23, no. 1, pp. 78-86, 1976.
[14] J. E. Beasley, “A population heuristic for constrained two-dimensional non-guillotine cutting,” European Journal of Operational Research, vol. 156, no. 3, pp. 601-627, 2004. · Zbl 1056.90011 · doi:10.1016/S0377-2217(03)00139-5
[15] J. Riehme, G. Scheithauer, and J. Terno, “The solution of two-stage guillotine cutting stock problems having extremely varying order demands,” European Journal of Operational Research, vol. 91, no. 3, pp. 543-552, 1996. · Zbl 0918.90122 · doi:10.1016/0377-2217(95)00200-6
[16] T. Westerlund, “Some efficient formulations for the simultaneous solution of trim-loss and scheduling problems in the paper-converting industry,” Chemical Engineering Research and Design, vol. 76, no. 6, pp. 677-684, 1998. · doi:10.1205/026387698525388
[17] R. Alvarez-Valdés, A. Parajón, and J. M. Tamarit, “A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems,” Computers and Operations Research, vol. 29, no. 7, pp. 925-947, 2002. · Zbl 0995.90075 · doi:10.1016/S0305-0548(00)00095-2
[18] K. K. Lai and J. W. M. Chan, “Developing a simulated annealing algorithm for the cutting stock problem,” Computers and Industrial Engineering, vol. 32, no. 1, pp. 115-127, 1997.
[19] S. Xianjun, Y. Li, B. Zheng, and Z. Dai, “General particle swarm optimization based on simulated annealing for multi-specification one-dimensional cutting stock problem,” in Proceedings of the IEEE International Conference on Cybernetics and Intelligent Systems (CIS ’06), vol. 4456 of Lecture Notes in Computer Science, pp. 67-76, Guangzhou, China, 2007.
[20] K. Deep, P. Chauhan, and J. C. Bansal, “Solving nonconvex trim loss problem using an efficient hybrid particle swarm optimization,” in Proceedings of the World Congress on Nature and Biologically Inspired Computing (NABIC ’09), pp. 1608-1611, Coimbatore, India, December 2009. · doi:10.1109/NABIC.2009.5393658
[21] K. Deep, P. Chauhan, and M. Pant, “New hybrid discrete PSO for solving non convex trim loss problem,” International Journal of Applied Evolutionary Computation, vol. 3, no. 2, pp. 19-41, 2012.
[22] B. J. Wagner, “Genetic algorithm solution for one-dimensional bundled stock cutting,” European Journal of Operational Research, vol. 117, no. 2, pp. 368-381, 1999. · Zbl 0998.90524 · doi:10.1016/S0377-2217(98)00244-6
[23] R. Östermark, “Solving a nonlinear non-convex trim loss problem with a genetic hybrid algorithm,” Computers and Operations Research, vol. 26, no. 6, pp. 623-635, 1999. · Zbl 0933.90048 · doi:10.1016/S0305-0548(98)00035-5
[24] M. Ali, M. Pant, and A. Abraham, “Improving differential evolution algorithm by synergizing different improvement mechanisms,” ACM Transaction on Autonomous and Adaptive Systems, vol. 7, no. 2, pp. 1-32, 2012.
[25] R. Storn and K. Price, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, vol. 11, no. 4, pp. 341-359, 1997. · Zbl 0888.90135 · doi:10.1023/A:1008202821328
[26] M. Ali, M. Pant, and A. Abraham, “Simplex differential evolution,” Acta Polytechnica Hungarica, vol. 6, no. 5, pp. 95-115, 2009.
[27] R. S. Rahnamayan, H. R. Tizhoosh, and M. M. A. Salama, “Opposition-based differential evolution,” IEEE Transactions on Evolutionary Computation, vol. 12, no. 1, pp. 64-79, 2008. · Zbl 1181.68212 · doi:10.1109/TEVC.2007.894200
[28] C. S. Adjiman, I. P. Androulakis, and C. A. Floudas, “Global optimization of mixed-integer nonlinear problems,” AIChE Journal, vol. 46, no. 9, pp. 1769-1797, 2000.
[29] C. H. Yen, D. S. H. Wong, and S. S. Jang, “Solution of trim-loss problem by an integrated simulated annealing and ordinal optimization approach,” Journal of Intelligent Manufacturing, vol. 15, no. 5, pp. 701-709, 2004. · doi:10.1023/B:JIMS.0000037718.43289.62
[30] M. Srinivas and G. P. Rangaiah, “Differential evolution with tabu list for solving nonlinear and mixed-integer nonlinear programming problems,” Industrial and Engineering Chemistry Research, vol. 46, no. 22, pp. 7126-7135, 2007. · doi:10.1021/ie070007q
[31] R. Angira and B. V. Babu, “Optimization of process synthesis and design problems: a modified differential evolution approach,” Chemical Engineering Science, vol. 61, no. 14, pp. 4707-4721, 2006. · Zbl 1266.90159 · doi:10.1016/j.ces.2006.03.004
[32] K. Deb, “An efficient constraint handling method for genetic algorithms,” Computer Methods in Applied Mechanics and Engineering, vol. 186, no. 2-4, pp. 311-338, 2000. · Zbl 1028.90533 · doi:10.1016/S0045-7825(99)00389-8
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.