Developing a heuristics for glass cutting process optimization: A case of two-dimensional two-stage guillotine cutting with multiple stock sizes

Kyung Tae Park; Jun-Hyung Ryu; Ho-Kyung Lee; In-Beum Lee

Korean Journal of Chemical Engineering, Vol.30, No.2, 278-285, February, 2013

DOI10.1007/s11814-012-0125-x Export Citation

Developing a heuristics for glass cutting process optimization: A case of two-dimensional two-stage guillotine cutting with multiple stock sizes

Kyung Tae Park, Jun-Hyung Ryu^{1, †}, Ho-Kyung Lee², and In-Beum Lee

Department of Chemical Engineering, POSTECH, Pohang 790-784, Korea
¹Department of Nuclear and Energy System, Dongguk University, Gyeongju 780-714, Korea
²LG Chemistry Ltd., Research Park, Deajeon 305-380, Korea

E-mail:

This paper presents a heuristic algorithm for a two-dimensional two-stage guillotine cutting problem with multiple stock sizes by allowing the rotation of items by 90o. The proposed algorithm generates levels or strips where the first item or base item is selected according to the length of the strip and packs the next items beside the base item in the strip. For each type of item, strips are generated for packing each type of item in a base item. The best n orders in a yield of strips or the best n strips are selected for each type of item. The selected best n strips are packed in one type of bin. For the other types of bins, another best n strips are selected and packed in each type of bin. The best yield in all types of bins is then selected. This iteration is executed until the number of item demands in the overall demands is less than the number of item demands in the bin. Four numerical examples generated from actual industries are illustrated to highlight the applicability of the proposed algorithm with some comments.

Keywords:Glass Production;Two-dimensional Two-stage;Guillotine Cut;Level Packing Problem

[References]

Wascher G, Hauβner H, Schumann H, Eur. J. Oper. Res., 183, 1109 (2007)
Dyckhoff H, Eur. J. Oper. Res., 44, 145 (1990)
Lodi A, Martello S, Monaci M, Eur. J. Oper. Res., 141(2), 241 (2002)
Pisinger D, Sigurd M, Discrete Optim., 2(2), 154 (2005)
Puchinger J, Raidl GR, Eur. J. Oper. Res., 183(3), 1304 (2007)
Lodi A, Martello S, Vigo D, INFORMS J. Comput., 11, 345 (1999)
Chung FRK, Garey MR, Johnson DS, SIAM J. ALGEBRA DISCR., 3(1), 66 (1982)
Coffman EG, Garey MR, Johnson DS, Tarjan RE, SIAM J. Comput., 9(4), 808 (1980)
Wua TH, Chen JF, Lowa C, Tanga PT, Int. J. Prod. Res., 41(16), 3883 (2003)
Ntene N, van Vuuren JH, Discrete Optim., 6(2), 174 (2009)
Ryu JH, Korean J. Chem. Eng., 27(6), 1681 (2010)
Ryu JH, Lee IB, Korean Chem. Eng. Res., 46(4), 792 (2008)

[Referenced By]

[Related Articles]

[1] Wascher G, Hauβner H, Schumann H, Eur. J. Oper. Res., 183, 1109 (2007)

[2] Dyckhoff H, Eur. J. Oper. Res., 44, 145 (1990)

[3] Lodi A, Martello S, Monaci M, Eur. J. Oper. Res., 141(2), 241 (2002)

[4] Pisinger D, Sigurd M, Discrete Optim., 2(2), 154 (2005)

[5] Puchinger J, Raidl GR, Eur. J. Oper. Res., 183(3), 1304 (2007)

[6] Lodi A, Martello S, Vigo D, INFORMS J. Comput., 11, 345 (1999)

[7] Chung FRK, Garey MR, Johnson DS, SIAM J. ALGEBRA DISCR., 3(1), 66 (1982)

[8] Coffman EG, Garey MR, Johnson DS, Tarjan RE, SIAM J. Comput., 9(4), 808 (1980)

[9] Wua TH, Chen JF, Lowa C, Tanga PT, Int. J. Prod. Res., 41(16), 3883 (2003)

[10] Ntene N, van Vuuren JH, Discrete Optim., 6(2), 174 (2009)

[11] Ryu JH, Korean J. Chem. Eng., 27(6), 1681 (2010)

[12] Ryu JH, Lee IB, Korean Chem. Eng. Res., 46(4), 792 (2008)