在服裝業上，由於布料的成本過高，因此縮短排版時間及提高利用利用率有助於節省成本。二維不規則切割和包裝問題是一種馬克排版優化資源的研究。透過在馬克上佈置不同形狀與尺寸的衣服圖案，同時防止圖案之間的任何重疊，找到最短的長度配置。由於衣服形狀不規則，因此隨著數量的增加會導致求解的時間呈現指數增長，因此需要使用啟發式演算法或混合啟發式演算法來解決這類的NP-Hard 或NP-complete問題。基於像素的表示法用於處理圖案的幾何形狀。基於粒子群優化的啟發式演算法是在這項研究中介紹用區域搜尋, 基因演算法與模擬退火法把基於粒子群優化性能提高。本文還考慮了混合順序尺寸，間隙和無間隙圖案排列，分離和不分離的尺寸排列。所提出的算法已在真實服裝行業中進行了測試，與其他的演算法相比之下，有大幅的改善。

In the apparel industry, fabric contributes to the high cost of raw material, and thus an improvement in terms of shorter and higher utilized marker layout will help cost efficiency of this industry. 2D Irregular Cutting and Packing Problem, also known as marker planning is a research field focusing on optimizing the fabric resource, by arranging a set of irregular shaped clothes pattern upon a sheet of fabric, while preventing any overlap between patterns, with the aim to find the shortest length arrangement. Due to the irregular shapes of clothes, the solving time will increase exponentially when there are more pieces involved, which make this problem NP-Hard or NP-complete. Therefore, the role of metaheuristic or hybrid heuristic approach is needed to save the problem. In this study, Moving Heuristic acts as placement strategy, considering pattern order and rotation degree. Pixel based or raster representation is used to handle the geometry of pattern. PSO-Based Heuristics are introduced in this research, by enhancing PSO performance with Local Search, GA and SA. Mix order size, gap and no-gap pattern arrangement, separated and unseparated size arrangement are also considered in this paper. The proposed algorithms are tested on real case apparel industry, compared with the well-known Bottom Left Fill Heuristic approach, and lead to competitive results.

Ayadi, O. and Barkallah, M. (2016). An adapted particle swarm optimization approach for a 2D guillotine cutting stock problem. Mechanics & Industry, 17, 508.
Bahrepour, M., Mahdipour, E. Cheloi, R., and Yaghoobi, M. (2009). Super-SAPSO: A New SA-Based PSO Algorithm. Applications of Soft Computing, AISC 58, 423-430.
Bennell, J. A, and Oliveira, J. F. (2008). The geometry of nesting problem: a tutorial. European Journal of Operational Research 184, 397-415.
Burke, E. et. al. (2006). A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Operations Research, Vol. 54, No. 3, 587-601.
Hifi, M. and Yousef, L. (2018). A hybrid algorithm for packing identical spheres into a container. Expert Systems with Applications, 96, 249-260.
Hong, C.H. 2019. Hybrid Heuristics for Marker Planning in Apparel Industry, Master thesis, National Taiwan University of Science and Technology, Taiwan.
Idoumghar, L., Melkemi, M., Schott, R., Aouad, M. I. (2011). Hybrid PSO-SA type algorithms for multimodal function optimization and reducing energy consumption in embedded systems. Applied Computational Intelligence and Soft Computing, article ID 138078.
Imamichi, T., Yagiura, M., and Nagamochi, H. (2009). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization, 6, 345-361.
Javidrad, F., Nazari, M., Javidrad, H.R. (2018). Optimum stacking sequence design of laminates using a hybrid PSO-SA method. Composite Structures, 185, 607-618.
Junior, B.A., Pinheiro, P.R., Saraiva, R.D. (2013). A Hybrid Methodology for Tackling the Irregular Strip Packing Problem. In 11th IFAC Workshop on Intelligent Manufacturing Systems, 396-401.
Lagha, G. B., Dahmani, N., Krichen, S. (2014). Particle swarm optimization approach for resolving the cutting stock problem. IEEE, International Conference on Advance Logistic and Transport, 259-263.
Leung, S. C. H., Lin, Y., and Zhang, D. (2012). Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Computers & Operations Research, 39, 678-686.
Liang, L. D. and Ye, J. W. (2010). Improved irregular parts nesting with particle swarm optimization. IEEE: International Conference on E-Business and E-Government, 769-772.
Liu, D. S., Tan, K. C., Huang, S. Y., Goh, C. K., Ho, W. K. (2008). On solving multiobjective bin packing problems using evolutionary particle swarm optimization. European Journal of Operational Research, 190, 357-382.
MirHassani, S. A. and Bashirzadeh, A. J. (2015). A GRASP metaheuristic for two-dimensional irregular cutting stock problem. Int J Adv Manuf Technol 81, 455-464.
Rocha, P., Rodrigues, R., Gomes, A. M., Toledo, F. M. B., Andretta, M. (2015). Two-phase approach to the nesting problem with continuous rotations. In IFAC-PapersOnLine 48-3, 501-506.
Salomon, C. P., Coutinho, M. P., Torres, G. L., Ferreira, C. (2011). Hybrid particle swarm optimization with biased mutation applied to load flow computation in electrical power system. Springer: Advances in Swarm Intelligence. In ICSI, Proceedings, Part I, 595-605.
Sato, A. K., Bauab, G. E. S., Martins, T. D. C., Tsuzuki, M. D. S. G., Gomes, A. M. (2016). Study of the grid size impact on a raster based strip packing problem solution. IFAC-PapersOnLine 49-31, 143-148.
Shalaby, M.A, and Kashkoush M. (2013). A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem. American Journal of Operations Research, Vol 3, 268-278.
Tang, H., Chen, R., Li, Y., Peng, Z., Guo, S., Du., Y. (2019). Flexible job-shop scheduling with tolerated time interval and limited starting time interval based on hybrid discrete PSO-SA: an application from a casting workshop. Applied Soft Computing Journal 78, 176-194.
Valvo, E. L. (2017). Metaheuristic algorithms for nesting problem of rectangular pieces. Procedia Engineering 183, 291-296.
Wong, W. K. and Leung, S.Y. S. (2013). Optimizing cut order planning in apparel production using evolutionary strategies. Woodhead Publishing Limited, 81-105.
Wong, W. K. and Wang, X. X. (2013). Optimizing marker planning in apparel production using evolutionary strategies and neural networks. Woodhead Publishing Limited, 106-131.
Xu, Y., Yang, G., Pan, C. (2013). A Heuristic Based on PSO for Irregular Cutting Stock Problem. In 13th IFAC Symposium on Large Scale Complex System: Theory and Applications, 473-477.
Yang, I. T. “Particle Swarm Optimization.” Application of Computational Intelligence in Engineering. 2019. National Taiwan University of Science and Technology. Lecture.
Yang, I. T. “Simulated Annealing.” Application of Computational Intelligence in Engineering. 2019. National Taiwan University of Science and Technology. Lecture.
Yu, S., Wei, Y. M., and Wang, K. (2012). A PSO-GA optimal model to estimate primary energy demand of China. Energy Policy, 42, 329-340.
Yu, V. F., Jewpanya, P., Ting, C. J., Redi, A. A. N. P. (2017). Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows. Applied Soft Computing, 61, 1022-1040.