Item Details

Print View

On a Constrained Bin-Packing Problem

Oh, Yingfeng; Son, Sang
Format
Report
Author
Oh, Yingfeng
Son, Sang
Abstract
We study a bin-packing problem which is one-dimensional and is constrained in the manner items are placed into bins. The problem is motivated by a practical real-time scheduling problem, where redundant periodic tasks need to be assigned to a multiprocessor system. The problem is stated in the traditional light: to use as few bins as possible to pack a given list of items, and it is a generalization of the classical bin-packing problem. We first propose a heuristic algorithm called First-Fit-K to solve the bin-packing problem, and then prove that First-Fit-K has an asymptotical worst-case tight bound of 1.7. We also study the average-case performance of the algorithm. The simulation results show that First-Fit-K performs within 10% of the optimal solution.
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1995
Published Date
1995
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra Open Repository

Availability

Access Online