Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns. (English) Zbl 1381.90059
Summary: A sequential value correction heuristic is presented for the two-dimensional cutting stock problem with three-staged homogenous patterns, considering both input-minimization and simplicity of the cutting process. The heuristic constructs many cutting plans iteratively and selects the best one as the solution. The patterns in each cutting plan are generated sequentially using simple recursive techniques. The values of the item types are corrected after the generation of each pattern to diversify the cutting plans. Computational results indicate that the proposed heuristic is more effective in input minimization than published algorithms and commercial stock cutting software packages that use three-staged general or exact patterns.
MSC:
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
two-dimensional cutting stock; homogenous three-staged patterns; sequential value correctionSoftware:
CutlogicReferences:
| [1] | DOI: 10.1057/jors.1985.51 · doi:10.1057/jors.1985.51 |
| [2] | DOI: 10.1287/ijoc.1050.0132 · Zbl 1241.90070 · doi:10.1287/ijoc.1050.0132 |
| [3] | DOI: 10.1057/palgrave.jors.2602393 · Zbl 1153.90444 · doi:10.1057/palgrave.jors.2602393 |
| [4] | DOI: 10.1016/j.ejor.2007.08.007 · Zbl 1146.90499 · doi:10.1016/j.ejor.2007.08.007 |
| [5] | DOI: 10.1016/j.cor.2006.02.029 · Zbl 1149.90428 · doi:10.1016/j.cor.2006.02.029 |
| [6] | DOI: 10.1016/j.ejor.2014.06.032 · Zbl 1339.90278 · doi:10.1016/j.ejor.2014.06.032 |
| [7] | DOI: 10.1057/jors.2014.33 · doi:10.1057/jors.2014.33 |
| [8] | DOI: 10.1016/j.ejor.2011.10.047 · Zbl 1244.90190 · doi:10.1016/j.ejor.2011.10.047 |
| [9] | DOI: 10.1080/10556780903420531 · Zbl 1226.90087 · doi:10.1080/10556780903420531 |
| [10] | DOI: 10.1080/0305215X.2013.841903 · doi:10.1080/0305215X.2013.841903 |
| [11] | DOI: 10.1016/j.cor.2012.11.020 · Zbl 1349.90853 · doi:10.1016/j.cor.2012.11.020 |
| [12] | DOI: 10.1016/j.ijpe.2013.03.011 · doi:10.1016/j.ijpe.2013.03.011 |
| [13] | DOI: 10.1287/mnsc.17.12.B793 · Zbl 0219.90021 · doi:10.1287/mnsc.17.12.B793 |
| [14] | DOI: 10.1023/A:1008743711658 · Zbl 0963.90051 · doi:10.1023/A:1008743711658 |
| [15] | Huang S., Comput. Eng. Appl. 47 pp 234– (2011) |
| [16] | DOI: 10.1007/0-387-25383-1_8 · doi:10.1007/0-387-25383-1_8 |
| [17] | DOI: 10.1023/B:JOCO.0000038915.62826.79 · Zbl 1084.90031 · doi:10.1023/B:JOCO.0000038915.62826.79 |
| [18] | DOI: 10.1590/S0101-74382000000200002 · Zbl 1181.90232 · doi:10.1590/S0101-74382000000200002 |
| [19] | DOI: 10.1016/j.ejor.2005.11.064 · Zbl 1135.90029 · doi:10.1016/j.ejor.2005.11.064 |
| [20] | DOI: 10.1016/j.ejor.2010.01.039 · Zbl 1188.90181 · doi:10.1016/j.ejor.2010.01.039 |
| [21] | DOI: 10.1016/j.ejor.2004.10.034 · Zbl 1136.90533 · doi:10.1016/j.ejor.2004.10.034 |
| [22] | DOI: 10.1016/j.ijpe.2004.12.017 · doi:10.1016/j.ijpe.2004.12.017 |
| [23] | DOI: 10.1287/mnsc.47.6.864.9809 · Zbl 1232.90326 · doi:10.1287/mnsc.47.6.864.9809 |
| [24] | DOI: 10.1016/j.ejor.2005.12.047 · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
