Paper Info

Title | ||
---|---|---|

Bin Packing with Item Fragmentation |

Abstract | ||
---|---|---|

We investigate a variant of the bin packing problem in which items may be fragmented into smaller size pieces called fragments. While there are a fewapplications to bin packing with item fragmentation, our model of the problem is derived from a scheduling problem present in data over CATV networks. Fragmenting an item is associated with a cost which renders the problem NP-hard. We study two possible cost functions and as a result get two variants of bin packing with item fragmentation. In the first variant, called bin packing with size-increasing fragmentation, each item may be fragmented in which case overhead units are added to the size of every fragment. In the second variant each item has a size and a cost and fragmenting an item increases its cost but does not change its size. We call this variant bin packing with sizepreserving fragmentation. We develop several algorithms for the problem and investigate their performance. The algorithms we present are based on well known bin packing algorithms such as Next-Fit and First-Fit Decreasing, as well as of other algorithms. |

Year | DOI | Venue |
---|---|---|

2001 | 10.1007/3-540-44634-6_29 | WADS |

Keywords | Field | DocType |

scheduling problem present,item fragmentation,problem np-hard,bin packing problem,bin packing,smaller size piece,sizepreserving fragmentation,size-increasing fragmentation,possible cost function,variant bin packing,scheduling problem,cost function | Job shop scheduling,Scheduling (computing),Computer science,Algorithm,Fragmentation (computing),Bin packing problem,Cable television | Conference |

Volume | ISSN | ISBN |

2125 | 0302-9743 | 3-540-42423-7 |

Citations | PageRank | References |

14 | 1.00 | 7 |

Authors | ||

2 |

Authors (2 rows)

Cited by (14 rows)

References (7 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Nir Menakerman | 1 | 16 | 1.43 |

Raphael Rom | 2 | 1165 | 240.85 |