No Access

A 4/3-APPROXIMATION ALGORITHM FOR CASSETTE PACKING IN STEEL INDUSTRY

HARK-CHIN HWANG

Department of Industrial Engineering, Chosun University, 375 Seosuk-Dong, Dong-Gu, Gwangju 501-759, Korea

https://doi.org/10.1142/S0217595907001462Cited by:1 (Source: Crossref)

Abstract

In packing steel products of coils into cassettes, we need to consider both the width and weight capacity of cassettes. Each coil has weight in (0, 1/3] and width in (1/6, 1/3] when scaling both the weight and width capacities to 1. With the objective of minimizing the number of cassettes to pack the coils, the problem is modeled by two-dimensional vector packing. To efficiently pack the coils having sizes specified by the ranges, we develop a 4/3-approximation algorithm.

Keywords:

References

S. Y. Chang, H. C. Hwang and S. Park, Computers & Operations Research 32, 2051 (2005). Crossref, Web of Science, Google Scholar
C. Chekuri and S. Khanna, On multi-dimensional packing problems, Proceedings of the 10th Annual ACM–SIAM Symposium on Discrete Algorithms (ACM Press, New York, 1999) pp. 185–194. Google Scholar
E. G. Coffman Jr. , M. R. Garey and D. S. Johnson , Approximation Algorithms for NP-hard Problems , ed. D. S. Hochbaum ( PWS Publishing Company , 1997 ) . Google Scholar
W. Fernandez de la Vega and G. S. Lueker, Combinatorica 1, 349 (1981). Crossref, Web of Science, Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the theory of NP-Completeness ( Freeman , San Francisco, CA , 1979 ) . Google Scholar
Johnson, D. S. (1973). Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge, MA . Google Scholar
H. Kellerer and V. Kotov, Operations Research Letters 31, 35 (2003). Crossref, Web of Science, Google Scholar
F. C. R. Spieksma, Computers & Operations Research 21, 19 (1994). Crossref, Web of Science, Google Scholar
G. J. Woeginger, Information Processing Letters 64, 293 (1997). Crossref, Web of Science, Google Scholar
A. C. C. Yao, Journal of the ACM 27, 207 (1980). Crossref, Web of Science, Google Scholar