Abstract
We consider a generalized one-dimensional bin-packing model where the cost of a bin is a nondecreasing concave function of the utilization of the bin. Four popular heuristics from the literature of the classical bin-packing problem are studied: First Fit (FF), Best Fit (BF), First Fit Decreasing (FFD), and Best Fit Decreasing (BFD). We analyze their worst-case performances when they are applied to our model. The absolute worst-case performance ratio of FF and BF is shown to be exactly 2, and that of FFD and BFD is shown to be exactly 1.5. Computational experiments are also conducted to test the performance of these heuristics. © 2006 Wiley Periodicals, Inc.
| Original language | English |
|---|---|
| Pages (from-to) | 298-308 |
| Journal | Naval Research Logistics |
| Volume | 53 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Jun 2006 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
This research was supported in part by the Research Grants Council of the Hong Kong Special Administrative Region, China, under Grant PolyU5312/04E and by theNational Science Foundation under Grant DMI-0196536.
Research Keywords
- Bin packing
- Concavity
- Worst-case analysis
RGC Funding Information
- RGC-funded
Fingerprint
Dive into the research topics of 'Bin-packing problem with concave costs of bin utilization'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver