×

The one-dimensional cutting stock problem with usable leftover - a heuristic approach. (English) Zbl 1176.90158

Summary: We consider a one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future, if large enough. This feature introduces difficulties in comparing solutions of the cutting problem, for example, up to what extent a minimum leftover solution is the most interesting one when the leftover may be used. Some desirable characteristics of good solutions are defined and classical heuristic methods are modified, so that cutting patterns with undesirable leftover (not large enough to be used, nor too small to be acceptable waste) are redesigned. The performance of the modified heuristics is observed by solving instances from the literature, practical instances and randomly generated instances.

MSC:

90B30 Production models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abuabara, A., 2006. OtimizaçÃo no corte de tubos estruturais: aplicaçÃo na indústria aeronáutica agrı´cola. MS Dissertation, DEP -UFSCar, São Carlos, SP, Brazil.; Abuabara, A., 2006. OtimizaçÃo no corte de tubos estruturais: aplicaçÃo na indústria aeronáutica agrı´cola. MS Dissertation, DEP -UFSCar, São Carlos, SP, Brazil.
[2] Cherri, A.C., 2006. O problema de corte de estoque com reaproveitamento da sobras de material. MS Dissertation, ICMC - USP, São Carlos, SP, Brazil.; Cherri, A.C., 2006. O problema de corte de estoque com reaproveitamento da sobras de material. MS Dissertation, ICMC - USP, São Carlos, SP, Brazil.
[3] Cherri, A.C., Arenales, M.N., Yanasse, H.H., 2007. The unidimensional cutting stock problem with usable leftover – a heuristic approach. Technical Report - Notas do ICMC, Series ComputaçÃo, 90, ICMC - USP.; Cherri, A.C., Arenales, M.N., Yanasse, H.H., 2007. The unidimensional cutting stock problem with usable leftover – a heuristic approach. Technical Report - Notas do ICMC, Series ComputaçÃo, 90, ICMC - USP. · Zbl 1176.90158
[4] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 848-859 (1961) · Zbl 0096.35501
[5] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem - Part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[6] Gradisar, M.; Trkman, P., A combined approach to the solution to the general one-dimensional cutting stock problem, Computers and Operations Research, 32, 1793-1807 (2005) · Zbl 1074.90045
[7] Gradisar, M.; Jesenko, J.; Resinovic, C., Optimization of roll cutting in clothing industry, Computers and Operational Research, 10, 945-953 (1997) · Zbl 0893.90144
[8] Gradisar, M.; Kljajic, M.; Resinovic, C.; Jesenko, J., A sequential heuristic procedure for one-dimensional cutting, European Journal of Operational Research, 114, 557-568 (1999) · Zbl 0938.90058
[9] Gradisar, M.; Resinovic, C.; Kljajic, M., A hybrid approach for optimization of one-dimensional cutting, European Journal of Operational Research, 119, 719-728 (1999) · Zbl 0945.90049
[10] Hinxman, A., The trim-loss and assortment problems: a survey, European Journal of Operational Research, 5, 8-18 (1980) · Zbl 0442.90072
[11] Poldi, K.C., Arenales, M.N., 2005. Dealing with small demand in integer cutting stock problems with limited different stock lengths. Notes of the ICMC - Series Computation, 85, ICMC - USP, São Carlos, SP, Brazil.; Poldi, K.C., Arenales, M.N., 2005. Dealing with small demand in integer cutting stock problems with limited different stock lengths. Notes of the ICMC - Series Computation, 85, ICMC - USP, São Carlos, SP, Brazil.
[12] Stadtler, H., A one-dimensional cutting stock problem in the aluminium industry and its solution, European Journal of Operational Research, 44, 209-223 (1990) · Zbl 0684.90049
[13] Trkman, P., 2005. Private Communication (09/11/2005).; Trkman, P., 2005. Private Communication (09/11/2005).
[14] Wäscher, G.; Gau, T., Heuristics for the integer one-dimensional cutting stock problem: a computational study, OR Spectrum, 18, 131-144 (1996) · Zbl 0853.90099
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.