Bin packing with divisible item sizes and rejection penalties
文献类型：期刊论文
| 作者 | Li, Jianping1; Pan, Pengxiang1; Cai, Lijian1; Lichen, Junran2; Wang, Wencheng1 |
| 刊名 | OPTIMIZATION LETTERS
 |
| 出版日期 | 2021-09-21 |
| 页码 | 11 |
| 关键词 | Combinatorial optimization Bin packing Divisible item sizes Rejection penalties Exact combinatorial algorithms |
| ISSN号 | 1862-4472 |
| DOI | 10.1007/s11590-021-01803-3 |
| 英文摘要 | The bin packing problem with divisible item sizes and rejection penalties (the BP-DR problem, for short) is defined as follows. Given a lot of bins with same capacity limitation L and a set X = {x(1), ..., x(n)} of items with a size function s : X -> Z(+) and a penalty function p : X -> R+, where the item sizes are divisible, i.e., either s(x(i))vertical bar s(x(j)) or s(x(j))vertical bar s(x(i)) for any two items xi and x j with 1 <= i < j <= n, each of these n items must be either put into a bin under the constraint that the summation of sizes of items in that bin does not exceed L, or rejected with its penalty that we must pay for. No item can be spread into more than one bin. We consider the BP-DR problem and its important variant. (1) The BP-DR problem is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above, the objective is to minimize the number of bins used plus the summation of penalties paid for the rejected items, and (2) Given a penalty budget B is an element of R+, the bin packing problem with divisible item sizes and bounded rejection penalties (the BP-DBR problem, for short) is asked to find a subset of items such that the items in that subset can be put in some bins to satisfy the constraint mentioned-above and that the summation of penalties paid for the rejected items does not exceed B, the objective is to minimize the number of bins used. In this paper, we design two exact combinatorial algorithms to solve the BP-DR problem and the BP-DBR problem, respectively. |
| 资助项目 | National Natural Science Foundation of China[11861075] ; National Natural Science Foundation of China[12101593] ; Project for Innovation Team (Cultivation) of Yunnan Province[202005AE160006] ; Key Project of Yunnan Provincial Science and Technology Department[2018FY001014] ; Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province[C176240111009] ; Project of Yunling Scholars Training of Yunnan Province ; Project of Doctorial Fellow Award of Yunnan Province[2018010514] ; Project of Yunnan Provincial Department of Education Science Research Fund[2020Y0040] ; Yunnan University[2018FY001014] |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000698064500001 |
| 出版者 | SPRINGER HEIDELBERG |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/59287]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Li, Jianping |
| 作者单位 | 1.Yunnan Univ, Dept Math, Fast Outer Ring South Rd, Kunming 650504, Yunnan, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, 55 Zhongguancun East Rd, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Li, Jianping,Pan, Pengxiang,Cai, Lijian,et al. Bin packing with divisible item sizes and rejection penalties[J]. OPTIMIZATION LETTERS,2021:11. |
| APA | Li, Jianping,Pan, Pengxiang,Cai, Lijian,Lichen, Junran,&Wang, Wencheng.(2021).Bin packing with divisible item sizes and rejection penalties.OPTIMIZATION LETTERS,11. |
| MLA | Li, Jianping,et al."Bin packing with divisible item sizes and rejection penalties".OPTIMIZATION LETTERS (2021):11. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。