phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2019 - 4 issue » pp. 599-611

Archive of Issues

Russia Yekaterinburg
Year
2019
Volume
29
Issue
4
Pages
599-611
<<
>>
Section Computer science
Title Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem
Author(-s) Belousov A.N.a, Ivanko E.E.a
Affiliations Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciencesa
Abstract 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
UDC 65.012.122, 519.688
MSC 68M20, 90B30
DOI 10.20537/vm190410
Received 10 October 2019
Language Russian
Citation Belousov A.N., Ivanko E.E. Experimental research of the application of modern combinatorial optimization solvers to the accompanying manufacturing optimization problem, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2019, vol. 29, issue 4, pp. 599-611.
References
  1. Berk J. Cost reduction and optimization for manufacturing and industrial companies, Wiley, 2010. https://doi.org/10.1002/9780470643815
  2. Caramia M., Dell'Olmo P. Effective resource management in manufacturing systems: Optimization algorithms for production planning, Springer, 2006. https://doi.org/10.1007/1-84628-227-6
  3. Venkata R.R. Advanced modeling and optimization of manufacturing processes: International research and development, Springer, 2011. https://doi.org/10.1007/978-0-85729-015-1
  4. Yoshimura M. System design optimization for product manufacturing, Concurrent Engineering, 2007, vol. 15, issue 4, pp. 329-343. https://doi.org/10.1177/1063293X07083087
  5. Abbasi M., Houshmand M. Production planning and performance optimization of reconfigurable manufacturing systems using genetic algorithm, The International Journal of Advanced Manufacturing Technology, 2011, vol. 54, issue 1-4, pp. 373-392. https://doi.org/10.1007/s00170-010-2914-x
  6. Dashchenko A.I. Reconfigurable manufacturing systems and transformable factories, Springer, 2006. https://doi.org/10.1007/3-540-29397-3
  7. Bortolini M., Galizia F.G., Mora C. Reconfigurable manufacturing systems: Literature review and research trend, Journal of Manufacturing Systems, 2018, vol. 49, pp. 93-106. https://doi.org/10.1016/j.jmsy.2018.09.005
  8. Mehrabi M.G., Ulsoy A.G., Koren Y. Reconfigurable manufacturing systems: Key to future manufacturing, Journal of Intelligent Manufacturing, 2000, vol. 11, no. 4, pp. 403-419. https://doi.org/10.1023/A:1008930403506
  9. Kaighobadi M., Venkatesh K. Flexible manufacturing systems: An overview, International Journal of Operations and Production Management, 1994, vol. 14, no. 4, pp. 26-49. https://doi.org/10.1108/01443579410056029
  10. Suh S.-H., Kang S.K., Chung D.-H., Stroud I. Theory and design of CNC systems, Springer, 2008. https://doi.org/10.1007/978-1-84800-336-1
  11. Xing B., Bright G., Tlale N., Potgieter J. Reconfigurable manufacturing system for agile mass customization manufacturing, 22nd International Conference on CAD/CAM, Robotics and Factories of the Future, 2006.
  12. Defersha F.M., Chen M. A comprehensive mathematical model for the design of cellular manufacturing systems, International Journal of Production Economics, 2006, vol. 103, no. 2, pp. 767-783. https://doi.org/10.1016/j.ijpe.2005.10.008
  13. Heragu S.S. Group technology and cellular manufacturing, IEEE Transactions on Systems, Man, and Cybernetics, 1994, vol. 24, no. 2, pp. 203-215. https://doi.org/10.1109/21.281420
  14. Singh N. Design of cellular manufacturing systems: An invited review, European Journal of Operational Research, 1993, vol. 69, no. 3, pp. 284-291. https://doi.org/10.1016/0377-2217(93)90016-G
  15. Singh N., Rajamani D. Cellular manufacturing systems: Design, planning and control, Springer US, 2012. https://doi.org/10.1007/978-1-4613-1187-4
  16. Benjaafar S., Heragu S.S., Irani S.A. Next generation factory layouts: Research challenges and recent progress, INFORMS Journal on Applied Analytics, 2002, vol. 32, no. 6, pp. 58-76. https://doi.org/10.1287/inte.32.6.58.6473
  17. Koren Y. General RMS characteristics. Comparison with dedicated and flexible systems, Reconfigurable Manufacturing Systems and Transformable Factories, Springer, 2006, pp. 27-45. https://doi.org/10.1007/3-540-29397-3_3
  18. Koren Y., Heisel U., Jovane F., Moriwaki T., Pritschow G., Ulsoy G., van Brussel H. Reconfigurable manufacturing systems, CIRP Annals, 1999, vol. 48, no. 2, pp. 527-540. https://doi.org/10.1016/S0007-8506(07)63232-6
  19. Koren Y., Shpitalni M. Design of reconfigurable manufacturing systems, Journal of Manufacturing Systems, 2010, vol. 29, no. 4, pp. 130-141. https://doi.org/10.1016/j.jmsy.2011.01.001
  20. Ahmadi E., Goldengorin B., Suer G.A., Mosadegh H. A hybrid method of 2-TSP and novel learning-based GA for job sequencing and tool switching problem, Applied Soft Computing, 2018, vol. 65, pp. 214-229. https://doi.org/10.1016/j.asoc.2017.12.045
  21. Al-Fawzan M.A., Al-Sultan K.S. A tabu search based algorithm for minimizing the number of tool switches on a flexible machine, Computers and Industrial Engineering, 2003, vol. 44, no. 1, pp. 35-47. https://doi.org/10.1016/S0360-8352(02)00183-3
  22. Blazewicz J., Finke G., Haupt R., Schmidt G. New trends in machine scheduling, European Journal of Operational Research, 1988, vol. 37, no. 3, pp. 303-317. https://doi.org/10.1016/0377-2217(88)90192-0
  23. Demir Y., Kursat Isleyen S. Evaluation of mathematical models for flexible job-shop scheduling problems, Applied Mathematical Modelling, 2013, vol. 37, no. 3, pp. 977-988. https://doi.org/10.1016/j.apm.2012.03.020
  24. Konak A., Kulturel-Konak S., Azizoglu M. Minimizing the number of tool switching instants in flexible manufacturing systems, International Journal of Production Economics, 2008, vol. 116, no. 2, pp. 298-307. https://doi.org/10.1016/j.ijpe.2008.09.001
  25. Paiva G.S., Carvalho M.A.M. Improved heuristic algorithms for the job sequencing and tool switching problem, Computers and Operations Research, 2017, vol. 88, pp. 208-219. https://doi.org/10.1016/j.cor.2017.07.013
  26. Xie J., Gao L., Peng K., Li X., Li H. Review on flexible job shop scheduling, IET Collaborative Intelligent Manufacturing, 2019, vol. 1, no. 3, pp. 67-77. https://doi.org/10.1049/iet-cim.2018.0009
  27. Gutin G., Punnen A.P. The traveling salesman problem and its variations, Boston: Springer, 2007. https://doi.org/10.1007/b101971
  28. Chentsov A.G., Chentsov P.A. Routing problem with precedence constraints (courier problem) dynamic programming approach, Vestnik UGTU-UPI. Na peredovykh rubezhakh nauki i inzhenernogo tvorchestva, Yekaterinburg: USTU-UPI, 2004, no. 15, pp. 148-152 (in Russian).
  29. Kalantari B., Hill A.V., Arora S.R. An algorithm for the traveling salesman problem with pickup and delivery customers, European Journal of Operational Research, 1985, vol. 22, no. 3, pp. 377-386. https://doi.org/10.1016/0377-2217(85)90257-7
  30. Schrage L., Baker K.R. Dynamic programming solution of sequencing problems with precedence constraints, Operations Research, 1978, vol. 26, no. 3, pp. 444-449. https://doi.org/10.1287/opre.26.3.444
  31. Beezao A.C., Cordeau J.-F., Laporte G., Yanasse H.H. Scheduling identical parallel machines with tooling constraints, European Journal of Operational Research, 2017, vol. 257, no. 3, pp. 834-844. https://doi.org/10.1016/j.ejor.2016.08.008
  32. Huy T.P. Constraint propagation in flexible manufacturing, Springer, 2000. https://doi.org/10.1007/978-3-642-58335-3
  33. van Pinxten J., Geilen M., Basten T., Waqas U., Somers L. Online heuristic for the multi-objective generalized traveling salesman problem, 2016 Design, Automation and Test in Europe Conference Exhibition (DATE), 2016, pp. 822-825. https://doi.org/10.3850/9783981537079_0953
  34. van Pinxten J. Optimization of product flows in flexible manufacturing systems, PhD thesis, Eindhoven University of Technology, 2018.
  35. Berrada M., Stecke K.E. A branch and bound approach for machine load balancing in flexible manufacturing systems, Management Science, 1986, vol. 32, no. 10, pp. 1316-1335. https://doi.org/10.1287/mnsc.32.10.1316
  36. Ho Y.-C., Hsieh H.-W. 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, 2005, vol. 43, no. 9, pp. 1831-1860. https://doi.org/10.1080/00207540512331340686
  37. Potts C.N., Whitehead J.D. Workload balancing and loop layout in the design of a flexible manufacturing system, European Journal of Operational Research, 2001, vol. 129, no. 2, pp. 326-336. https://doi.org/10.1016/S0377-2217(00)00230-7
  38. Boe W.J., Cheng C.H. A close neighbour algorithm for designing cellular manufacturing systems, International Journal of Production Research, 1991, vol. 29, no. 10, pp. 2097-2116. https://doi.org/10.1080/00207549108948069
  39. Chan H.M., Milner D.A. Direct clustering algorithm for group formation in cellular manufacture, Journal of Manufacturing Systems, 1982, vol. 1, no. 1, pp. 65-75. https://doi.org/10.1016/S0278-6125(82)80068-X
  40. Chu C.-H. Cluster analysis in manufacturing cellular formation, Omega, 1989, vol. 17, no. 3, pp. 289-295. https://doi.org/10.1016/0305-0483(89)90034-0
  41. Chu C.-H., Hayya J.C. A fuzzy clustering approach to manufacturing cell formation, International Journal of Production Research, 1991, vol. 29, no. 7, pp. 1475-1487. https://doi.org/10.1080/00207549108948024
  42. Onwubolu G.C., Mutingi M. A genetic algorithm approach to cellular manufacturing systems, Computers and Industrial Engineering, 2001, vol. 39, no. 1-2, pp. 125-144. https://doi.org/10.1016/S0360-8352(00)00074-7
  43. De Souza R.B.R., Bell R. A tool cluster based strategy for the management of cutting tools in flexible manufacturing systems, Journal of Operations Management, 1991, vol. 10, no. 1, pp. 73-91. https://doi.org/10.1016/0272-6963(91)90036-W
  44. Kaufman L., Rousseeuw P.J. Finding groups in data: An introduction to cluster analysis, John Wiley and Sons, 1990. https://doi.org/10.1002/9780470316801
  45. Hsu V.N., Chhajed D., Lowe T. Tool design problems in a punch press flexible manufacturing system, IIE Transactions, 1998, vol. 30, no. 4, pp. 331-340. https://doi.org/10.1080/07408179808966473
  46. Wang H., Alidaee B., Glover F., Kochenberger G. Solving group technology problems via clique partitioning, International Journal of Flexible Manufacturing Systems, 2006, vol. 18, pp. 77-97. https://doi.org/10.1007/s10696-006-9011-3
  47. Askin R.G. Contributions to the design and analysis of cellular manufacturing systems, International Journal of Production Research, 2013, vol. 51, no. 23-24, pp. 6778-6787. https://doi.org/10.1080/00207543.2013.825745
  48. Macchiaroli R., Riemma S. Clustering algorithms to optimize the tool handling system management in an FMS, International Journal of Flexible Manufacturing Systems, 1996, vol. 8, pp. 183-201. https://doi.org/10.1007/BF00394503
  49. Stecke K.E. Formulation and solution of non-linear integer production planning problems for flexible manufacturing system, Management Science, 1983, vol. 29, no. 3, pp. 272-288. https://doi.org/10.1287/mnsc.29.3.273
  50. Stecke K.E., Solberg J.J. Loading and control policies for a flexible manufacturing system, International Journal of Production Research, 1981, vol. 19, no. 5, pp. 481-490. https://doi.org/10.1080/00207548108956679
  51. Chisman J.A. The clustered traveling salesman problem, Computers and Operations Research, 1975, vol. 2, no. 2, pp. 115-119. https://doi.org/10.1016/0305-0548(75)90015-5
  52. Helsgaun K. Solving the clustered traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm, Roskilde University, 2014, no. 142, 16 p.
  53. Finke G., Kusiak A. Models for the process planning problem in flexible manufacturing systems, The International Journal of Advanced Manufacturing Technology, 1987, vol. 2, no. 2, pp. 3-12. https://doi.org/10.1007/BF02601472
  54. Hamming R.W. Error detecting and error correcting codes, The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147-160. https://doi.org/10.1002/j.1538-7305.1950.tb00463.x
  55. Jiang H., Li C., Liu Y., Manya F. 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. Chentsov A.G. Extremal'nye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii (Extremal routing and distribution problems: theory), Moscow: Regular and Chaotic Dynamics, 2007.
Full text
/doc/issues-2019/19-04-10.pdf
<< Previous article
Next article >>