Two-dimensional on-line bin packing problem with rotatable items

被引：22

作者：

Fujita, S ^{[1
]}

Hada, T ^{[1
]}

机构：

[1] Hiroshima Univ, Grad Sch Engn, Dept Informat Engn, Higashihiroshima 7398527, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2002年 / 289卷 / 02期

关键词：

on-line algorithm; two-dimensional bin packing; rotation of items;

D O I：

10.1016/S0304-3975(01)00410-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is "rotatable" by 90degrees. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：939 / 952

页数：14

共 7 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BLITZ D, 1996, UNPB LOWER BOUNDS AS

[3] MULTIDIMENSIONAL ONLINE BIN PACKING - ALGORITHMS AND WORST-CASE ANALYSIS [J].

COPPERSMITH, D ;

RAGHAVAN, P .

OPERATIONS RESEARCH LETTERS, 1989, 8 (01) :17-20

[4] AN ONLINE ALGORITHM FOR MULTIDIMENSIONAL BIN PACKING [J].

CSIRIK, J ;

VANVLIET, A .

OPERATIONS RESEARCH LETTERS, 1993, 13 (03) :149-158

[5] A SIMPLE ONLINE BIN-PACKING ALGORITHM [J].

LEE, CC ;

LEE, DT .

JOURNAL OF THE ACM, 1985, 32 (03) :562-572

[6] IMPROVED BOUNDS FOR HARMONIC-BASED BIN PACKING ALGORITHMS [J].

RICHEY, MB .

DISCRETE APPLIED MATHEMATICS, 1991, 34 (1-3) :203-227

[7] AN IMPROVED LOWER BOUND FOR ONLINE BIN PACKING ALGORITHMS [J].

VANVLIET, A .

INFORMATION PROCESSING LETTERS, 1992, 43 (05) :277-284

← 1 →