HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Linear probing with lazy deletions, parking problem with exponential sojourn time, receiver release Cambridge ring and other related problems

Abstract : In this paper we intend to give an exact analytical evaluation of some parameters arising in a general bin-packing problem. There is an infinite sequence of cells ranked from the left to the right. A cell is either empty, either busy, i.e. contains an item. Items are generated over the cells according to independent Poisson processes of l item per cell and per time unit. When an item is generated on an empty cell it enters the cell which therefore becomes busy. When an item is generated on a busy cell, it tries the next cell on the right and so forth, until it finds an empty cell which it enters. Each stored item has a sojourn time in the cell which is supposed to be exponential of mean one. When the item leaves a cell it disappears completely, i.e. quits the system, the cell immediately becomes empty and available for a next item. We give an exact evaluation of the steady state of the system in terms of a Taylor expansion with respect to variable l.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074856
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:35:10 PM
Last modification on : Friday, February 4, 2022 - 3:13:30 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:45:41 PM

Identifiers

  • HAL Id : inria-00074856, version 1

Collections

Citation

Philippe Jacquet. Linear probing with lazy deletions, parking problem with exponential sojourn time, receiver release Cambridge ring and other related problems. [Research Report] RR-1816, INRIA. 1992. ⟨inria-00074856⟩

Share

Metrics

Record views

42

Files downloads

39