An asymptotically optimal algorithm for online stacking

Martin Olsen (), Lars Nørvang Andersen () and Allan Gross ()
Additional contact information
Martin Olsen: Aarhus University
Lars Nørvang Andersen: Aarhus University
Allan Gross: Aarhus University

Mathematical Methods of Operations Research, 2023, vol. 97, issue 2, No 2, 178 pages

Abstract: Abstract Consider a storage area where arriving items are stored temporarily in bounded capacity stacks until their departure. We look into the problem of deciding where to put an arriving item with the objective of minimizing the maximum number of stacks used over time. The decision has to be made as soon as an item arrives, and we assume that we only have information on the departure times for the arriving item and the items currently at the storage area. We are only allowed to put an item on top of another item if the item below departs at a later time. We refer to this problem as online stacking. We assume that the storage time intervals are picked i.i.d. from $$[0, 1] \times [0, 1]$$ [ 0 , 1 ] × [ 0 , 1 ] using an unknown distribution with a bounded probability density function. Under this mild condition, we present a simple polynomial time online algorithm and show that the competitive ratio converges to 1 in probability. The result holds if the stack capacity is $$o(\sqrt{n})$$ o ( n ) , where n is the number of items, including the realistic case where the capacity is a constant. Our experiments show that our results also have practical relevance.

Keywords: Online algorithms; Stacking; Stowage; Asymptotic optimality (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-022-00808-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:97:y:2023:i:2:d:10.1007_s00186-022-00808-7

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-022-00808-7

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().