Bin packing with divisible item sizes and rejection penalties

doi:10.1007/s11590-021-01803-3

	Bin packing with divisible item sizes and rejection penalties
	Li, Jianping 2; Pan, Pengxiang 2; Cai, Lijian 2; Lichen, Junran 1; Wang, Wencheng 2
刊名	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
语种	英语
出版者	SPRINGER HEIDELBERG
WOS记录号	WOS:000698064500001
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/59287]
专题	中国科学院数学与系统科学研究院
通讯作者	Li, Jianping
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, 55 Zhongguancun East Rd, Beijing 100190, Peoples R China 2.Yunnan Univ, Dept Math, Fast Outer Ring South Rd, Kunming 650504, Yunnan, 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.