On a Constrained Bin-packing Problem

Authors:Oh, Yingfeng, Department of Computer ScienceUniversity of Virginia Son, Sang, Department of Computer ScienceUniversity of Virginia

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.

All rights reserved (no additional license for public reuse)
Source Citation:

Oh, Yingfeng, and Sang Son. "On a Constrained Bin-packing Problem." University of Virginia Dept. of Computer Science Tech Report (1995).

University of Virginia, Department of Computer Science
Published Date: