Two-dimensional Strip Packing With Unloading Constraints

dc.creatorDa Silveira J.L.M.
dc.creatorXavier E.C.
dc.creatorMiyazawa F.K.
dc.date2014
dc.date2015-06-25T17:56:34Z
dc.date2015-11-26T14:46:01Z
dc.date2015-06-25T17:56:34Z
dc.date2015-11-26T14:46:01Z
dc.date.accessioned2018-03-28T21:55:28Z
dc.date.available2018-03-28T21:55:28Z
dc.identifier
dc.identifierDiscrete Applied Mathematics. , v. 164, n. PART 2, p. 512 - 521, 2014.
dc.identifier0166218X
dc.identifier10.1016/j.dam.2013.08.019
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84894902064&partnerID=40&md5=9341a0b69a94395f5393d51731221d10
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/87065
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/87065
dc.identifier2-s2.0-84894902064
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1252671
dc.descriptionIn this paper we present approximation algorithms for the two-dimensional strip packing problem with unloading constraints. In this problem, we are given a strip S of width 1 and unbounded height, and n items of C different classes, each item ai with height h(ai), width w(ai) and class c(ai). As in the strip packing problem, we have to pack all items, minimizing the height used, but now we have the additional constraint that items of higher classes cannot block the way out of items of lower classes. For the case in which horizontal and vertical movements for removing the items are allowed, we design an algorithm whose asymptotic performance bound is 3. For the case in which only vertical movements are allowed, we design a bin packing based algorithm with an asymptotic approximation ratio of 5.745. Moreover, we also design approximation algorithms for restricted cases of both versions of the problem. These problems have practical applications in dealing with routing problems with loading/unloading constraints. © 2013 Elsevier B.V. All rights reserved.
dc.description164
dc.descriptionPART 2
dc.description512
dc.description521
dc.descriptionAzar, Y., Epstein, L., On two dimensional packing (1997) J. Algorithms, 25, pp. 290-310
dc.descriptionDa Silveira, J.L.M., Miyazawa, F.K., Xavier, E.C., Heuristics for the strip packing problem with unloading constraints (2013) Comput. Oper. Res., 40, pp. 991-1003
dc.descriptionDe Azevedo, B.L.P., Hokama, P.H., Miyazawa, F.K., Xavier, E.C., A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints (2009) Simpósio Brasileiro de Pesquisa Operacional - SBPO, , Porto Seguro, Brazil
dc.descriptionDoerner, K.F., Fuellerer, G., Hartl, R.F., Iori, M., Ant colony optimization for the two-dimensional loading vehicle routing problem (2009) Comput. Oper. Res., 36, pp. 655-673
dc.descriptionFekete, S.P., Kamphans, T., Schweer, N., Online square packing with gravity (2012) Algorithmica, pp. 1-26
dc.descriptionGendreau, M., Iori, M., Laporte, G., Martello, S., A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints (2008) Networks, 51, pp. 4-18
dc.descriptionIori, M., Salazar-Gonzalez, J.-J., Vigo, D., An exact approach for the vehicle routing problem with two-dimensional loading constraints (2007) Transp. Sci., 41, pp. 253-264
dc.descriptionJunqueira, L., Morabito, R., Yamashita, D.S., Mip-based approaches for the container loading problem with multi-drop constraints (2012) Ann. Oper. Res., 199, pp. 51-75
dc.descriptionLi, K., Cheng, K.-H., On three-dimensional packing (1990) SIAM J. Comput., 19, pp. 847-867
dc.descriptionMeir, A., Moser, L., On packing of squares and cubes (1968) J. Combin. Theory Ser. A, 5, pp. 116-127
dc.languageen
dc.publisher
dc.relationDiscrete Applied Mathematics
dc.rightsfechado
dc.sourceScopus
dc.titleTwo-dimensional Strip Packing With Unloading Constraints
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución