A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories

Xiuqin Shang; Dayong Shen; Fei-Yue Wang; Timo R. Nyberg

doi:10.1109/JAS.2019.1911573

Volume 6 Issue 4

Jul. 2019

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2019 > 6(4): 961-968

Xiuqin Shang, Dayong Shen, Fei-Yue Wang and Timo R. Nyberg, "A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories," IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 961-968, July 2019. doi: 10.1109/JAS.2019.1911573

Citation:

Xiuqin Shang, Dayong Shen, Fei-Yue Wang and Timo R. Nyberg, "A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories," IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 961-968, July 2019. doi: 10.1109/JAS.2019.1911573

Citation:

PDF( 603 KB)

A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories

doi: 10.1109/JAS.2019.1911573

Funds: This work was supported in part by the National Key Research and Development Program of China (2018YFB1702701), the National Natural Science Foundation of China (61773381, 61773382, 61533019, 61702519), Dongguan's Innovation Talents Project (Gang Xiong), Guangdong's Science and Technology Project (2017B090912001), Beijing Natural Science Foundation (4182065), and Chinese Hunan's Science and Technology Project (20181040)

More Information

Author Bio:
Xiuqin Shang received the B.Eng. degree in automation from China University of Petroleum, Qingdao, China, in 2005, and the Ph.D. degree in control theory and control engineering from Zhejiang University, China, in 2010. Since 2011, she has been an Assistant Research Scientist in the State Key Laboratory of Management and Control for Complex Systems, Institute of Automation, Chinese Academy of Sciences, China. Her research interests include social manufacturing, industrial process con-and control

Dayong Shen received the bachelor degree and master degree in system engineering from NUDT in 2011 and 2013 respectively. He received the Ph.D. degree in management science and engineering from NUDT in 2018. His current research interests include intelligent scheduling, artificial intelligence algorithm, and parallel social systems

Fei-Yue Wang (S’87–M’89–SM’94–F’03) received the Ph.D. degree in computer and systems engineering from Rensselaer Polytechnic Institute, Troy, New York in 1990. He joined the University of Arizona in 1990 and became a Professor and Director of the Robotics and Automation Laboratory (RAL) and Program in Advanced Research for Complex Systems (PARCS). In 1999, he founded the Intelligent Control and Systems Engineering Center at the Institute of Automation, Chinese Academy of Sciences (CAS), Beijing, China, under the support of the Outstanding Oversea Chinese Talents Program from the State Planning Council and “100 Talent Program” from CAS, and in 2002, was appointed as the Director of the Key Laboratory of Complex Systems and Intelligence Science, CAS. From 2006 to 2010, he was Vice President for Research, Education, and Academic Exchanges at the Institute of Automation, CAS. In 2011, he became the State Specially Appointed Expert and the Director of the State Key Laboratory for Management and Control of Complex Systems. Dr. Wang’s current research focuses on methods and applications for parallel systems, social computing, parallel intelligence and knowledge automation. He was the Founding Editor-in-Chief (EiC) of the International Journal of Intelligent Control and Systems (1995–2000), Founding EiC of IEEE ITS Magazine (2006–2007), EiC of IEEE Intelligent Systems (2009-2012), and EiC of IEEE Transactions on ITS (2009–2016). Currently he is EiC of IEEE Transactions on Computational Social Systems, Founding EiC of IEEE/CAA Journal of Automatica Sinica, and Chinese Journal of Command and Control. Since 1997, he has served as General or Program Chair of more than 20 IEEE, INFORMS, ACM, and ASME conferences. He was the President of IEEE ITS Society (2005–2007), Chinese Association for Science and Technology (CAST, USA) in 2005, the American Zhu Kezhen Education Foundation (2007–2008), the Vice President of the ACM China Council (2010–2011), and the Vice President and Secretary General of Chinese Association of Automation (CAA, 2008–2018). Since 2019, he has been the President of CAA Supervision Council. Dr. Wang has been elected as Fellow of IEEE, INCOSE, IFAC, ASME, and AAAS. In 2007, he received the National Prize in Natural Sciences of China and was awarded the Outstanding Scientist by ACM for his research contributions in intelligent control and social computing. He received IEEE ITS Outstanding Application and Research Awards in 2009, 2011 and 2015, and IEEE SMC Norbert Wiener Award in 2014

Timo R. Nyberg received the M.Sc. (Tech) degree in mechanical engineering from Helsinki University of Technology, Espoo, Finland, in 1988, and the Dr. (Tech) degree in automation from Helsinki University of Technology, Espoo, Finland, in 1993. From 1996 to 2002, he was a Professor of Automation and Director of Graduate School, Tampere University of Technology, Finland. From 2001 to 2002, he was a Senior Vice President, Novo Astra Oy, Finland. From 2002 to 2005, he was Laboratory Director and Management Board member, Helsinki University of Applied Sciences, Finland. Since 2010, he has worked as a Senior Research Fellow and Research Director of School of Science at Aalto University, Finland. Since 2012, he has also been a Visiting Professor of Cloud Computing Center, CAS, China. His research interests include enterprise automation systems, business strategies in software, intelligent wearable device and social manufacturing. He has finished more than 30 research projects funded by Finnish TEKES, Academy of Finland, EU, and Finnish companies. He is the author or co-author of about 100 refereed journal and conference proceeding papers, and 35 EU/American/Finnish patents. He has experience from both the academic world and industries (Metso, Logica, and Nokia). He has over 15 years of experience from R&D cooperation with Chinese and American companies and universities (Tsinghua University, Tongji University, MIT, and Stanford University). He has been the board member in Finland & China Trade Association
Corresponding author: X. Q. Shang is with the State Key Laboratory for Management and Control of Complex Systems, Institute of Automation, Chinese Academy of Sciences (CAS), Beijing 100190, China (e-mail: xiuqin.shang@ia.ac.cn)
Received Date: 2018-10-09
Revised Date: 2018-11-15
Accepted Date: 2018-11-28

Available Online: 2019-05-27

Abstract

Abstract

We study the fabric spreading and cutting problem in apparel factories. For the sake of saving the material costs, the cutting requirement should be met exactly without producing additional garment components. For reducing the production costs, the number of lays that corresponds to the frequency of using the cutting beds should be minimized. We propose an iterated greedy algorithm for solving the fabric spreading and cutting problem. This algorithm contains a constructive procedure and an improving loop. Firstly the constructive procedure creates a set of lays in sequence, and then the improving loop tries to pick each lay from the lay set and rearrange the remaining lays into a smaller lay set. The improving loop will run until it cannot obtain any smaller lay set or the time limit is due. The experiment results on 500 cases show that the proposed algorithm is effective and efficient.
- Construction and improvement,
- cutting and packing,
- fabric spreading and cutting,
- heuristic algorithm

FullText(HTML)

References(29)

References

[1]	H. Dyckhoff, " A typology of cutting and packing problems,” European J. Operational Research, vol. 44, no. 2, pp. 145–159, 1990. doi: 10.1016/0377-2217(90)90350-K
[2]	P. E. Sweeney and E. R. Paternoster, " Cutting and packing problems: a categorized, application-orientated research bibliography,” J. Operational Research Society, vol. 43, no. 7, pp. 691–706, 1992. doi: 10.1057/jors.1992.101
[3]	C. Jacobs-Blecha, J. C. Ammons, A. Schutte, and T. Smith, " Cut order planning for apparel manufacturing,” IIE Trans., vol. 30, no. 1, pp. 79–90, 1998. doi: 10.1080/07408179808966439
[4]	D. M. Rose and D. R. Shier, " Cut scheduling in the apparel industry,” Computers &Operations Research, vol. 34, no. 11, pp. 3209–3228, 2007.
[5]	D. B. Nascimento, J. N. D. Figueiredo, S. F. Mayerle, P. R. Nascimento, and R. M. Casali, " A state-space solution search method for apparel industry spreading and cutting,” Int. J. Production Economics, vol. 128, no. 1, pp. 379–392, 2010. doi: 10.1016/j.ijpe.2010.07.035
[6]	W. K. Wong, " Optimisation of apparel manufacturing resource allocation using a generic optimised table-planning model,” Int. J. Advanced Manufacturing Technology, vol. 21, no. 12, pp. 935–944, 2003.
[7]	G. Wascher, H. Haubner, and H. Schumann, " An improved typology of cutting and packing problems,” European J. Operational Research, vol. 183, no. 3, pp. 1109–1130, 2007. doi: 10.1016/j.ejor.2005.12.047
[8]	W. K. Wong, C. K. Chan, and W. H. Ip, " Optimization of spreading and cutting sequencing model in garment manufacturing,” Computers in Industry, vol. 43, no. 1, pp. 1–10, 2000. doi: 10.1016/S0166-3615(00)00057-9
[9]	Z. Degraeve and M. Vandebroek, " A mixed integer programming model for solving a layout problem in the fashion industry,” Management Science, vol. 44, no. 3, pp. 301–310, 1998. doi: 10.1287/mnsc.44.3.301
[10]	Z. Degraeve, W. chet, and R. Jansbc, " Alternative formulations for a layout problem in the fashion industry,” European J. Operational Research, vol. 143, no. 1, pp. 80–93, 2002. doi: 10.1016/S0377-2217(01)00330-7
[11]	A. Toscano, S. Rangel, and H. H. Yanasse, " A heuristic approach to minimize the number of saw cycles in small-scale furniture factories,” Annals of Operations Research, vol. 258, no. 2, pp. 719–746, 2017.
[12]	M. Vanzela, G. M. Melega, S. Rangel, and S. A. D. Araujo, " The integrated lot sizing and cutting stock problem with saw cycle constraints applied to furniture production,” Computers &Operations Research, vol. 79, pp. 148–160, 2017.
[13]	D. A. Wuttke and H. S. Heese, " Two-dimensional cutting stock problem with sequence dependent setup times,” European J. Operational Research, vol. 265, no. 1, pp. 303–315, 2018. doi: 10.1016/j.ejor.2017.07.036
[14]	H. Foerster and G. Wascher, " Pattern reduction in one-dimensional cutting stock problems,” Int. J. Production Research, vol. 38, pp. 1657–1676, 2000.
[15]	H. H. Yanasse and M. S. Limeira, " A hybrid heuristic to reduce the number of different patterns in cutting stock problems,” Computers &Operations Research, vol. 33, pp. 2744–2756, 2006.
[16]	Y. Cui, C. Zhong, and Y. Yao, " Pattern-set generation algorithm for the onedimensional cutting stock problem with setup cost,” European J. Operational Research, vol. 243, no. 2, pp. 540–546, 2015.
[17]	Y. Cui, Y. P. Cui, and L. Yang, " Heuristic for the two-dimensional arbitrary stock-size cutting stock problem,” Computers &Industrial Engineering, vol. 78, pp. 195–204, 2014.
[18]	N. Ma, Y. Liu, Z. L. Zhou, and C. B. Chu, " Combined cutting stock and lot-sizing problem with pattern setup,” Computers &Operations Research, vol. 95, pp. 44–55, 2018.
[19]	Y. Cui and Z. Zhao, " Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns,” European J. Operational Research, vol. 231, no. 2, pp. 288–298, 2013. doi: 10.1016/j.ejor.2013.05.042
[20]	R. Alvarez-Valdés, R. Mart, J. M. Tamarit, and A. Parajn, " GRASP and path relinking for the two-dimensional two-staged cutting stock problem,” INFORMS J. Computing, vol. 19, no. 2, pp. 261–272, 2007.
[21]	M. Hifi and R. M’Hallah, " An exact algorithm for constrained two dimensional two-staged cutting problems,” Operations Research, vol. 53, no. 1, pp. 140–150, 2005. doi: 10.1287/opre.1040.0154
[22]	M. Hifi and R. M’Hallah, " Strip generation algorithms for constrained twodimensional two-staged cutting problems,” European J. Operational Research, vol. 172, no. 2, pp. 515–527, 2006. doi: 10.1016/j.ejor.2004.10.020
[23]	M. Hifi, R. M’Hallah, and T. Saadi, " Algorithms for the constrained two staged two-dimensional cutting problem,” INFORMS J. Computing, vol. 20, pp. 212–221, 2008. doi: 10.1287/ijoc.1070.0233
[24]	J. Li, X. H. Meng, and X. Dai, " Collision-free scheduling of multi-bridge machining systems: a colored traveling salesman problem-based approach,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 139–147, 2018. doi: 10.1109/JAS.2017.7510415
[25]	X. Meng, J. Li, M. C. Zhou, X. Dai, and J. Dou, " Population-based incremental learning algorithm for a serial colored traveling salesman problem,” IEEE Trans. Systems,Man,and Cybernetics:Systems, vol. 48, no. 2, pp. 277–288, 2018. doi: 10.1109/TSMC.2016.2591267
[26]	X. W Guo, S. X. Liu, M. C. Zhou, and G. D. Tian, " Dual-objective program and scatter search for the optimization of disassembly sequences subject to multi-resource constraints,” IEEE Trans. Automation Science and Engineering, vol. 15, no. 3, pp. 1091–1013, 2018. doi: 10.1109/TASE.2017.2731981
[27]	J. Zhao, S. X, Liu, M. C. Zhou, and X. W. Guo, L Qi, " Modified cuckoo search algorithm to solve economic power dispatch optimization problems,” IEEE/CAA J. Automatic Sinica, vol. 5, no. 4, pp. 794–806, 2018. doi: 10.1109/JAS.2018.7511138
[28]	J. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and L Qi, " An improved binary cuckoo search algorithm for solving unit commitment problem: method description,” IEEE Access, vol. 6, no. 4, pp. 43535–43545, 2018.
[29]	M. Delorme, M. Iori, and S. Martello, " Bin packing and cutting stock problems: Mathematical models and exact algorithms,” European J. Operational Research, vol. 255, no. 1, pp. 1–20, 2016. doi: 10.1016/j.ejor.2016.04.030

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(1) / Tables(7)

Get Citation

PDF

XML

Article Metrics

Article views (1497) PDF downloads(33)

A Heuristic Algorithm for the Fabric Spreading and Cutting Problem in Apparel Factories

doi: 10.1109/JAS.2019.1911573

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Export File

Citation

Format

Content