A new version of on-line variable-sized bin packing

✍ Scribed by Guochuan Zhang

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 304 KB
• Volume: 72
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00018-2

✦ Synopsis

This paper investigates a new version of the on-line variable-sized bin packing problem. Suppose that bin capacities can vary. Given a list of items, the goal is to pack items in the bins which arrive in an on-line way such that the total size of bins used is minimized. It is shown that next fit and first fit (decreasing) algorithms all have a worst-case performance bound of 2.