Geodesic
Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 29 (2019) no. 4, pp. 599-611
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the problem of optimization of accompanying manufacturing in flexible or reconfigurable manufacturing systems. Using a set of obligatory products as an input, the initial problem is reduced to two interrelated subproblems: 1) for each product from the set of obligatory products, form a group of additional (accompanying) products that can be manufactured without changing the state of production, and 2) determine the order of manufacturing changeovers between the groups of additional products, as well as the “points of entry and exit” for each group. The subproblems are considered sequentially: the first subproblem is reduced to the maximum weight clique problem, the second — to the cluster traveling salesman problem. Large-scale computational experiments were conducted to reveal the benefits of applying effective modern methods for solving both subproblems in comparison with the greedy solution (which models the rational actions of a human operator solving large accompanying manufacturing problems in short time).
Keywords: optimization of accompanying manufacturing, flexible and reconfigurable manufacturing, maximum weight clique, cluster travelling salesman problem. 
@article{VUU_2019_29_4_a9,
     author = {A. N. Belousov and E. E. Ivanko},
     title = {Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {599--611},
     year = {2019},
     volume = {29},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2019_29_4_a9/}
}
TY  - JOUR
AU  - A. N. Belousov
AU  - E. E. Ivanko
TI  - Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2019
SP  - 599
EP  - 611
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VUU_2019_29_4_a9/
LA  - ru
ID  - VUU_2019_29_4_a9
ER  - 
%0 Journal Article
%A A. N. Belousov
%A E. E. Ivanko
%T Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2019
%P 599-611
%V 29
%N 4
%U http://geodesic.mathdoc.fr/item/VUU_2019_29_4_a9/
%G ru
%F VUU_2019_29_4_a9
A. N. Belousov; E. E. Ivanko. Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 29 (2019) no. 4, pp. 599-611. http://geodesic.mathdoc.fr/item/VUU_2019_29_4_a9/

[1] J. Berk, Cost reduction and optimization for manufacturing and industrial companies, Wiley, 2010 | DOI

[2] M. Caramia, P. Dell'Olmo, Effective resource management in manufacturing systems: Optimization algorithms for production planning, Springer, 2006 | DOI

[3] R. R. Venkata, Advanced modeling and optimization of manufacturing processes: International research and development, Springer, 2011 | DOI

[4] M. Yoshimura, “System design optimization for product manufacturing”, Concurrent Engineering, 15:4 (2007), 329–343 | DOI

[5] M. Abbasi, M. Houshmand, “Production planning and performance optimization of reconfigurable manufacturing systems using genetic algorithm”, The International Journal of Advanced Manufacturing Technology, 54:1–4 (2011), 373–392 | DOI

[6] A. I. Dashchenko, Reconfigurable manufacturing systems and transformable factories, Springer, 2006 | DOI

[7] M. Bortolini, F. G. Galizia, C. Mora, “Reconfigurable manufacturing systems: Literature review and research trend”, Journal of Manufacturing Systems, 49 (2018), 93–106 | DOI

[8] M. G. Mehrabi, A. G. Ulsoy, Y. Koren, “Reconfigurable manufacturing systems: Key to future manufacturing”, Journal of Intelligent Manufacturing, 11:4 (2000), 403–419 | DOI

[9] M. Kaighobadi, K. Venkatesh, “Flexible manufacturing systems: An overview”, International Journal of Operations and Production Management, 14:4 (1994), 26–49 | DOI

[10] S. H. Suh, S. K. Kang, D. H. Chung, I. Stroud, Theory and design of CNC systems, Springer, 2008 | DOI | Zbl

[11] B. Xing, G. Bright, N. Tlale, J. Potgieter, “Reconfigurable manufacturing system for agile mass customization manufacturing”, 22nd International Conference on CAD/CAM, Robotics and Factories of the Future, 2006

[12] F. M. Defersha, M. Chen, “A comprehensive mathematical model for the design of cellular manufacturing systems”, International Journal of Production Economics, 103:2 (2006), 767–783 | DOI

[13] S. S. Heragu, “Group technology and cellular manufacturing”, IEEE Transactions on Systems, Man, and Cybernetics, 24:2 (1994), 203–215 | DOI

[14] N. Singh, “Design of cellular manufacturing systems: An invited review”, European Journal of Operational Research, 69:3 (1993), 284–291 | DOI

[15] N. Singh, D. Rajamani, Cellular manufacturing systems: Design, planning and control, Springer US, 2012 | DOI

[16] S. Benjaafar, S. S. Heragu, S. A. Irani, “Next generation factory layouts: Research challenges and recent progress”, INFORMS Journal on Applied Analytics, 32:6 (2002), 58–76 | DOI

[17] Y. Koren, “General RMS characteristics. Comparison with dedicated and flexible systems”, Reconfigurable Manufacturing Systems and Transformable Factories, Springer, 2006, 27–45 | DOI

[18] Y. Koren, U. Heisel, F. Jovane, T. Moriwaki, G. Pritschow, G. Ulsoy, H. van Brussel, “Reconfigurable manufacturing systems”, CIRP Annals, 48:2 (1999), 527–540 | DOI

[19] Y. Koren, M. Shpitalni, “Design of reconfigurable manufacturing systems”, Journal of Manufacturing Systems, 29:4 (2010), 130–141 | DOI

[20] E. Ahmadi, B. Goldengorin, G. A. Suer, H. Mosadegh, “A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problem”, Applied Soft Computing, 65 (2018), 214–229 | DOI

[21] M. A. Al-Fawzan, K. S. Al-Sultan, “A tabu search based algorithm for minimizing the number of tool switches on a flexible machine”, Computers and Industrial Engineering, 44:1 (2003), 35–47 | DOI

[22] J. Blazewicz, G. Finke, R. Haupt, G. Schmidt, “New trends in machine scheduling”, European Journal of Operational Research, 37:3 (1988), 303–317 | DOI | MR | Zbl

[23] Y. Demir, S. Kursat Isleyen, “Evaluation of mathematical models for flexible job-shop scheduling problems”, Applied Mathematical Modelling, 37:3 (2013), 977–988 | DOI | MR | Zbl

[24] A. Konak, S. Kulturel-Konak, M. Azizoglu, “Minimizing the number of tool switching instants in flexible manufacturing systems”, International Journal of Production Economics, 116:2 (2008), 298–307 | DOI

[25] G. S. Paiva, M. A.M. Carvalho, “Improved heuristic algorithms for the job sequencing and tool switching problem”, Computers and Operations Research, 88 (2017), 208–219 | DOI | MR | Zbl

[26] J. Xie, L. Gao, K. Peng, X. Li, H. Li, “Review on flexible job shop scheduling”, IET Collaborative Intelligent Manufacturing, 1:3 (2019), 67–77 | DOI | MR

[27] G. Gutin, A. P. Punnen, The traveling salesman problem and its variations, Springer, Boston, 2007 | DOI | MR | Zbl

[28] A. G. Chentsov, P. A. Chentsov, “Routing problem with precedence constraints (courier problem) dynamic programming approach”, Na peredovykh rubezhakh nauki i inzhenernogo tvorchestva, Vestnik UGTU-UPI, 15, USTU-UPI, Yekaterinburg, 2004, 148–152 (in Russian)

[29] B. Kalantari, A. V. Hill, S. R. Arora, “An algorithm for the traveling salesman problem with pickup and delivery customers”, European Journal of Operational Research, 22:3 (1985), 377–386 | DOI | MR | Zbl

[30] L. Schrage, K. R. Baker, “Dynamic programming solution of sequencing problems with precedence constraints”, Operations Research, 26:3 (1978), 444–449 | DOI | Zbl

[31] A. C. Beezao, J. F. Cordeau, G. Laporte, H. H. Yanasse, “Scheduling identical parallel machines with tooling constraints”, European Journal of Operational Research, 257:3 (2017), 834–844 | DOI | MR | Zbl

[32] T. P. Huy, Constraint propagation in flexible manufacturing, Springer, 2000 | DOI | MR | Zbl

[33] J. van Pinxten, M. Geilen, T. Basten, U. Waqas, L. Somers, “Online heuristic for the multi-objective generalized traveling salesman problem”, 2016 Design, Automation and Test in Europe Conference Exhibition (DATE), 2016, 822–825 | DOI

[34] J. van Pinxten, Optimization of product flows in flexible manufacturing systems, PhD thesis, Eindhoven University of Technology, 2018

[35] M. Berrada, K. E. Stecke, “A branch and bound approach for machine load balancing in flexible manufacturing systems”, Management Science, 32:10 (1986), 1316–1335 | DOI | Zbl

[36] Y. C. Ho, H. W. Hsieh, “A part-and-tool assignment method for the workload-balance between machines and the minimisation of tool-shortage occurrences in an FMS”, International Journal of Production Research, 43:9 (2005), 1831–1860 | DOI | Zbl

[37] C. N. Potts, J. D. Whitehead, “Workload balancing and loop layout in the design of a flexible manufacturing system”, European Journal of Operational Research, 129:2 (2001), 326–336 | DOI | MR | Zbl

[38] W. J. Boe, C. H. Cheng, “A close neighbour algorithm for designing cellular manufacturing systems”, International Journal of Production Research, 29:10 (1991), 2097–2116 | DOI | Zbl

[39] H. M. Chan, D. A. Milner, “Direct clustering algorithm for group formation in cellular manufacture”, Journal of Manufacturing Systems, 1:1 (1982), 65–75 | DOI

[40] C. H. Chu, “Cluster analysis in manufacturing cellular formation”, Omega, 17:3 (1989), 289–295 | DOI

[41] C. H. Chu, J. C. Hayya, “A fuzzy clustering approach to manufacturing cell formation”, International Journal of Production Research, 29:7 (1991), 1475–1487 | DOI

[42] G. C. Onwubolu, M. Mutingi, “A genetic algorithm approach to cellular manufacturing systems”, Computers and Industrial Engineering, 39:1–2 (2001), 125–144 | DOI

[43] R. B. R. De Souza, R. Bell, “A tool cluster based strategy for the management of cutting tools in flexible manufacturing systems”, Journal of Operations Management, 10:1 (1991), 73–91 | DOI | MR

[44] L. Kaufman, P. J. Rousseeuw, Finding groups in data: An introduction to cluster analysis, John Wiley and Sons, 1990 | DOI | MR | Zbl

[45] V. N. Hsu, D. Chhajed, T. Lowe, “Tool design problems in a punch press flexible manufacturing system”, IIE Transactions, 30:4 (1998), 331–340 | DOI | MR

[46] H. Wang, B. Alidaee, F. Glover, G. Kochenberger, “Solving group technology problems via clique partitioning”, International Journal of Flexible Manufacturing Systems, 18 (2006), 77–97 | DOI | MR | Zbl

[47] R. G. Askin, “Contributions to the design and analysis of cellular manufacturing systems”, International Journal of Production Research, 51:23–24 (2013), 6778–6787 | DOI

[48] R. Macchiaroli, S. Riemma, “Clustering algorithms to optimize the tool handling system management in an FMS”, International Journal of Flexible Manufacturing Systems, 8 (1996), 183–201 | DOI

[49] K. E. Stecke, “Formulation and solution of non-linear integer production planning problems for flexible manufacturing system”, Management Science, 29:3 (1983), 272–288 | DOI

[50] K. E. Stecke, J. J. Solberg, “Loading and control policies for a flexible manufacturing system”, International Journal of Production Research, 19:5 (1981), 481–490 | DOI

[51] J. A. Chisman, “The clustered traveling salesman problem”, Computers and Operations Research, 2:2 (1975), 115–119 | DOI

[52] K. Helsgaun, Solving the clustered traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm, Technical report No 142, Roskilde University, 2014, 16 pp. | MR

[53] G. Finke, A. Kusiak, “Models for the process planning problem in flexible manufacturing systems”, The International Journal of Advanced Manufacturing Technology, 2:2 (1987), 3–12 | DOI

[54] R. W. Hamming, “Error detecting and error correcting codes”, The Bell System Technical Journal, 29:2 (1950), 147–160 | DOI | MR | Zbl

[55] H. Jiang, C. Li, Y. Liu, F. Manya, “A two-stage MaxSAT reasoning approach for the maximum weight clique problem”, Thirty-Second AAAI Conference on Artificial Intelligence, 2018 https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16809

[56] A. G. Chentsov, Extremal routing and distribution problems: theory, Regular and Chaotic Dynamics, M., 2007