Motivated by bursty bandwidth allocation and by the allocation of virtual machines to servers in the cloud, we consider the online problem of packing items with random sizes into unit-capacity bins. Items arrive sequentially, but upon arrival an item's actual size is unknown; only its probabilistic information is available to the decision maker. Without knowing this size, the decision maker must irrevocably pack the item into an available bin or place it in a new bin. Once packed in a bin, the decision maker observes the item's actual size, and overflowing the bin is a possibility. An overflow incurs a large penalty cost and the corresponding bin is unusable for the rest of the process. In practical terms, this overflow models delayed services, failure of servers, and/or loss of end-user goodwill. The objective is to minimize the total expected cost given by the sum of the number of opened bins and the overflow penalty cost. We present an online algorithm with expected cost at most a constant factor times the cost incurred by the optimal packing policy when item sizes are drawn from an i.i.d. sequence of unknown length. We give a similar result when item size distributions are exponential with arbitrary rates. We also study the offline model, where distributions are known in advance but must be packed sequentially. We construct a soft-capacity PTAS for this problem, and show that the complexity of computing the optimal offline cost is $\#\mathbf{P}$-hard. Finally, we provide an empirical study of our online algorithm's performance.
翻译:受爆炸带宽分配和将虚拟机器分配到云层服务器的驱动, 我们考虑将随机大小的物品包装到单位容量桶中的在线问题。 物品按顺序运抵, 但到达时项目的实际大小未知; 只有其概率信息可供决策者使用。 决策者在不知道此大小的情况下, 必须不可撤销地将物品包装到一个可用的垃圾桶或将其放置在一个新的垃圾箱中。 一旦包装在垃圾箱中, 决策者观察项目的实际大小, 并填满垃圾箱是有可能的。 溢出要支付大笔罚款费用, 相应的垃圾桶无法用于进程的其余部分。 实际上, 这种溢出模型延迟服务、 服务器故障和/ 或终端用户善意的丢失。 目标是将打开的垃圾箱和溢出罚款的总额所给出的预期总成本。 我们提出在线算, 当项目大小从 I. i.d. d. 抽取最佳包装政策产生的成本时, 我们给出了一个不为人所知的软长度序列, 我们给出了一种不为人知的精确的逻辑性计算结果 。 我们给出了一种不甚为精确的排序的序列 。 我们给出了我们所知道的序列的序列的序列的序列的序列分配结果 。