Document Type : Research Paper

Authors

Abstract

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

Keywords

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