首页> 外文会议>Institution of Engineering and Technology International Conference on Wireless Communications and Applications >An automatic verifier for the feasibility of special cases of the offline dynamic storage allocation problem
【24h】

An automatic verifier for the feasibility of special cases of the offline dynamic storage allocation problem

机译:用于离线动态存储分配问题的特殊情况的自动验证者

获取原文

摘要

The offline Dynamic Storage Allocation (DSA) problem is a well-known problem in combinatorial optimization. The problem is one of packing a set of blocks of arbitrary sizes on an area, with the objective of minimizing the area's usage along the y-axis, under the condition that the x-position of the blocks are fixed (as given in the input). The problem has uses in memory management, berth allocation, and can potentially be used in the allocation of bandwidth resources in a network. Li et al. [4] considered the case of the problem where the width of the blocks (their dimension along the y-axis) is to be no larger than a given number. They obtained several approximation algorithms for special cases of the problem, by first studying the feasibility of several subcases with further restriction, such as limiting the y-dimension of the area to pack the blocks. We believe that such feasibility results on subcases of the problem can help in obtaining algorithms for other special cases of the problem. In this paper we propose a method to automatically derive such results. Our implementation of a simplified version of the proposed method in C++ correctly duplicated many of the earlier results obtained by Li et al.
机译:离线动态存储分配(DSA)问题是组合优化中的众所周知的问题。问题是在一个区域上包装一组任意尺寸的块之一,目的是在块的x位置固定的条件下最小化沿着y轴的区域的使用(如输入所示)。问题在内存管理,泊位分配中使用,并且可以在网络中分配带宽资源的分配中。李等人。 [4]考虑了块的宽度(沿着Y轴)的宽度的问题的情况不大于给定数量。它们通过首先研究具有进一步限制的若干子级的可行性,例如限制该区域的Y尺寸来包装块的若干子级的可行性来获得几个问题的近似算法。我们认为,此类可行性导致问题的提案可以有助于获得其他特殊情况的算法。在本文中,我们提出了一种自动推导出这样的结果的方法。我们在C ++中实现了所提出的方法的简化版本,正确重复了Li等人获得的许多前面结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号