حل مسأله ی برش دوبعدی غیرگیوتینی با تقاضا با استفاده از الگوریتم بهینه سازی ازدحام ذرات

نوع مقاله: مقاله پژوهشی

نویسندگان

1 کارشناسی ارشد مدیریت صنعتی دانشگاه یزد

2 عضو هیات علمی گروه مدیریت صنعتی دانشکده اقتصاد دانشگاه یزد

چکیده

بهینهسازی چیدمان قطعات کاربردهای فراوانی در صنایع برش ورق فلزی، برش الوار، تولید
شیشه، کاغذ و پوشاک دارد و به دلیل اهمیت کاهش ضایعات، روش های زیادی برای حل این
مسأله ارائه شده است. یکی از بهترین روشها استفاده از الگوریتم بهینهسازی ازدحام ذرات میباشد.
در این پژوهش، مسألهی برش دوبعدی با تقاضا مورد بررسی قرار میگیرد. در این مسأله باید با برش
ورق های مستطیل شکل بزرگ، مستطیلهای کوچکتر مورد نیاز به نحوی تولید شوند که ضمن
تأمین تقاضای آنها، ضایعات یا تعداد ورقهای مصرفی حداقل شود. در این مقاله جهت حل این
مسأله از الگوریتم بهینهسازی ازدحام ذرات استفاده شده است. به منظور بهبود کارایی این الگوریتم و
بهکار گرفته شد. جهت حل CUL جلوگیری از همپوشانی در مسأله ی برش، الگوریتم ابتکاری
مسألهی فوق، نرم افزاری تهیه شد. این نرم افزار به دو حالت عمل میکند. در حالت اول با در
نظرگرفتن طول و عرض صفحه ی اصلی، اندازه قطعات و تعداد مورد تقاضا، الگوی بهینهی برش را
ارائه میدهد. در حالت دوم، امکان دادن عرضهای متفاوت به نرم افزار وجود دارد. در این حالت،
نرمافزار پس از ارائهی عرض بهینه، الگوی بهینه ی برش و طول بهینهی صفحهی اصلی را نیز برای
کاربر مشخص میکند.

کلیدواژه‌ها


عنوان مقاله [English]

Solving two dimensional non-guillotine cutting problem Using Particle Swarm Optimization

نویسندگان [English]

  • Faezeh Asadian Ardakani 1
  • Ali Morovati Sharifabadi 2
چکیده [English]

One of the solutions for solving cutting stock problem in different
industries, such as sheet metal, lumber, glass, paper and textile, is
applying ,Particle Swarm Optimization to minimize the waste of
rawmaterials. This article is intended to solve two-dimensional cutting
problem. In these problems, larger rectangular plates, divided into
smaller rectangularsegments, aim to minimizing the number of used
plates or the waste of plates by considering demand. In this article
PSO is used. To enhance the efficiency of algorithm, and preventing
overlap in cutting problem, the CUL algorithm is used. In order to
investigate the results of algorithm, new software has been designed.
This software has two ways for solving the problem. First, it ends up
with optimized cutting pattern considering the number and dimension
of segments and, length and width of main plate. Also, there is a
possibility to give different width to software, in this case, the
software gives the user the optimum cutting pattern and optimum
length of main plate in addition to optimum width

کلیدواژه‌ها [English]

  • Optimization
  • Meta-Heuristic Algorithms
  • Discrete Particle Swarm Optimization (DPSO)
  • CUL algorithm
  • Twodimensional Cutting Problem
1. مصلحی ٬ قاسم. رضایی ٬ علیرضا. ) 1383 (، "ارائه الگوریتمی برای مسئله برش دوبعدی با
. تقاضا". استقلا ، ل سال ٬23 شماره 2
2. Dyckhoff, H. )1990(. A typology of cutting and packing problems.
European Journal of Operational Research., 44, pp. 145–159.
3. Chambers, M.L.; Dyson, R.G. (1976). The cutting stock problem in
the flat glass industry. Operations Research Quarterly., Vol 27, Nr.
4, pp. 949 -957.
4. Coffman, E.G.; Garey, M.R.; Johnson, D.S.; Tarjan, R.E. (1980).
Performance Bounds for Level-Oriented Two-Dimensional Packing
Algorithms. SIAM Journal on Computing., 9, 4, pp. 808-826.
5. Coffman, E.G.; Shor, P.W. (1990). Average-Case Analysis of Cutting
and Packing in Two Dimensions. European Journal of Operational
Research., 44, 2, pp. 134-145.
6. Paul, R.J. (1979). A production scheduling problem in the glass
container industry. Operations Research., Vol 27, Nr. 2, pp. 290-
302.
7. Van-dat, C.; Hifi,mhand, and Le cun , bertrand, . (1997).
Constrained two dimensional cutting stock problems , a best first
branch and bound algorithm. laborattoire PR&SM-CNRS URA
1525, University of Versailles, paris.
8. Whitlock, C.; Christofides, N. )1977(. an Algorithm for Two-
Dimensional Cutting Problems. Operations Research., Vol. 25, Nr. 1,
January-February, pp. 30- 44.
9. Gass, S. (1985). Linear Programming, Methods and Applications.
McGraw-Hill
10. Gradišar, M.; Jesenko, J.; Resinovič, G. (1997). Optimization of roll
cutting in clothing industry. Computer & Operations Research., 24,
pp. 945-953.
11. Gradišar, M.; Resinovič, G.; Jesenko, J.; Kljajić, M. (1999). A
sequential heuristic procedure for one-dimensional cutting. European
Journal of Operational Research., 114, pp. 557-568.
12. Kopač, J. (2002). Cutting forces and Their Influence on the
Economics of Machining. Strojniški vestnik - Journal of Mechanical
Engineering., 48 3, pp. 121-132.
13. Vasko, F.; Newhart, D.; Stott, K. (1999). A hierarchical approach
for one-dimensional cutting stock problems in the steel industry that
maximizes yield and minimizes overgrading. European Journal of
Operational Research., 114, pp. 72-82.
14. Westerlund, T.; Harjunkoski, I.; Isaksson, J. (1998). Solving a
Production Optimization Problem in a Paper-Converting Mill with
MILP. Computers & Chemical Engineering., 22, pp. 563-570.
15. Nazemi, J.(2005). Kiln Planning a Cutting Stock Approach, Social
Research Research Network.
16. Kantorovich, L.V. )1939(. Mathematical methods of organizing and
planning production. Mgmt. Sci.,Vol. , pp.363-422.
حل مسأله ی برش دوبعدی غیرگیوتینی با... 67
17. Gilmore, P.C.; Gomory, R.E. (1961). A Linear Programming
Approach to the Cutting-Stock Problem. Operations Research., Vol.
9, pp. 849-859.
18. Gilmore, P.C.; Gomory, R.E. (1965). Multi-stage cutting stock
problems of two and more dimensions. Operations Research., 13, pp.
94–120.
19. Farley, A.A. (1988). Mathematical programming models for cutting
stock problems in the clothing industry. Journal of the Operational
Research Society., 39, pp. 41–53.
20. Farley, A.A. (1990). A note on bounding a class of linear
programming problems, including cutting stock problems. Operations
Research., 38, pp. 922–923.
21. Beasley, J.E. )1985(. Algorithms for Unconstraind Two-Dimensional
Guillotine Cutting. Operation’s Research Society.,Vol.36, No.4,
PP.297-306.
22. Hifi, M.; Ouafi, R. )1977(. Best-first search And Dynamic
Programming Methods for Cutting Problems: The cases of One or
More Stock Plates. Computers ind.Eng., Vol.32, No.1, PP.187-205,.
23. Agrawal, P.K. (1993). Minimizing trim loss in cutting rectangular
blanks of a single size from a rectangular sheet using orthogonal
guillotine cuts. European Journal of Operational Research., 64, pp.
410–422.
24. Cui, Y. (2005). Dynamic programming algorithms for the optimal
cutting of equal rectangles. Applied Mathematical Modeling., 29, pp.
1040-1053.
25. Cui, Y. (2006). Simplest optimal cutting patterns for equal
rectangles. Operations Research Letters, 34, pp. 630-638.
26. Cheng, C.H.; Feiring, B.R.; Cheng, T.C. (1994). The cutting stock
problem-a survey. International Journal of Production Economics.,
36, pp. 291–305.
27. Dowsland, K.A.; Dowsland, W.B. (1992). Packing problems.
European Journal of Operational Research., 56, pp. 2-14.
28. [82] Haessler, R.W.; Sweeney, P.E. (1991). Cutting stock problems
and solution procedures. European Journal of Operational Research.,
54, pp. 141-150.
29. Sweeney, P.E.; Paternoster, E.R. (1992). Cutting and packing
problems: a categorized, application-orientated research
bibliography. Journal of the Operational Research Society., 43, pp.
691-706.
30. Arenales, M.; Morabito, R. (1995). An AND/OR-graph approach to
the solution of two-dimensional non-guillotine cutting problems.
European Journal of Operational Research., 84, pp. 599-617.
31. Beasley, J.E. )1985(. An Exact Two-Dimensional Non-Guillotine
Cutting Tree Search Procedure. Operation’s Research., Vol.33,
No.1, PP.49-64.
32. Hadjiconstantinou, E.; Christofides, N. (1995). An exact algorithm
for general, orthogonal, two-dimensional knapsack problems.
European Journal of Operational Research., 83, pp. 39-56.
67 مطالعات مدیریت صنعتی، سال دهم، شماره 68 ، پاییز 19
33. Lai, K.K.; Chan, W.M. (1997). An evolutionary algorithm for the
rectangular cutting stock problem. International Journal of Industrial
Engineering., 4, pp. 130-139.
34. Tsai, R.D.; Malstrom, E.M.; Meeks, H.D. (1988). A twodimensional
palletizing procedure for warehouse loading operations.
IIE Transactions., 20, pp. 418-425.
35. Suliman, S.M.A. (2006). A sequential heuristic procedure for the
two-dimensional cutting-stock problem. Int. J. Production
Economics., 99, pp. 177–185.
36. Hadjiconstantinou, E.; Iori, M. (2007). A hybrid genetic algorithm
for the two-dimensional single large object placement problem.
European Journal of Operational Research., 183, pp. 1150-1166.
37. Ono, T.; Ikeda, T. (1998). Optimization of two-dimensional guillotine
cutting by genetic algorithms. Proceedings of Sixth European
Congress on Intelligent Techniques and Soft Computing.
38. Lai, K. K.; Chan, W.M. (1997). Developing a Simulated Annealing
Algorithm for the Cutting Stock Problem. Computer and Industrial
Engineering., Vol. 33, pp. 115-127.
39. Leung, T. W.; Yung, C. H.; Troutt Marvin, D. )2001(. Applications
of Genetic Search and Simulated Annealing to the Two-dimensional
Non-guillotine Cutting Stock Problem. Computer and Industrial
Engineering., Vol. 40, pp. 201-214.
40. Beasley, J.W.(2000). A Population Heuristic for Constrained Two-
Dimensional Non-Guillotine Cutting.
http://mscmga.ms.ic.ac.uk/jebihtml.
41. Tiwari, S.; Chakraborti, N. (2006). Multi-objective optimization of a
two-dimensional cutting problem using genetic algorithms. Journal of
Materials Processing Technology., 173, pp. 384-393.
42. Jiang, J.Q.; Xing, X.L.; Yang, X.W.; Liang, Y.C. (2004). A Hybrid
Algorithm Based on PSO and Genetic Operation and Its Applications
For Cutting Stock Problem. Proceedings of The Third Int.
Conference on Machine Learning and Cybernetics., Shangai, pp.
2198-2201.
43. Liu, B.; Wang, L.; & Jin, Y. H. (2008). An effective hybrid PSObased
algorithm for flow shop scheduling with limited buffers.
Computers and Operations Research, 35, pp. 2791–2806.
44. Chen, M. (2011). A hybrid ANFIS model for business failure
prediction utilizating particle swarm optimization and subtractive
clustering, Information Sciences.
45. Wang, H. S.; Che, Z. H.; & Wu, C. (2010). Using analytic hierarchy
process and particle swarm optimization algorithm for evaluating
product plans. Expert Systems with Applications, 37, pp. 1023–
1034.
46. Marinakis, Y.; Marinaki, M.; Doumpos, M.; & Zopounidis, C.
(2009). Ant colony and particle swarm optimization for financial
classification problems. Expert Systems with Applications, 36, pp.
10604–10611.
47. Onut, S.; Tuzkaya, U. R.; & Dog˘ac, B. (2008). A particle swarm
optimization algorithm for the multiple-level warehouse layout design
problem. Computers and Industrial Engineering, 54, pp. 783–799.
حل مسأله ی برش دوبعدی غیرگیوتینی با... 67
48. Kennedy, J.; Eberhart, R. )1995(. Particle Swarm Optimization. in:
Proceedings of IEEE International Conference on Neural Networks,
Perth, Australia, pp. 1942-1948.
49. Shi, Y.; Eberhart, R.C. )1999 (. Empirical study of particle swarm
optimization. in: Proc. IEEE Int. Congr. Evolutionary Computation.,
vol 3, pp. 101-106.
50. Jia, D.L.; Zheng, G. X.; Qu, B.Y.; & Khurram Khan, M. (2011). A
hybrid particle swarm optimization algorithm for high-dimensional
problems, Computers & Industrial Engineering.
51. Kiranyaz, S.; Pulkkinen, J.; & Gabbouj, M. (2011). Multidimensional
particle swarm optimization in dynamic environments,
Expert Systems with Applications, 38, pp. 2212–2223.
52. Shi, Y.; Liu, H.; Gao, L.; & Zhang, G. (2011). Cellular particle
swarm optimization, Information Sciences, 181, pp. 4460–4493.
53. Chen, M.R.; Li, X.; Zhang, X.; & Lu, Y. Z. (2010). A novel particle
swarm optimizer hybridized with extremal optimization, Applied
Soft Computing, 10, pp. 367–373.
54. Liu, Y.; Wang, G.; Chen, H.; Dong, H.; Zhu, X.; & Wang, S.
(2011). An Improved Particle Swarm Optimization for Feature
Selection, Journal of Bionic Engineering, 8, pp. 191–200
55. Liua, B.; Wanga, L.; Liud, Y.; Qiane, B.; & Jin, Y. H. (2010). An
effective hybrid particle swarm optimization for batch scheduling of
polypropylene processes, Computers and Chemical Engineering, 34,
pp. 518–528
56. Robati, A.; Barani, G. A.; Nezam Abadi Pour, H.; Fadaee, M. J.;
Rahimi Pour Anaraki, J. (2011). Balanced fuzzy particle swarm
optimization, Applied Mathematical Modelling.
57. Poli, R.; Kennedy, J. )2007(. Particle swarm optimization An
overview.Springer Science., pp. 33–57.
58. Navalertporn, T.; Afzulpurkar, N.V. (2011). Optimization of tile
manufacturing process using particle swarm optimization, Swarm
and Evolutionary Computation, 1 , pp. 97–109.
59. Alatas, B.; Akin, E. A.; Ozers, B.l. (2007). Chaos-embedded particle
swarm optimization algorithms,Chaos, Solitons and Fractals.
60. Shi, Y.; Eberhart, R.C. ) 1998(. A modified particle swarm
optimizer[C]. In: IEEE World Congress on Computational
Intelligence., pp. 69-73.
61. Wang, K.P.; Huang, L.; Zhou, C.G.; Pang, W. (2003). Particle
Swarm Optimization For Traveling Salesman Problem. Proceedings
of The Second International Conference on Machine Learning and
Cybernetics, Xi’an, pp. 1583-1585.
62. Wang, C.; Zhang, J.; Yang, J.; Hu, C.; Liu, J. (2005). A Modified
Particle Swarm Optimization Algorithm and its Application for
Solving Traveling Salesman Problem. Neural Networks and Brain.,
ICNN&B '05. Int. Conference on, 2, pp. 689-694.
63. Soke, A.; Bingul, Z. Applications of Discrete PSO Algorithm to
Two-Dimensional Non-Guillotine Rectangular Packing Problems.
Conf. on Genetic and Evolutionary Methods.
68 مطالعات مدیریت صنعتی، سال دهم، شماره 68 ، پاییز 19
64. Malviya, R.; Kumar Pratihar, D. (2011). Tuning of neural networks
using particle swarm optimization to model MIG welding process,
Swarm and Evolutionary Computation.
65. Jakobs, S. (1996). On genetic algorithms for the packing of polygons.
European Journal of Operational Research, 88, pp. 165- 181