In the textile and clothing industry, marker planning is a critical operation in the fabric-cutting room, in which pattern pieces of different sizes and styles of a garment are laid out on a sheet of paper with fixed width and arbitrary length in order to achieve the highest fabric utilization (marker efficiency). The layout always contains areas of unusable fabric due to the irregular shapes of garment pattern pieces. The minimization of fabric wastage is crucial to the reduction of production costs. In this study, a methodology that hybridizes a heuristic packing (HP) approach based on grid approximation with an integer representation-based (µ + λ) evolutionary strategy (ES) is proposed in order to obtain an efficient layout of garment patterns so as to optimize the fabric utilization. The performance of the proposed methodology is validated by the experiments and the results demonstrate that the proposed method provides an effective means by which to increase the marker efficiency.
Jhaveri, T., Rovner, V., Pileggi, L., Strojwas, A.J., Motiani, D., Kheterpal, V., Tong, K.Y., Hersan, T., and Pandini, D., Maximization of Layout Printability/Manufacturability by Extreme Layout Regularity , J. Micro/Nanolithography, 6(3), article no. 031011, (2007).
2.
Taylor, B., and Pileggi, L., Exact combinatorial optimization methods for physical design of regular logic bricks, in "Proceedings of Design Automation Conference" , 2007, pp. 344-349.
3.
Lodi, A., Martello, S., and Monaci, M., Two-Dimensional Packing Problems: a Survey, Europ. J. Oper. Res., 141, 241-252 (2002).
4.
Dowsland, K.A. , and Dowsland, W.B., Solution Approaches to Irregular Nesting Problems, Europ. J. Oper. Res., 84, 506- 521 ( 1995).
5.
Li, Z., and Milenkovic, V.J. , Compaction and Separation Algorithms for Non-Convex Polygons and their Applications, Europ. J. Oper. Res., 84, 539-561 (1995).
6.
Stoyan, Y.G., Novozhilova, M.V., and Kartashov, A.V., Mathematical Model and Method of Searching for a Local Extremum for the Non-Convex Oriented Polygons Allocation Problem, Europ. J. Oper. Res. , 92, 193-210 (1996).
7.
Bennell, J.A. , Dowsland, K.A., and Dowsland , W.B., The Irregular Cutting-Stock Problem-a New Procedure for Deriving the No-Fit Polygon, Comput. Oper. Res., 28(3), 271-287 (2001).
8.
Oliveira, J.F. , Gomes, A.M., and Ferreira , J.S., TOPOS-a New Constructive Algorithm for Nesting Problems, OR Spectr., 22(2), 263-284 (2000).
9.
Gomes, A.M., and Oliveira, J.F., A 2-exchange Heuristic for Nesting Problems, Europ. J. Oper. Res., 141, 359-370 (2002).
10.
Bennell, J.A. , and Dowsland, K.A., Hybridizing Tabu Search with Optimization Techniques for Irregular Stock Cutting, Manage. Sci., 47(8), 1160-1172 (2001).
11.
Oliveira, J.F. , and Ferreira, J.S., Algorithms for nesting problems, in "Applied Simulated Annealing, Lecture Notes in Economics and Mathematical System", Vol. 396, Vidal, R. V. V. (eds), 1993, pp. 255-273.
12.
Heckmann, R. , and Lengauer, T., A Simulated Annealing Approach to the Nesting Problem in the Textile Manufacturing Industry, Ann. Oper. Res., 57, 103-133 (1995).
13.
Burke, E., and Kendall, G., Applying simulated annealing and the no fit polygon to the nesting problem , in "Proceedings of the World Manufacturing Congress", 1999, pp. 27-30.
14.
Gomes, A.M., and Oliveira, J.F., Nesting irregular shapes with simulated annealing, in "Proceedings of the 3rd International Conference on Metaheuristics", 1999, pp. 235-239.
15.
Gomes, A.M. , and Oliveira, J.F., Solving Irregular Strip Packing Problems by Hybridizing Simulated Annealing and Linear Programming, Europ. J. Oper. Res., 171, 811-829 (2006).
16.
Blazewicz, J., Hawryluk, P., and Walkowiak, R., Using a Tabu Search Approach for Solving the Two-Dimensional Irregular Cutting Problem, Ann. Oper. Res., 41, 313-325 (1993).
17.
Bennell, J.A. , and Dowsland, K.A., A Tabu Thresholding Implementation for the Irregular Stock Cutting Problem, Int. J. Prod. Res., 37(18), 4259-4275 (1999).
18.
Han, G.C. , and Na, S.J., Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing, in "Proceedings of the Institute of Mechanical Engineers", 1996, pp. 509-519.
19.
Fujita, K., Akagji, S., and Kirokawa, N., Hybrid approach for optimal nesting using a genetic algorithm and a local minimization algorithm, in "Proceedings of the 19th Annual ASME Design Automation Conference", 1993, pp. 477-484.
20.
Jakobs, S., On Genetic Algorithms for the Packing of Polygons, Europ. J. Oper. Res., 88, 165-181 (1996).
21.
Bounsaythip, C., Maouche, S., and Neus, M., Evolutionary search techniques application in automated lay-planning optimization problem, in "Proceedings of the IEEE Conference on SMC", 1995, 4497-4502.
22.
Ismail, H.S., and Hon, K.K.B., Nesting of two-dimensional shapes using genetic algorithms, in "Proceedings of the Institute of Mechanical Engineers", 1995, pp. 115-124.
23.
Bounsaythip, C., and Maouche, S., Irregular shape nesting and placing with evolutionary approach, in "Proceedings of the IEEE International Conference on Systems, Man and Cybernetics", 4, 1997, pp. 425-430.
Hopper, E., "Two-dimensional Packing UtilizingEvolutionary Strategies and Other Meta-Heuristic Methods", PhD. Thesis, University of Wales, 2000 .
26.
Hifi, M., and Hallah, R.M., A Hybrid Algorithm for the Two-Dimensional Layout Problem: The Cases of Regular and Irregular Shapes, Int. Trans. Oper. Res., 10, 195-216 (2003).
27.
Bouziri, A. , and M’hallah , R., A Hybrid Genetic Algorithm for the Cut Order Planning Problem, Lect. Notes Comput. Sci. , 4570, 454-463, 2007.
28.
Goldberg, D.E. , "Genetic Algorithms in Search, Optimization and Machine Learning", Addison Wesley, Reading MA, 1989.
29.
Azar, Y., and Epstein, L., On Two Dimensional Packing, J. Algo., 25, 290-310, 1997.
30.
Rechenberg, I. , "Evolution Strategy: Optimization of Technical Systems according to the Principles of Biological Evolution", (in German), Frommann-Holzboog, Stuttgart, 1973 .
