在成衣業中，因各服裝的尺寸與眾多服裝類別而有多元的成衣樣板，馬克排版的用意即是將這些成衣樣板在一定長度與寬度的紙上進行移動與排列以形成一張馬克才能執行後續裁剪布料與縫製的程序，所以馬克排版也可以歸類為一種二維排版問題。在進行馬克排版時，需要將樣板排列緊密以減少裁減過後所造成的布料浪費，因此，本研究以馬克的最小長度為目標，以混和啟發式演算法的方式來求出最佳的馬克排版與長度。
首先，本研究考慮多種旋轉角度與鏡像的翻轉來獲取更多樣化的排版結果，而透過這些多元的排版結果，可以得到最佳馬克排版與其最小長度的機會亦會愈高。因此，本研究依上述的考慮條件呈現新的移動方法，用於樣板不重疊的情況下進行排列與移動以獲得初解的馬克排版與長度。為了能改善初解，本研究考量柔性計算，基因演算法與模擬退火法來各結合本研究的移動方法，以尋找具有最佳旋轉角度與翻轉位置的排列順序，從而獲得馬克的最小長度，此外，本研究亦利用基因演算法的全局搜索與模擬退火法的局部搜索之特性，提出混合式基因演算法－模擬退火法來比較此三種演算法的適應值與效率。本研究亦考慮於旋轉角度上的特殊應用情況，以便成衣業於不同狀況下可以決定和式的演算法來執行馬克排版問題。

With diverse sizes and categories of clothes in apparel industry, marker planning aims to arrange and move all these parts of clothes in a long-thin paper before cutting process, which can also be considered as one of a category in two-dimensional packing problems. In order to decrease the wastage of fabric after the cutting process, the marker layout essentially needs to be as compact as possible. Therefore, a minima length in marker layout is required in marker planning problem. In this paper, hybrid heuristics are proposed to conduct and acquire the optimized marker layout and length.
Firstly, a Moving Heuristic is presented as a new packing method to arrange and move the patterns without overlapped situation, where an initial marker will be presented to calculate the length. Specially, this heuristic considers multiple rotated angles and flipping positions of the patterns in order to obtain more diverse arrangements. With more different arrangements, the higher chance of optimized marker layout and length can be obtained. Next, to improve this initial solution, soft computing algorithms are taken into account, including genetic algorithm, simulated annealing, and hybrid genetic algorithm-simulated annealing proposed in this paper to find the best arranging sequence, obtaining the minima length in this marker layout and comparing each of the fitness value and efficiency. In addition, special case with specific scenarios in rotated angles is considered, so that the industry can decide the suitable algorithms to conduct the marker planning problem.

Bennell, J. A., & Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), 397-415.

Bortfeldt, A. (2006). A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research, 172(3), 814-837.

Burke, E. K., Hellier, R. S., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179(1), 27-49.

Chen, P. H., & Shahandashti, S. M. (2009). Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction, 18(4), 434-443.

Chen, P., Fu, Z., Lim, A., & Rodrigues, B. (2003). Two-dimensional packing for irregular shaped objects. In 36th Annual Hawaii International Conference on System Sciences, 2003. Proceedings of the (pp. 10-pp). IEEE.

Dowsland, K. A., Vaid, S., & Dowsland, W. B. (2002). An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research, 141(2), 371-381.

Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99.

Gomes, A. M., & Oliveira, J. F. (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3), 811-829.

Huang, E., & Korf, R. E. (2013). Optimal rectangle packing: An absolute placement approach. Journal of Artificial Intelligence Research, 46, 47-87.

Jacobs-Blecha, C., Ammons, J. C., Schutte, A., & Smith, T. (2007). Cut order planning for apparel manufacturing. IIE transactions, 30(1), 79-90.

Jain, S., & Gea, H. C. (1998). Two-dimensional packing problems using genetic algorithms. Engineering with Computers, 14(3), 206-213.

Jakobs, S. (1996). On genetic algorithms for the packing of polygons. European journal of operational research, 88(1), 165-181.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.

Leung, T. W., Chan, C. K., & Troutt, M. D. (2003). Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 145(3), 530-542.

Lin, F. T., Kao, C. Y., & Hsu, C. C. (1993). Applying the genetic approach to simulated annealing in solving some NP-hard problems. IEEE Transactions on systems, man, and cybernetics, 23(6), 1752-1767.

Lin, Y. K., Yeh, C. T., & Huang, P. S. (2013). A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem. Applied Soft Computing, 13(8), 3529-3543.

Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European journal of operational research, 141(2), 241-252.
Mahadevan, A. (1984). Optimization in computer-aided pattern packing (marking, envelopes).

Martins, T. C., & Tsuzuki, M. D. S. G. (2010). Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions. Expert Systems with Applications, 37(3), 1955-1972.

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.

M'Hallah, R., & Bouziri, A. (2016). Heuristics for the combined cut order planning two‐dimensional layout problem in the apparel industry. International Transactions in Operational Research, 23(1-2), 321-353.

Mundim, L. R., Andretta, M., & de Queiroz, T. A. (2017). A biased random key genetic algorithm for open dimension nesting problems using no-fit raster. Expert Systems with Applications, 81, 358-371.

Pinheiro, P. R., Amaro Júnior, B., & Saraiva, R. D. (2016). A random-key genetic algorithm for solving the nesting problem. International Journal of Computer Integrated Manufacturing, 29(11), 1159-1165.

Sha, O. P., & Kumar, R. (2000). Nesting of two-dimensional irregular parts within an irregular boundary using genetic algorithm. Journal of ship production, 16(4), 222-232.

Shalaby, M. A., & Kashkoush, M. (2013). A particle swarm optimization algorithm for a 2-D irregular strip packing problem. American Journal of Operations Research, 3(02), 268.

Taiwan Textile Federation (2017). 2017年臺灣紡織工業概況-紡拓會. Retrieved April 29, 2019, from https://www.textiles.org.tw/TTF/main/content/wHandMenuFile.ashx?file_id=1

Van Laarhoven, P. J., & Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications (pp. 7-15). Springer, Dordrecht.

Van Laarhoven, P. J., & Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications (pp. 7-15). Springer, Dordrecht.

Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3), 1109-1130.

Whitley, D. (1994). A genetic algorithm tutorial. Statistics and computing, 4(2), 65-85.

Wong, W. K., Guo, Z. X., & Leung, S. Y. S. (2013). Optimizing cut order planning in apparel production using evolutionary strategies. Optimizing Decision Making in the Apparel Supply Chain Using Artificial Intelligence (AI), 81-105.

Wong, W. K., Wang, X. X., & Guo, Z. X. (2013). Optimizing marker planning in apparel production using evolutionary strategies and neural networks. Optimizing decision making in the apparel supply chain using artificial intelligence (AI): form production to retail. Woodhead Publishing Series in Textiles, 106-131.

史俊友, & 冯美贵. (2007). 二维不规则件优化排样的小生境遗传算法. 工程设计学报, 14(2), 170-174.