




























Stacking is an important process within logistics. Some notable examples of items to be stacked are steel bars or steel plates in a steel yard or containers in a container terminal or on a ship. We say that two items are conflicting if their storage time intervals overlap in which case one of the items needs to be rehandled if the items are stored at the same LIFO storage location. We consider the problem of stacking items using $k$ LIFO locations with a minimum number of conflicts between items sharing a location. We present an extremely simple online stacking algorithm that is oblivious to the storage time intervals and storage locations of all other items when it picks a storage location for an item. The risk of assigning the same storage location to two conflicting items is proved to be of the order $1/k^2$ under mild assumptions on the distribution of the storage time intervals for the items. Intuitively, it seems natural to pick a storage location uniformly at random in the oblivious setting implying a risk of $1/k$ so the risk for our algorithm is surprisingly low. Our results can also be expressed within the context of the MAX $k$-CUT problem for circle graphs. The results indicate that circle graphs on average have relatively big $k$-cuts compared to the total number of edges.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。