Actas de congresos
Two-dimensional Strip Packing With Unloading Constraints
Registro en:
Discrete Applied Mathematics. , v. 164, n. PART 2, p. 512 - 521, 2014.
0166218X
10.1016/j.dam.2013.08.019
2-s2.0-84894902064
Autor
Da Silveira J.L.M.
Xavier E.C.
Miyazawa F.K.
Institución
Resumen
In 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. 164 PART 2 512 521 Azar, Y., Epstein, L., On two dimensional packing (1997) J. Algorithms, 25, pp. 290-310 Da 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 De 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 Doerner, 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 Fekete, S.P., Kamphans, T., Schweer, N., Online square packing with gravity (2012) Algorithmica, pp. 1-26 Gendreau, 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 Iori, 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 Junqueira, 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 Li, K., Cheng, K.-H., On three-dimensional packing (1990) SIAM J. Comput., 19, pp. 847-867 Meir, A., Moser, L., On packing of squares and cubes (1968) J. Combin. Theory Ser. A, 5, pp. 116-127