Bin packing with divisible item sizes and rejection penalties

doi:10.1007/s11590-021-01803-3

CSpace

	Bin packing with divisible item sizes and rejection penalties
	Li, Jianping 1; Pan, Pengxiang 1; Cai, Lijian 1; Lichen, Junran 2; Wang, Wencheng 1
	2021-09-21
发表期刊	OPTIMIZATION LETTERS
ISSN	1862-4472
页码	11
摘要	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.
关键词	Combinatorial optimization Bin packing Divisible item sizes Rejection penalties Exact combinatorial algorithms
DOI	10.1007/s11590-021-01803-3
收录类别	SCI
语种	英语
资助项目	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类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000698064500001
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/59288
专题	中国科学院数学与系统科学研究院
通讯作者	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.